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](https://en.wikipedia.org/wiki/Symbolic_integration#Discussion) 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](https://mathoverflow.net/revisions/171979/1) says the same thing. However, I have some doubts, based on the following [comment by Manuel Bronstein himself](https://groups.google.com/d/msg/sci.math.symbolic/YXlaU8WA2JI/1w1MxrSpm6IJ) 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](https://web.archive.org/web/20090709152940/http://www.ccas.ru/sabramov/ps/PCS56.pdf). 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](https://sites.psu.edu/dpsmath/files/2016/12/IntegrationOnCurves-2hhuby8.pdf) 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.



Does there exist a complete implementation of the Risch algorithm?
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](https://arxiv.org/abs/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](https://arxiv.org/abs/2004.04910.pdf) 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](http://hdl.handle.net/2346/45299)”. Thesis (Ph.D.) Texas Tech University, Dept. of Mathematics and Statistics.


