Symbolic Integration I

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.

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.

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.

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, g ∈ K, to decide whether the equation 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 y ∈ k(t). The algorithm we present in this chapter proceeds as follows:

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.

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 ₁, f ₂, g ₁, g ₂ in K, to decide whether the system of equations 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 ₁, y ₂) ∈ K × K is a solution of the slightly more general system 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 which implies that y is a solution in \(K\sqrt a \) of the Risch differential equation .

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.