Does there exist a complete implementation of the Risch algorithm? | Hacker News Reader

Does there exist a complete implementation of the Risch algorithm?

mathoverflow.net

154 pointsthechao22 comments

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

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.

The comments underneath the post explain that zero-testing isn't the issue: https://mathoverflow.net/questions/374089/does-there-exist-a...

Still a bit puzzled by it.

It's no surprise that the algorithm is incomplete, if some of its subtasks are still open problems in math. (And therefore it has to resort to imperfect heuristics or try and detect classes of inputs for which no results can be generated)

However, the OP and links sound as if even just implementing the existing algorithm spec is so insanely hard that no one has managed to do so yet for the entirety of it.

It'd be interested to know what exactly makes it so hard.

Wikipedia doesn't link to the actual spec unfortunately, though they do mention that the spec is something like 100 pages in size. Maybe that's a hint of the amount of complexity that is involved...

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/...

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

I wonder if someone will make a publication out of his incomplete manuscripts. How many years do this kind of work take in the field of mathematics? Marx's Capital Volume IV took 20 years from his death to Kautsky's publication.

I wrote a program to do symbolic integration as my undergrad project around 2010. I had (still have) Bronstein's book which I had pored over for the best part of a year. I had also visited his website[0] and found tons of useful info there. You know when you read so much of and about a person you almost feel like you know them?

It wasn't until right at the end of the project I happened across an obituary[1]. He'd been dead the whole time. It was a very strange feeling. Like I had been in communication with a ghost.

It's such a shame as I feel like he probably would have finished the Risch algorithm eventually.

[0] https://www-sop.inria.fr/cafe/Manuel.Bronstein/ [1] http://www.ccas.ru/sabramov/ps/PCS56.pdf

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. :)

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

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.

Does this count?

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

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

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...

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

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

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.

The question at hand is "how do you verify that an implementation is complete?", not "what is one test case whose failure would demonstrate that an implementation is incomplete?"

Yes, I read it.

What you responded does not address what i asked.

For example, you could have an implementation that handles the example you cited, but fails at others you did not mention. So would your comment claim "complete" for handling what you mentioned, when it is not?

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.

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

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.

Reply on news.ycombinator.com