https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm Stack Exchange Network Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Visit Stack Exchange [ ] Loading... 1. + Tour Start here for a quick overview of the site + Help Center Detailed answers to any questions you might have + Meta Discuss the workings and policies of this site + About Us Learn more about Stack Overflow the company, and our products. 2. 3. current community + MathOverflow help chat + MathOverflow Meta your communities Sign up or log in to customize your list. more stack exchange communities company blog 4. 5. Log in 6. Sign up MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up. Sign up to join this community [ano] Anybody can ask a question [ano] Anybody can answer [an] The best answers are voted up and rise to the top MathOverflow 1. Home 2. 1. Public 2. Questions 3. Tags 4. Users 5. Unanswered Does there exist a complete implementation of the Risch algorithm? Ask Question Asked 2 years, 10 months ago Modified today Viewed 13k times 56 $\begingroup$ 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. * algorithms * integration * computer-algebra * differential-algebra Share Cite Improve this question Follow edited Nov 11, 2021 at 15:38 Timothy Chow asked Oct 15, 2020 at 0:04 Timothy Chow's user avatar Timothy ChowTimothy Chow 74.6k2222 gold badges332332 silver badges539539 bronze badges $\endgroup$ 6 * 5 $\begingroup$ I thought Risch's algorithm was contigent on having the ability to perform zero-testing that isn't quite algorithmically justified? $\endgroup$ - Andrej Bauer Oct 15, 2020 at 6:51 * 9 $\begingroup$ @AndrejBauer : It does assume that zero-recognition can be performed in the underlying field of constants. But if your initial expression involves only algebraic numbers (satisfying known polynomial equations with integer coefficients) then there is an algorithm for zero-recognition, that is conjectural only in the sense that the guarantee that it terminates depends on Schanuel's conjecture. When the algorithm terminates, it gives the right answer, and since Schanuel's conjecture is surely true, the algorithm will always terminate. See Richardson's paper on the elementary constant problem. $\ endgroup$ - Timothy Chow Oct 15, 2020 at 12:13 * 3 $\begingroup$ Bottom line is, zero-recognition of constants isn't the sticking point in practice. I'd be happy to see an implementation whose only "gap" is zero-recognition of constants (and of course the constraints imposed by finite time and memory). $\endgroup$ - Timothy Chow Oct 15, 2020 at 12:17 * 1 $\begingroup$ Landau required students who wanted to study with him to be able to compute every indefinite integral that can be computed in elementary functions. Perhaps his students had the Risch code built into their synapses. $\endgroup$ - Ben McKay Oct 17, 2020 at 18:24 * 2 $\begingroup$ @MichaelBachtold : I could be missing some subtlety but I think that's right. Just now I took a quick look at Risch's original paper and it seems to me that the base case of the induction requires only zero-recognition of constants. $\ endgroup$ - Timothy Chow Oct 19, 2020 at 13:37 | Show 1 more comment 3 Answers 3 Sorted by: Reset to default [Highest score (default) ] 37 $\begingroup$ 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. Share Cite Improve this answer Follow edited Oct 18, 2020 at 11:21 David Roberts's user avatar David Roberts 32.6k99 gold badges110110 silver badges308308 bronze badges answered Oct 15, 2020 at 1:43 Sam Blake's user avatar Sam BlakeSam Blake 48644 silver badges44 bronze badges $\endgroup$ 13 * 1 $\begingroup$ actually, fricas does this integral in a second $\ endgroup$ - Martin Rubey Oct 15, 2020 at 12:42 * 1 $\begingroup$ @MartinRubey, I didn't mean to imply that AXIOM and /or FriCAS could not compute this integral. Here's an example which Maple and AXIOM can compute and FriCAS claims is not elementary: int(convert(((-1+3*x^4)*(1+x+2*x^4+x^5+x^8)^(1/2))/(x ^2*(4+x+4*x^4)),RootOf),x); $\endgroup$ - Sam Blake Oct 16, 2020 at 0:51 * 1 $\begingroup$ To be fair, here's one which may be computed with FriCAS and AXIOM, but returns an error in Maple: int(convert((x^ 3+1)*(x^6-x^3-2)^(1/2)/x^4/(x^6-2*x^3-1),RootOf),x); $\endgroup$ - Sam Blake Oct 16, 2020 at 1:02 * 2 $\begingroup$ I cannot verify you claim that fricas returns the integral above unevaluated. I get: ${-{x \ {\log \left( {{{-{2 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+{2 \ {{x} ^ {4}}}+x+1}}}}+{2 \ {{x} ^ {4}}}+x+2} \over x}} \right)}} -{x \ {\sqrt {3}} \ {\ arctan \left( {{{{\left( {2 \ {{x} ^ {4}}} -x+2 \right)} \ {\sqrt {3}}} \over {6 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+{2 \ {{x} ^ {4}}}+x+1}}}}}} \right)}}+{4 \ {\sqrt {{{{x} ^ {8}}+{{x} ^ {5}}+ {2 \ {{ x} ^ {4}}}+x+1}}}}} \over {{16} \ x} $ within a second, at least with the current version from git. $\endgroup$ - Martin Rubey Oct 16, 2020 at 9:15 * 3 $\begingroup$ Extremely informative response...thanks! I am wondering if there is some kind of "roadmap" that delineates the main challenges that stand in the way of a complete implementation. The Fricas "Risch Implementation Status" page mentioned by Dima Pasechnik is a start but is vague about some important details. If there were a clearly mapped-out plan of attack, perhaps it would attract more researchers to the area, and the challenges could be knocked off one by one. $\endgroup$ - Timothy Chow Oct 16, 2020 at 14:39 | Show 8 more comments 21 $\begingroup$ Fricas, an open-source clone of Axiom, implements a considerable chunk of Risch, see http://fricas-wiki.math.uni.wroc.pl/ RischImplementationStatus Fricas is also available as a optional package of SageMath open-source system. Edit: here how it goes in SageMath with Fricas as backend. --------------------------------------------------------------------- sage: r=integrate((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),x,algorithm="fricas") sage: r log(x^29 + 40*x^28 + 776*x^27 + 9648*x^26 + 85820*x^25 + 578480*x^24 + 3058536*x^23 + 12979632*x^22 + 45004902*x^21 + 129708992*x^20 + 317208072*x^19 + 675607056*x^18 + 1288213884*x^17 + 2238714832*x^16 + 3548250712*x^15 + 5097069328*x^14 + 6677210721*x^13 + 8106250392*x^12 + 9056612528*x^11 + 8991685504*x^10 + 7944578304*x^9 + 6614046720*x^8 + 4834279424*x^7 + 2374631424*x^6 + 916848640*x^5 + 638582784*x^4 - 279969792*x^3 - 528482304*x^2 + (x^26 + 38*x^25 + 699*x^24 + 8220*x^23 + 68953*x^22 + 436794*x^21 + 2161755*x^20 + 8550024*x^19 + 27506475*x^18 + 73265978*x^17 + 165196041*x^16 + 324386076*x^15 + 570906027*x^14 + 914354726*x^13 + 1326830817*x^12 + 1731692416*x^11 + 2055647184*x^10 + 2257532160*x^9 + 2246693120*x^8 + 1939619840*x^7 + 1494073344*x^6 + 1097859072*x^5 + 640024576*x^4 + 207618048*x^3 + 95420416*x^2 + 50331648*x - 50331648)*sqrt(x^6 + 4*x^5 + 6*x^4 - 12*x^3 + 33*x^2 - 16*x) + 150994944*x - 134217728) Share Cite Improve this answer Follow edited Oct 15, 2020 at 15:56 answered Oct 15, 2020 at 13:11 Dima Pasechnik's user avatar Dima PasechnikDima Pasechnik 13.4k22 gold badges3030 silver badges6969 bronze badges $\endgroup$ Add a comment | -1 $\begingroup$ The Douglas Adams conjecture suggests that 42 is the answer. Share Cite Improve this answer Follow answered 29 mins ago John Bohn's user avatar John BohnJohn Bohn 1 New contributor John Bohn is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. $\endgroup$ Add a comment | Your Answer [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Thanks for contributing an answer to MathOverflow! * Please be sure to answer the question. Provide details and share your research! But avoid ... * Asking for help, clarification, or responding to other answers. * Making statements based on opinion; back them up with references or personal experience. Use MathJax to format equations. MathJax reference. To learn more, see our tips on writing great answers. Draft saved Draft discarded [ ] Sign up or log in Sign up using Google Sign up using Facebook Sign up using Email and Password Submit Post as a guest Name [ ] Email Required, but never shown [ ] Post as a guest Name [ ] Email Required, but never shown [ ] Post Your Answer Discard By clicking "Post Your Answer", you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct. Not the answer you're looking for? Browse other questions tagged * algorithms * integration * computer-algebra * differential-algebra or ask your own question. * Featured on Meta * Moderation strike: Results of negotiations * Our Design Vision for Stack Overflow and the Stack Exchange network * Moderation strike update 6 and last : back to work Linked 32 How does Mathematica do symbolic integration? 4 Techniques to solve equations involving a definite integral Related 24 Fastest algorithm to compute the sum of primes? 22 Does a theory of stochastic differential algebras exist? 7 Books/Lecture notes which contrast Risch algorithm with basic standard procedure of finding an antiderivative Question feed Subscribe to RSS Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader. [https://mathoverflow] * MathOverflow * Tour * Help * Chat * Contact * Feedback Company * Stack Overflow * Teams * Advertising * Collectives * Talent * About * Press * Legal * Privacy Policy * Terms of Service * Cookie Settings * Cookie Policy Stack Exchange Network * Technology * Culture & recreation * Life & arts * Science * Professional * Business * API * Data * Blog * Facebook * Twitter * LinkedIn * Instagram Site design / logo (c) 2023 Stack Exchange Inc; user contributions licensed under CC BY-SA. rev 2023.8.14.43577 Your privacy By clicking "Accept all cookies", you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. Accept all cookies Necessary cookies only Customize settings