Skip to main content



1. Algebraic Preliminaries

We review in this chapter the basic algebraic structures and algorithms that will be used throughout this book. This chapter is not intended to be a replacement for an introductory course in abstract algebra, and we expect the reader to have already encountered the definitions and fundamental properties of rings, fields and polynomials. We only recall those definitions here and describe some algorithms on polynomials that are not always covered in introductory algebra courses. Since they are well-known algorithms in computer algebra, we do not reprove their correctness here, but give references instead. For a comprehensive introduction to constructive algebra and algebraic algorithms, including more efficient alternatives for computing greatest common divisors of polynomials, we recommend consulting introductory computer algebra textbooks [2, 29, 31, 50, 82]. Readers with some background in algebra can skip this chapter and come back to it later as needed.
Manuel Bronstein

2. Integration of Rational Functions

We describe in this chapter algorithms for the integration of rational functions. This case, which is the simplest since rational functions always have elementary integrals, is important because the algorithms for integrating more complicated functions are essentially generalizations of the techniques used for rational functions. Since the algorithms and theorems of this chapter are special cases of the Risch algorithm, we postpone the proof of their correctness until the later chapters on integrating transcendental functions.
Manuel Bronstein

3. Differential Fields

We develop in this chapter the algebraic machinery in which the integration algorithms can be presented and proved correct. The main idea, which originates from J. F. Ritt [63], is to define the notion of derivation in a pure algebraic setting (i.e. without using the notions of “function”, “limit”, and “tangent line” from analysis) and to study the properties of such formal derivations on arbitrary objects. This way, we can later translate an integration problem to solving an equation in some algebraic structure, which can be done using algebraic algorithms. Since an arbitrary transcendental function can be seen as a univariate rational function over a field with an arbitrary derivation, we first need to study the general properties of derivations over rings and fields. This will allow us to generalize the rational function integration algorithms to large classes of transcendental functions (Chap. 5).
Manuel Bronstein

4. The Order Function

We introduce in this chapter the order function at an element, which will be our main tool later when we prove the correctness of the integration algorithm. The usefulness of this function is that it maps elements of arbitrary unique factorization domains into integers, so applying it on both sides of an equation produces equations and inequalities involving integers, making it possible to either prove that the original equation cannot have a solution, or to compute estimates for the orders of its solutions. Therefore it is used in many contexts besides integration, for example in algorithms for solving differential equations. While we use only the order function at a polynomial in the integration algorithm, we introduce it here in unique factorization domains of arbitrary characteristic, and study its properties in the general case when the order is taken at an element that is not necessarily irreducible.
Manuel Bronstein

5. Integration of Transcendental Functions

Having developped the required machinery in the previous chapters, we can now describe the integration algorithm. In this chapter, we define formally the integration problem in an algebraic setting, prove the main theorem of symbolic integration (Liouville’s Theorem), and describe the main part of the integration algorithm.
Manuel Bronstein

6. The Risch Differential Equation

We describe in this chapter the solution to the Risch differential equation problem, i.e. given a differential field K of characteristic 0 and f, gK, to decide whether the equation
$${\text{Dy + fy = g}}$$
has a solution in K, and to find one if there are some. We only study equation (6.1) in the transcendental case, i.e. when K is a simple monomial extension of a differential subfield k, so for the rest of this chapter, let k be a differential field of characteristic 0 and t be a monomial over k. We suppose that the coefficients f and g of our equation are in k(t) and look for a solution yk(t). The algorithm we present in this chapter proceeds as follows:
Compute the normal part of the denominator of any solution. This reduces the problem to finding a solution in k<t>.
Compute the special part of the denominator of any solution. This reduces the problem to finding a solution in k[t].
Bound the degree of any solution in k[t].
Reduce equation (6.1) to one of a similar form but with f, gk[t].
Find the solutions in k[t] of bounded degree of the reduced equation.
Manuel Bronstein

7. Parametric Problems

We describe in this chapter solutions to several integration-related problems involving parameters. Those problems arise as subproblems in the integration algorithm: the limited integration problem, which arises from integrating polynomials in a primitive extension (Sect. 5.8) and the parametric logarithmic derivative problem, which arises from recognizing logarithmic derivatives (Sect. 5.12) and from bounding orders and degrees of solutions of the Risch differential equation (Sects. 6.2 and 6.3). The common thread between those problems is that they ask whether there exists constants for which a given parametric differential equation has a solution in a given differential field.
Manuel Bronstein

8. The Coupled Differential System

We describe in this chapter the solution to the coupled differential system problem, i.e. given a differential field K of characteristic 0 and f 1, f 2, g 1, g 2 in K, to decide whether the system of equations
$$(_{D{y_2}}^{D{y_1}}) + (_{{f_2}}^{{f_1}}{}_{{f_1}}^{ - {f_2}})(_{{y_2}}^{{y_1}}) = (_{{g_2}}^{{g_1}})$$
has a solution in K × K, and to find one if there are some. It turns out that (8.1) is not really a second order equation, but the coupled system for the real and imaginary parts of a Risch differential equation. Indeed, suppose that (y 1, y 2) ∈ K × K is a solution of the slightly more general system
$$(_{D{y_2}}^{D{y_1}}) + (_{{f_2}}^{{f_1}}{}_{{f_1}}^{a{f_2}})(_{{y_2}}^{{y_1}}) = (_{{g_2}}^{{g_1}})$$
for an arbitrary a ∈ Const D (K). Then, since \(D\sqrt a = 0\) by Lemma 3.3.2, writing \(y = {y_1} + {y_2}\sqrt a \) we have
$$\begin{gathered} Dy + \left( {f_1 + f_2 \sqrt a } \right)y = Dy_1 + D\left( {y_2 } \right)\sqrt a + \left( {f_1 + f_2 \sqrt a } \right)\left( {y_1 + y_2 \sqrt a } \right) \hfill \\ = Dy_1 + f_1 y_1 + af_2 y_2 + \left( {Dy_2 + f_2 y_1 + f_1 y_2 } \right)\sqrt a \hfill \\ = g_1 + g_2 \sqrt a \hfill \\ \end{gathered} $$
which implies that y is a solution in \(K\sqrt a \) of the Risch differential equation
$$Dy + ({f_1} + {f_2}\left){\vphantom{1a}}\right. \!\!\!\!\overline{\,\,\,\vphantom 1{a}})y = {g_1} + {g_2}\sqrt a $$
Manuel Bronstein

9. Structure Theorems

We present in this chapter proofs of the various structure theorems that were used in Chap. 7 for solving the parametric logarithmic derivative problem. Although they are used in the integration algorithm, the main application of structure theorems is to determine algebraic dependencies between functions.
Manuel Bronstein


Weitere Informationen