Re: [Axiom-math] Axiom's integration non-deterministic?

[Igor Khavkine]

On 3/26/06, William Sit <address@hidden> wrote:

> So it seems that because the integrand is algebraic over Q(x), Axiom
> tries to find a primitive element of the algebraic extension which
> contains the integrand. But a primitive elment is not unique, and
> there might be some randomness in selecting this primitive element
> (which involving building a tower of algebraic extensions to
> successively remove the radicals appearing in the integrand, and so
> there could be some choice of order that is not deterministic or some
> factoring algorithm involved in getting to the minimal polynomials at
> each stage, with a different integral also at each stage). Tracing
> primitiveElement:
>
> )trace FSPRMELT )math

If you also add

)trace PRIMELT )math

you'll see that that William is basically correct. The primitiveElement
routing from PRIMELT gets called with a 4-argument signature and returns
different answers with the same input. Looking at the source
(algebra/primelt.spad.pamphlet) there is in deed a call to
random()$Integer in that routine. If you run the following command a few
times, it will return different results.

primitiveElement(x^(1/3),sqrt(1+x^(2/3)))

BTW, what exactly does this routine do? The documentation is rather
terse and the only mention of "primitive element" in my copy of Geddes
et al. doesn't seem relevant.

So, I guess, the answer to my original question is Yes, Axiom's
integration routine for algebraic functions is non-deterministic. That's
not really a problem, since it seems to return the correct answer but in
different forms. But I am surprized that there doesn't seem to be a
canonical form for algebraic expressions. It may be that I was expecting
too much. However, looking at the last chapter of Geddes et al., there
is a discussion of a canonical form for algebraic functions as they are
fed into the Risch integrator. It doesn't look like any of the
"normalize" routines that I found in Axiom actually perform this trick.
Is this step actually taken or bypassed in the integration code?

Igor