34
$\begingroup$

Is there a generally available (commercial or not) complete implementation of the Risch algorithm for determining whether an elementary function has an elementary antiderivative?

The Wikipedia article on symbolic integration claims that the general case of the Risch algorithm was solved and implemented in Axiom by Manuel Bronstein, and an answer to another MO question says the same thing. However, I have some doubts, based on the following comment by Manuel Bronstein himself on the USENET newsgroup sci.math.symbolic on September 5, 2003:

If Axiom returns an unevaluated integral, then it has proven that no elementary antiderivative exists. There are however some cases where Axiom can return an error message saying that you've hit an unimplemented branch of the algorithm, in which case it cannot conclude. So Richard was right in pointing out that the Risch algorithm is not fully implemented there either. Axiom is unique in making the difference between unimplemented branches and proofs of non-integrability, and also in actually proving the algebraic independence of the building blocks of the integrand before concluding nonintegrability (others typically assume this independence after performing some heuristic dependence checking).

Bronstein unfortunately passed away on June 6, 2005. It is possible that he completed the implementation before he died, but I haven't been able to confirm that. I do know that Bronstein never managed to finish his intended book on the integration of algebraic functions. [EDIT: As a further check, I emailed Barry Trager. He confirmed that the implementation that he and Bronstein worked on was not complete. He did not know much about other implementations but was not aware of any complete implementations.]

I have access to Maple 2018, and it doesn't seem to have a complete implementation either. A useful test case is the following integral, taken from the (apparently unpublished) paper Trager's algorithm for the integration of algebraic functions revisited by Daniel Schultz: $$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz explicitly provides an elementary antiderivative in his paper, but Maple 2018 returns the integral unevaluated.

$\endgroup$
  • 3
    $\begingroup$ I thought Risch's algorithm was contigent on having the ability to perform zero-testing that isn't quite algorithmically justified? $\endgroup$ – Andrej Bauer Oct 15 at 6:51
  • 5
    $\begingroup$ @AndrejBauer : It does assume that zero-recognition can be performed in the underlying field of constants. But if your initial expression involves only algebraic numbers (satisfying known polynomial equations with integer coefficients) then there is an algorithm for zero-recognition, that is conjectural only in the sense that the guarantee that it terminates depends on Schanuel's conjecture. When the algorithm terminates, it gives the right answer, and since Schanuel's conjecture is surely true, the algorithm will always terminate. See Richardson's paper on the elementary constant problem. $\endgroup$ – Timothy Chow Oct 15 at 12:13
  • 3
    $\begingroup$ Bottom line is, zero-recognition of constants isn't the sticking point in practice. I'd be happy to see an implementation whose only "gap" is zero-recognition of constants (and of course the constraints imposed by finite time and memory). $\endgroup$ – Timothy Chow Oct 15 at 12:17
  • 1
    $\begingroup$ Landau required students who wanted to study with him to be able to compute every indefinite integral that can be computed in elementary functions. Perhaps his students had the Risch code built into their synapses. $\endgroup$ – Ben McKay Oct 17 at 18:24
  • 1
    $\begingroup$ @MichaelBächtold : I could be missing some subtlety but I think that's right. Just now I took a quick look at Risch's original paper and it seems to me that the base case of the induction requires only zero-recognition of constants. $\endgroup$ – Timothy Chow Oct 19 at 13:37
18
$\begingroup$

No computer algebra system implements a complete decision process for the integration of mixed transcendental and algebraic functions.

The integral from the excellent paper of Schultz may be solved by Maple if you convert the integrand to RootOf notation (Why this is not done internally in Maple is an interesting question?)

int(convert((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),RootOf),x);

My experiments suggest Maple has the best implementation of the Risch-Trager-Bronstein algorithm for the integration of purely algebraic integrals in terms of elementary functions (ref: table 1, section 3 of Sam Blake, A Simple Method for Computing Some Pseudo-Elliptic Integrals in Terms of Elementary Functions, arXiv:2004.04910). However, Maple's implementation does not integrate expressions containing parameters or nested radicals (both of which has some support in AXIOM and FriCAS).

It would seem that some significant progress has been made in computing the logarithmic part of a mixed transcendental-algebraic integral by Miller [1]. Though, as far as I know, no computer algebra system has implemented his algorithm. It is also not clear if Miller's algorithm can deal with parameters, for example, the Risch-Trager-Bronstein algorithm has difficulties with the following pseudo-elliptic integral

$$\int\frac{\left(p x^2-q\right) \left(p x^2-x+q\right)dx}{x \left(p x^2+2 x+q\right) \sqrt{2 p^2x^4+2 p x^3+(4 p q+1) x^2+2 q x+2 q^2}} = - \frac{1}{\sqrt{2}}\log (x) + \frac{1}{\sqrt{2}}\log \left(\sqrt{2} y +2 p x^2+x+2q\right) - \frac{3}{\sqrt{5}}\tanh ^{-1}\left(\frac{\sqrt{5} y}{3 p x^2+3 q+x}\right),$$ where $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. My heuristic in the previously-linked paper computes this integral quickly with the substitution $u=\frac{px^2+q}{p x}$.

In regards to the mixed algebraic-transcendental case of the Risch-Trager-Bronstein algorithm, an integral which cannot be solved with Maple, Mathematica, AXIOM or FriCAS (and possibly other CAS) is

$$\int \frac{\left(\sqrt{x}+1\right) \left(e^{2x \sqrt{x}} -a\right) \sqrt{a^2+2 a x e^{2 \sqrt{x}} +cx e^{2 \sqrt{x}} +x^2 e^{4 \sqrt{x}}}}{x \sqrt{x}e^{\sqrt{x}} \left(a+x e^{2 \sqrt{x}} \right)} dx.$$

This integral is interesting as it returns two distinct messages from AXIOM and FriCAS suggesting their respective implementations are incomplete. FriCAS returns

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:                                                               
   integrate: implementation incomplete (has polynomial part)                                                                                                                                                

While AXIOM returns

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:
   integrate: implementation incomplete (constant residues)                                                                                                                                             

[1] Miller, B. (2012). “On the Integration of Elementary Functions: Computing the Logarithmic Part”. Thesis (Ph.D.) Texas Tech University, Dept. of Mathematics and Statistics.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ actually, fricas does this integral in a second $\endgroup$ – Martin Rubey Oct 15 at 12:42
  • 1
    $\begingroup$ @MartinRubey, I didn't mean to imply that AXIOM and/or FriCAS could not compute this integral. Here's an example which Maple and AXIOM can compute and FriCAS claims is not elementary: int(convert(((-1+3*x^4)*(1+x+2*x^4+x^5+x^8)^(1/2))/(x^2*(4+x+4*x^4)),RootOf),x); $\endgroup$ – Sam Blake Oct 16 at 0:51
  • 1
    $\begingroup$ To be fair, here's one which may be computed with FriCAS and AXIOM, but returns an error in Maple: int(convert((x^3+1)*(x^6-x^3-2)^(1/2)/x^4/(x^6-2*x^3-1),RootOf),x); $\endgroup$ – Sam Blake Oct 16 at 1:02
  • 2
    $\begingroup$ I cannot verify you claim that fricas returns the integral above unevaluated. I get: ${-{x \ {\log \left( {{{-{2 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+{2 \ {{x} ^ {4}}}+x+1}}}}+{2 \ {{x} ^ {4}}}+x+2} \over x}} \right)}} -{x \ {\sqrt {3}} \ {\arctan \left( {{{{\left( {2 \ {{x} ^ {4}}} -x+2 \right)} \ {\sqrt {3}}} \over {6 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+{2 \ {{x} ^ {4}}}+x+1}}}}}} \right)}}+{4 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+{2 \ {{ x} ^ {4}}}+x+1}}}}} \over {{16} \ x} $ within a second, at least with the current version from git. $\endgroup$ – Martin Rubey Oct 16 at 9:15
  • 2
    $\begingroup$ Extremely informative response...thanks! I am wondering if there is some kind of "roadmap" that delineates the main challenges that stand in the way of a complete implementation. The Fricas "Risch Implementation Status" page mentioned by Dima Pasechnik is a start but is vague about some important details. If there were a clearly mapped-out plan of attack, perhaps it would attract more researchers to the area, and the challenges could be knocked off one by one. $\endgroup$ – Timothy Chow Oct 16 at 14:39
12
$\begingroup$

Fricas, an open-source clone of Axiom, implements a considerable chunk of Risch, see http://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus

Fricas is also available as a optional package of SageMath open-source system.

Edit: here how it goes in SageMath with Fricas as backend.


sage: r=integrate((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),x,algorithm="fricas")                                                                                                                                     
sage: r                                                                                                                                                                                                                                
log(x^29 + 40*x^28 + 776*x^27 + 9648*x^26 + 85820*x^25 + 578480*x^24 + 3058536*x^23 + 12979632*x^22 + 45004902*x^21 + 129708992*x^20 + 317208072*x^19 + 675607056*x^18 + 1288213884*x^17 + 2238714832*x^16 + 3548250712*x^15 + 5097069328*x^14 + 6677210721*x^13 + 8106250392*x^12 + 9056612528*x^11 + 8991685504*x^10 + 7944578304*x^9 + 6614046720*x^8 + 4834279424*x^7 + 2374631424*x^6 + 916848640*x^5 + 638582784*x^4 - 279969792*x^3 - 528482304*x^2 + (x^26 + 38*x^25 + 699*x^24 + 8220*x^23 + 68953*x^22 + 436794*x^21 + 2161755*x^20 + 8550024*x^19 + 27506475*x^18 + 73265978*x^17 + 165196041*x^16 + 324386076*x^15 + 570906027*x^14 + 914354726*x^13 + 1326830817*x^12 + 1731692416*x^11 + 2055647184*x^10 + 2257532160*x^9 + 2246693120*x^8 + 1939619840*x^7 + 1494073344*x^6 + 1097859072*x^5 + 640024576*x^4 + 207618048*x^3 + 95420416*x^2 + 50331648*x - 50331648)*sqrt(x^6 + 4*x^5 + 6*x^4 - 12*x^3 + 33*x^2 - 16*x) + 150994944*x - 134217728)
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.