[Axiom-developer] Axiom' integrator (was: Axiom Volume 1: Tutorial)

[Bill Page]

Martin,

On January 3, 2006 6:49 AM you wrote:
>...
>   "... Axiom's integrator gives you the answer when an answer
>   exists. If one does not, it provides a proof that there is
>   no answer."
>
> on page 2 is simply wrong. (Apart from containing a typo).

Rather than just state that there is a typo: please, please
state exactly the error and the correction. Or better yet
include a 'diff -au' patch to correct the error.

> Even if read as
>
>   ... Axiom's integrator gives you the answer when an answer
>   in terms of elementary functions exists. If one does not,
>   it provides a proof that there is no answer.
>
> it is not true. The Risch algorithm is *not* completely
> implemented in Axiom, unfortunately.

If, we can finish the implementation of this algorithm in Axiom,
then would your re-worded statement above be correct?

Of course we are really talking about "anti-derivatives", not
integration as such. Manuel Bronstein has written extensively
about this:

http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.pdf
http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications

So what "elementary functions" are being considered by Axiom's
algorithm? E.g. addition, division, exponents, logarithms,
multiplication, polynomials, radicals, rationals, subtraction,
and trigonometric expressions such as suggested here:

Eric W. Weisstein. "Elementary Function." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/ElementaryFunction.html

Or should we be talking about "closed forms" as in the reference:

http://arxiv.org/abs/math.NT/9805045?front

Date: Fri, 8 May 1998 22:49:15 GMT   (12kb)

What is a closed-form number?
Authors: Timothy Y. Chow
Comments: 11 pages; submitted to Amer. Math. Monthly

If a student asks for an antiderivative of exp(x^2), there is a
standard reply: the answer is not an elementary function. But if
a student asks for a closed-form expression for the real root of
x = cos(x), there is no standard reply. We propose a definition
of a closed-form expression for a number (as opposed to a *function*)
that we hope will become standard. With our definition, the question
of whether the root of x = cos(x) has a closed form is, perhaps
surprisingly, still open. We show that Schanuel's conjecture in
transcendental number theory resolves questions like this, and we
also sketch some connections with Tarski's problem of the decidability
of the first-order theory of the reals with exponentiation. Many
(hopefully accessible) open problems are described. 

--------

Or some other definition such as:

http://en.wikipedia.org/wiki/List_of_functions#Elementary_functions

> It might be more complete than the ones in MMA and Maple, I doubt
> that it's better than MuPAD, but boasting that it is complete is
> unwise, I'm afraid.

Since it was obviously the intention of the author of Axiom's
integration algorithm that it completely implement the Risch
algorithm and in spite of:

http://mathworld.wolfram.com/RischAlgorithm.html

"The case of algebraic extensions is quite complicated and is
therefore not completely implemented in any computer algebra
system."

http://en.wikipedia.org/wiki/Risch_algorithm

"The Risch decision procedure is not formally an algorithm because
it requires an oracle that decides whether a constant expression
is zero, a problem shown by Daniel Richardson to be undecidable.
Transforming the Risch decision procedure into an algorithm that
can be executed by a computer is a complex task that requires the
use of heuristics and many refinements."

-------

What are the prospects for actually completing this programme in
Axiom rather than "correcting" the documentation? So far we have
documented the following cases:

http://wiki.axiom-developer.org/198IntegrateSinX2XIsNotHandled

http://wiki.axiom-developer.org/199IntegrateExpX2ExpXXX

and the Risch algorithm is mentioned in the following places in
the current Axiom source:

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/EfstrucSpad
http://wiki.axiom-developer.org/axiom--test--1/src/algebra/IntafSpad
http://wiki.axiom-developer.org/axiom--test--1/src/algebra/IntefSpad
http://wiki.axiom-developer.org/axiom--test--1/src/algebra/IntrfSpad

And we also have Manuel Bronstein's work on

http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/index.html

pmint - The Poor Man's Integrator

pmint is a very short (95 lines) Maple program for integrating
transcendental elementary or special functions. It is based on recent
improvements to a powerful heuristic called parallel integration.
While it is not meant to be as complete as the large commercial
integrators based on the Risch algorithm, its very small size makes
it easy to port to any computer algebra system or library capable of
factoring multivariate polynomials. Because it is applicable to special
functions (such as Airy, Bessel, Whittaker, Lambert), it is able to
compute integrals not handled by the existing integrators.

pmint is not meant as a replacement for existing integrators, but either
as an extension, or as a cheap and powerful alternative for any computer
algebra project. 

-------

It would be wonderful to have this available in Axiom.

Regards,
Bill Page.