Does there exist a complete implementation of the Risch algorithm?

[dataflow]

Anybody know why there doesn't exist a complete implementation? What makes the hardest portions so difficult to implement compared to the rest?

[userbinator]

https://en.wikipedia.org/wiki/Risch_algorithm#Decidability seems to be the most difficult part; and it is unusual in that the Wikipedia article itself doesn't seem to clearly link to the original description of the algorithm.

[irrep]

Manuel Bronstein wrote a book [1] about symbolic integration, but unfortunately it only covers the transcendental part. There is also a shorter "tutorial" from some workshop [2].

[1] Manuel Bronstein: Symbolic Integration I, https://doi.org/10.1007/b138171

[2] https://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/...

[slavapestov]

Sadly he passed away before completing Part 2. https://lists.gnu.org/archive/html/axiom-developer/2005-06/m...

[1letterunixname]

I wonder how Giac measures up as it's reportedly more general than HP48's Erable.

https://en.wikipedia.org/wiki/Xcas#Giac

PS: The HP 48 could also be used a very long distance remote to turn on and off all of the TVs in a lecture hall simultaneously. :)

[murkle]

Why not try the WebAssembly version? https://www-fourier.ujf-grenoble.fr/~parisse/xcasen.html

[downvotetruth]

https://news.ycombinator.com/item?id=589004

https://news.ycombinator.com/item?id=19291578

Not sure of a connection between the failure of the high school axiom set / nonfiniteness of axioms and Rubi/rule based integration feasiblility or validity of Schanuel's conjecture.

[tehsauce]

Does this count?

https://github.com/sympy/sympy/blob/master/sympy/integrals/r...

[owalt]

This does not – according to what I can see from the code and comments – implement the case of algebraic extensions. As someone only really familiar with the implementation of the transcendental case[1], my understanding is that the algebraic case is where the major difficulty lies.

[1]: Manuel Bronstein, Symbolic Integration I. Online: https://archive.org/details/springer_10.1007-978-3-662-03386...

[irrep]

Unfortunately this is not complete, because it does not work with integrals that require algebraic extensions (they are more complicated than transcendental extensions).

[Havoc]

No idea, but I am impressed by the clarity and preciseness of the question

[jjtheblunt]

I'd check Mathematica or Macaulay2...but how would you verify an implementation is complete?

[irrep]

Mathematica does not have a complete implementation of the Risch algorithm. It actually cannot do the integral in the mathoverflow question.

Macaulay2 has a focus on commutative algebra and algebraic geometry and doesn't have an implementation of the Risch algorithm either.

[jychang]

It's written in the mathoverflow question, did you read it?

> 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: ∫29x2+18x−3x6+4x5+6x4−12x3+33x2−16x−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√dx Schultz explicitly provides an elementary antiderivative in his paper, but Maple 2018 returns the integral unevaluated.

[38]

why dont any of the users has scores by their name?

[vient]

On reloading scores are shown for a split second, interesting. Turning off ad blocker does not help, seems to be some JS inside the page.

Edit: looks like MO added an option to hide rep which is turned on by default. You can find it in achievements menu at the upper right angle.