Risch Algorithm – Does a Complete Implementation of the Risch Algorithm Exist?

algorithmscomputer-algebradifferential-algebraintegration

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.

Best Answer

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.

Related Question