       Re: If Integrate returns no result, can we conclude that no closed-form

• To: mathgroup at smc.vnet.net
• Subject: [mg87793] Re: [mg87759] If Integrate returns no result, can we conclude that no closed-form
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Wed, 16 Apr 2008 22:35:07 -0400 (EDT)
• References: <200804161052.GAA29333@smc.vnet.net>

```You are right that all computer algebra systems that perform
indefinite integration use the Risch algorithm (arguably misnamed
since Risch's original work in 1968 dealt chiefly with the easier part
of the algorithm, and others such as Liouville, Hermite, Hardy and
Ritt earlier and Davenport, Trager and others later, contributed at
least as much).

A completely implemented Risch algorithm will either return an
explicit answer for an integral that can be evaluated in terms of
elementary functions or determine that no such answer can be given.

The Risch algorithm consists of two parts. The first deals with so
called "transcendental elementary functions". This is the easy part
and is very similar to the Hermite's method of integrating arbitrary
rational functions (a part of which is taught in calculus courses).
However, the second part, which deals with algebraic functions is much
harder and uses some quite advanced computational algebraic geometry.

As far as there is no complete implementation of the Risch algorithm
in any CAS. Anyway, this was sure about 10 years ago and I doubt that
anything has changed since then (but would not stake my life on that).
The problem lies, of course, with the part involving computational
algebraic geometry. Algorithms in computational algebraic geometry are
often  very hard to implement (and the number of people who understand
them and can program at the professional level and also have the time
that would be needed for this is surely rather limited). As a result I
believe there are certain "branches" of the Risch algorithm where some
kind of "heuristics" are used instead of the algorithm itself.

I have no idea will happen if the Mathematica implementation gets into
one of such branches. One possibility,of course, it that the heuristic
method will work anyway and you will get an answer (possible a wrong
one;-)). Or the thing may just run for ever. I doubt that it will just
admit defeat and return the integral unevaluated. I think it is fairly
safe to assume that if an indefinite integral is returned unevaluated
than it can't be integrated in terms of elementary functions. But
this, of course, is only mere speculation.

Andrzej Kozlowski

On 16 Apr 2008, at 19:52, Szabolcs Horv=E1t wrote:
>
> The documentation says:
>
> "In the most convenient cases, integrals can be done purely in terms
> of
> elementary functions such as exponentials, logarithms and
> trigonometric
> functions. In fact, if you give an integrand that involves only such
> elementary functions, then one of the important capabilities of
> Integrate is that if the corresponding integral can be expressed in
> terms of elementary functions, then Integrate will essentially always
> succeed in finding it."
>
> http://reference.wolfram.com/mathematica/tutorial/IntegralsThatCanAndCannotBeDone.html
>
> How precise is this?  Can one rely on this information?  Is it really
> true that if Mathematica cannot integrate an expression made up of
> elementary functions, then no closed-form result exists?
>
> Szabolcs
>
> (P.S. I do not know how Integrate works.  I heard that CASs use a
> so-called "Risch-alogrithm", but there is relatively little
> information