Computer Algebra and Integration

Wm C Bauldry Dept of Mathematical Sciences Appalachian State University wmcb@math.appstate.edu

November 10, 1997 Questions

• How does computer algebra affect the learning of integration?

• What techniques are still important?

• Which other methods are unnecessary in firstyear instruction?

Patterns, I. Consider the four integrals:

∫ \frac{1}{1 + x^{2}} = arctan (x)

∫ cos (x) = sin (x)

∫ \frac{1}{√1 − x^{2}} = arcsin (x)

∫ arccosh (x) = x arccosh (x) − √x^{2} − 1

(from Geddes, Szapor, and Labahn Algorithms for Computer Algebra)

Patterns, II. The four integrals represented with logarithms and exponentials:

∫ \frac{1}{1 + x^{2}} = \frac{1}{2} (log (x + ı) − log (x − ı)) · ı

\begin{aligned}∫ cos (x) & = & \frac{1}{2} ∫ (e^{ıx} + e^{−ıx}) \\ & = & \frac{ı}{2} (−e^{ıx} + e^{−ıx}) \end{aligned}

∫ \frac{1}{√1 − x^{2}} = −ı log (ıx + √1 − x^{2} )

∫ arccosh (x) = ∫ log (x + √x^{2} − 1 )
= x log (x + √x^{2} − 1 ) − √x^{2} − 1

The Integration Problem Given two class of functions, F and G, find an algorithm that, for every f ∈ F, presents a g ∈ G such that g′ = f or proves no such g exists.

Definitions

Algebraic: θ is algebraic over K if θ satifies a polynomial with coefficients from K.

Logarithmic: θ is logarithmic over K if there is a λ ∈ K such that θ′λ = λ′.

Exponential: θ is exponential over K if there is a η ∈ K such that θ′ = η′θ.

I. Liouville – 1832

Integration in Finite Terms – Liouville’s Principle Let f be from a function field K. If f has an elementary integral over K, then it is of the form

∫ f = v_{0} + ∑ c_{i} log (v_{i})

where v_{0} ∈ K, v_{i} ∈ K^{∗}, a finite algebraic extension of K, and the constants c_{i} ∈ K^{∗}.

II. Hermite – 1872 Rational Functions – Algorithm (Partial Fractions)

III. Risch – 1968

Logarithmic and Exponential Extension Fields – Extended Algorithm Add finitely many transcendental extensions, then decompose the integral as in Hermite’s method

IV. Davenport/Bronstein – 1988/1992

Transcendental/Algebraic Extension – Extends Risch’s Algorithm Liouville’s Principle – 1832 Let f be from a function field K. If f has an elementary integral over K, then it is of the form

∫ f = v_{0} + ∑ c_{i} log (v_{i})

where v_{0} ∈ K, v_{i} ∈ K^{∗}, a finite algebraic extension of K, and the constants c_{i} ∈ K^{∗}.

Risch’s Theorem – 1968 Let C be a field of constants. Let K = C(x, θ_{1}, …, θ_{n}) be a field of functions with θ_{i} being either an exponential or a logarithm of an element in C(x, θ_{1}, …, θ_{i−1}) for i = 1..n and, hence, C(x, θ_{1}, …, θ_{i}) is a transcendental extension of C(x, θ_{1}, …, θ_{i−1}). The field of constants of K is C. Then there is an algorithm that, for f ∈ K, either gives an elementary function g over K such that ∫ f = g or proves that f has no elementary integral over K.

Davenport’s Extension – 1988 Replace C(x, θ_{1}, …, θ_{n}) with C(x, y, θ_{1}, …, θ_{n}) where y is algebraic over C(x).

Example

Consider ∫ e^{x^{2}}.

If ∫ e^{x^{2}} has an elementary integral, then, by Liouville’s Principle, the integral must have the form

∫ e^{x^{2}} = R(x) · e^{x^{2}}

where R = N/D is rational and has gcd (N, D) = 1. Differentiate both sides:

e^{x^{2}} = R′ · e^{x^{2}} + 2xR · e^{x^{2}}

So

1 = R′ + 2xR
D^{2} = N′D − D′N + 2xND

Rearrange to obtain D ·(D −N′ −2xN) = −D′N. A simple argument based on roots of D shows no such R exists. Therefore ∫ e^{x^{2}} has no elementary integral.

Hermite’s Method I. Square-Free Factorization

\frac{p}{q} = \frac{p}{n ; ∏ ; i=1 q_{i}^{i}} = n ; ∑ ; i=1 \frac{p_{i}}{q_{i}^{i}}, deg (p_{i}) ≤ i − 1

II. Exponent Reduction

∫ \frac{p_{i}}{q_{i}^{i}} = ∫ \frac{p_{i} · (aq_{i} + bq′_{i})}{q_{i}^{i}}
= ∫ \frac{p_{i}a}{q_{i}^{i−1}} + ∫ \frac{p_{i}bq′_{i}}{q_{i}^{i}}
= −\frac{p_{i}b/(i − 1)}{q_{i}^{i−1}} + ∫ \frac{p_{i}a + (p_{i}b)′/(i − 1)}{q_{i}^{i−1}}

III. Synthesis

∫ \frac{p}{q} = n ; ∑ ; i=1 (c_{i,0} log (q_{i}) + i−1 ; ∑ ; i=1 \frac{c_{i,j}}{q_{i}^{j}} )

Horowitz’ Method I. Separate Logarithmic Integral

∫ \frac{q}{r} = \frac{q_{1}}{r_{1}} + ∫ \frac{q_{2}}{r_{2}}
= \frac{q_{1}}{r_{1}} + j ; ∑ ; k=1 c_{k} log (r_{2,k})

II. Logarithmic Sum Denominator

r_{2} = r/ gcd (r, r′)

Trager / Rothstein Improvement I. Logarithmic Part Suppose that ∫ \frac{p}{q} = n ; ∑ ; k=1 c_{k} log (v_{k}). Then

c_{k} ∈ RootOf{Res_{x}(p − y q′, q)}

and

v_{k} = gcd (p − c_{k} q′, q)

References

1. A. Akritas, Elements of Computer Algebra with Applications, Wiley, New York, 1989.

2. M. Bronstein, “The transcendental Risch differential equation,” J. Symbolic Comp, 9, 1990, 49–60.

3. J. Calmet, Computer Algebra; EUROCAM ’82, Springer-Verlag, New York, 1982.

4. K. Geddes, S. Czapor, and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Pub., 1992.

5. G. Hardy, The Integration of Functions of a Single Variable, Hafner, New York, 1971.

6. A. Heck, Introduction to Maple, 2nd ed., Springer, New York, 1996.

7. E. Hermite, “Sur l’integration des fractions rationelles,” N. Ann. de Math., 1872, 145–148.

8. E. Horowitz, “Algorithms for partial fraction decomposition and rational function integration,” in Proc. Second Symp. Sym. and Alg. Manip., ACM Press, 1971, 441–457.

9. R. Jenks and R. Sutor, AXIOM: The Scientific Computation System, Springer-Verlag, New York, 1992.

References

10. A. Ostrowski, “Sur l’intégrabitité élémentaire de quelques classes d’expressions,” Comm. Math. Helvetica 18, 1946, 283–308.

11. D. Richardson, “Some unsolvable problems involving elementary functions of a real variable,” J. Symbolic Logic 33, 1968, 511–520.

12. H. Risch, “The problem of integration in finite terms,” Trans. AMS 139, 167–189.

13. M. Rothstein, Aspects of Symbolic Integration and Simplification of Exponential amd Primitive Functions, Ph.D. Thesis, U of Wisc., Madison, 1976.

14. M. Rosenlicht, “Integration in finite terms,” Am. Math. Monthly 79, 1972, 963–971.

15. B. Trager, “Algebraic Factoring and Rational Function Integration,” in Proc. SYMSAC ’76, ACM Press, 1976, 219– 226.

16. D. Zerwilleger, Handbook of Integration, Jones and Bartlett Pub., Boston, 1992.