University of Maryland, College Park
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.
Email: cosine at freesoft.org
Math Bldg Rm 0307
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.
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).
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
Bronstein, "Symbolic Integration I: Transcendental Functions", 2nd ed (2005).
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.
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.
1 week - Introduction
2-3 weeks - Algebra
Rings and fields. Polynomial long division. GCD computation.
Polynomial diophantine equations.
1-2 weeks - Algebraic structure of Risch integration
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
Berlekamp's factorization algorithm (maybe).
Algebraic extensions. Factorization in algebraic extensions (maybe).
Exponential and logarithmic extensions.
Expression of elementary functions in terms of exps and logs.
1 week - Differentiation
1 week - Integration in a differential field
Integration by factoring the denominator and partial fractions.
Integration with Rothstein/Trager resultants.
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.
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.