Risch Integration

Spring 2006 University of Maryland, College Park

non-credit course

Abstract:

In 1968, Robert Risch, using abstract algebra, solved a centuries-old problem in mathematics - given an elementary function f(x), can its integral be written as another elementary function F(x)? Risch's technique either finds the integral or proves that it doesn't exist. Refined and improved, it has found its way into computer programs like MAXIMA, Mathematica, AXIOM, and MAPLE, to name a few. Unfortunately, calculus is still taught the "old way" - after presenting a hodgepodge of techniques (integration by parts, trigonometric substitutions, change of variables) the student is basically told, "now if you really want to solve an integral, you use a computer." This class teaches how the computer does it, not through massive approximation or exhaustively checking thousands of integrals, but in a framework that may ultimately define how computers will be used in twenty-first century mathematics - hard theorems, tight proofs, solid math.

Teacher:

Brent Baccala
Email: cosine at freesoft.org
443-618-8702 (cell)

Location:

Math Bldg Rm 0307
TuTh 3:30-4:45

Prerequisites:

Calculus II (MATH 141)

Abstract Algebra (MATH 403) helpful but not required

This class could be seen as a "Calculus II+" in the sense that it continues trying to answer the basic question of second-semester calculus - how to "do" an integral. The approach is heavily algebraic, but I'll try to introduce the needed abstract algebra concepts as we go.

References:

We have no textbook as such, partly because I know of no single text that covers all of this material. By the end of the class, we'll be into various research papers. These are my main references:

Geddes, Czapor, Labahn, "Algorithms for Computer Algebra" (1992). ISBN 0-7923-9259-0

Good book for an undergraduate audience that covers all sorts of issues like polynomial factorization, solving systems of equations, Grober bases. Only one chapter on Risch integration, unfortunately.
Bronstein, "Symbolic Integration I: Transcendental Functions", 2nd ed (2005). ISBN 3-540-21493-3
Graduate level; maybe the best book on the subject. Unfortunately, Dr. Bronstein died before completing the second volume of this work, so the algebraic case remains completely unaddressed here.
Trager, "Integration of Algebraic Functions", Ph.D. thesis (1984).
Available from M.I.T's website. A good place to pick up where Bronstein's book leaves off. Advanced.
Bronstein, "Integration of Elementary Functions", J Symbolic Computation (1990) 9, 117-173.
A published version of Bronstein's Ph.D. thesis, available at EPSL. I haven't read it (yet), but it looks like a good place to go after Trager.

Lecture Recordings:

Lectures will be conducted using a tablet computer and LCD projector to do all the math. The computer's screen and classroom audio will be recorded, converted to MPEG-4 (DivX) and posted, typically within 24 hours. All recorded material is public domain; no rights reserved; copying and redistribution freely permitted. DivX players are available from divx.com; video iPods may also be capable of playing these videos.

Links to the MPEG-4 AVI files are slotted into the (continually revised) syllabus as they become available.

Syllabus:

1 week - Introduction

Introduction to teacher, class, subject, students. Whirlwind tour of subject; no proofs; half dozen worked problems

31 Jan 2006 (192 MB)
2 Feb 2006 (197 MB)

2-3 weeks - Algebra
Rings and fields. Polynomial long division. GCD computation. Polynomial diophantine equations.
7 Feb 2006 (195 MB)
Problem Set #1
5 Mar 2006 (146 MB)
Problem Set #2
14 Mar 2006 (134 MB)

Partial fractions expansion.
27 Apr 2006 (165 MB)
Problem Set #3

Polynomial factorization. Berlekamp's factorization algorithm (maybe). Square-free/splitting factorizations. Algebraic extensions. Factorization in algebraic extensions (maybe). Resultants.

1-2 weeks - Algebraic structure of Risch integration
Exponential and logarithmic extensions. Expression of elementary functions in terms of exps and logs.
1 week - Differentiation
Differential fields.
1 week - Integration in a differential field
Liouville's theorem.
Integration by factoring the denominator and partial fractions. Integration with Rothstein/Trager resultants. Hermite reduction. Problems created by multi-valued nature of the complex logarithm. 2-3 weeks - Integration in logarithmic extensions
Rational component. Logarithmic component. Polynomial component.
3-4 weeks - Integration in exponential extensions
Risch differential equation. Order function. Splitting factorization.
3-4 weeks - Integration in algebraic extensions (Trager's method)
Integral algebraic functions. Integral bases. Computation of integral bases for polynomials algebraic extensions.
any remaining time - Integration in algebraic extensions (Bronstein's method)

Thurs May 11 - Last class

Survey of research directions in the field. Social.