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].
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.
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.
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.
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.
Unfortunately this is not complete, because it does not work with integrals that require algebraic extensions (they are more complicated than transcendental extensions).
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?"
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?
