Content deleted Content added
No edit summary |
m Maintain {{WPBS}}: 1 WikiProject template. Remove 1 deprecated parameter: field. Tag: |
||
| (40 intermediate revisions by 26 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|importance=mid}}
}}
==Constant undecidability==
Line 34 ⟶ 38:
[[User:Baccala@freesoft.org|Baccala@freesoft.org]] 21:49, 26 January 2006 (UTC)
:: I think the following statement applies, and is confusingly written:
:::''Also, the Risch algorithm is not an "algorithm" literally, because it needs as a part to check if some expression is equivalent to zero. And for a common meaning of what an "elementary function" is it's not known whether such an algorithm exists or not''
:: That sentence needs to be put into the intro if its correct, it needs to be sourced, and if its true we need to stop calling it an algorithm. [[User:Fresheneesz|Fresheneesz]] ([[User talk:Fresheneesz|talk]]) 07:40, 18 November 2008 (UTC)
Basically, these problems arise in the constant field. So you can have some function c*f(x), and c == 0 will be undecidable. Therefore, the Risch Algorithm requires that the constant field be computable. For example, for Q, the rational numbers it ''is'' decidable if a == 0, but this also the case, for example, in Q(a), the field or rational functions on a with rational coefficients, where a is some variable not dependent on x, the integration variable, or even Q(a1, a2, …, an), where the ai do not depend on each other or on x. The actual result of course does not apply to the function field, because abs() is non-elementary. Even if you get a function that is really 0, and try to Risch integrate it, you will get as your result a function that is really an element of the constant field. For example, the integral of sin(x)^2 + cos(x)^2 - 1 is (integrating term wise), x/2 - sin(x)*cos(x)/2 + sin(x)*cos(x)/2 + x/2 - x, which is of course 0. But the algorithm never needed to know or care that the integrand was really identically 0 to get to that. Also, you should know that basic things like the division algorithm, which are essential to algorithms like the Risch Algorithm or even Euclid's gcd algorithm, do not work correctly if they cannot determine zero-equivalence in their coefficients. --<span style="color:#008888;">[[User:Asmeurer|<span style="color:#008888;">Asmeurer</span>]] ([[User talk:Asmeurer|<span style="color:#008888;">talk</span>]] ♬ [[Special:Contributions/Asmeurer|<span style="color:#008888;">contribs</span>]])</span> 03:37, 17 July 2010 (UTC)
"An important consequence of Risch's result is that the Gaussian integral has no elementary antiderivative." Actually, this was proven by Liouville years before Risch. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/82.244.80.154|82.244.80.154]] ([[User talk:82.244.80.154|talk]]) 20:22, 5 October 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Possibly an error? ==
Line 48 ⟶ 60:
::Why not write it with the logarithms? Because I went to check Rosenlicht, and he stated the result in terms of ''f''.
::[[User:XaosBits|XaosBits]] 01:33, 10 May 2006 (UTC)
::: In the current state of the article this formula is a little overcomplicated: why are there logarithms in the first place? If the formula is correct, then there's no need for logarithms, since the logarithm of an elementary function is an elementary function.
::: [[Special:Contributions/85.187.35.160|85.187.35.160]] ([[User talk:85.187.35.160|talk]]) 15:27, 13 January 2011 (UTC)
:::: As it is stated, the sum is not needed at all: if you skip the sum, it says that if there is an elementary solution ''g'' then for some elementary function ''v'' the solution is of the form ''g''=''v'', so there's obviously something wrong with the statement. /[[User:Pontus|Pontus]] ([[User talk:Pontus|talk]]) 09:25, 31 May 2011 (UTC)
== typo of some sort? ==
Line 63 ⟶ 78:
:: <math> f(x) = x / \sqrt{x^4 + 10 x^2 - 96 x - 71}</math>
This is simply not true. Both Mathematica and Maple can calculate the antiderivative (even not-so-recent versions). Anyone can try this at http://integrals.wolfram.com/ . (The Root[] objects represent roots of polynomials, i.e. numbers, and can be easily expanded (written in explicit form) using the ToRadicals[] command). I won't edit the article because I am not familiar with the topic (perhaps these programs don't use the Risch-algorithm for this specific problem?), but this needs to be cleaned up or rephrased ... <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/129.177.44.25|129.177.44.25]] ([[User talk:129.177.44.25|talk]]) 08:51, 8 April 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: Sorry to tell this, but this seems to be correct. Try http://integrals.wolfram.com with input "x/sqrt(x^4+10*x^2-96*x-71)". You will receive large answer. But the problem is not in the Root[] objects (of course, you are right, they are just numbers, so the fuction is elementary even if it use such numbers - no matter whether they can be transferred to radicals or not). The problem that the answer contains "F", and "Π". F is which is elliptic ingegral of the first kind, and Π is elliptic integral of the third kind. Both F and Π cannot be written using elementary functions. And the question is not whether x/sqrt(x^4+10*x^2-96*x-71) has an antiderivative - the question is <i>whether this antiderivative can be written using elementary functions</i>.
: Starting from this point to the end, I am not sure, whether this is 100% correct.
: Try to change 71 to 72 in the polynomial. Integrals.wolfram.com will give you the answer which will look near the same. This is because integrals.wolfram.com cannot understand, that there is very big difference between
: x/sqrt(x^4+10*x^2-96*x-71) and
: x/sqrt(x^4+10*x^2-96*x-72)
: Antiderivative of the first <i>can</i> be written using elementary functions, and antiderivative of the second cannot. This is because Galois groups of these polynomials are different:
: x^4+10*x^2-96*x-71 Galois group is D(4), e.g. generated by permutations (1 2 3 4) and (1 3), and contains 8 elements (same as in "x^4-2")
: x^4+10*x^2-96*x-72 Galois group is S(4), e.g. generated by permutations (1 2), (1 3), (1 4) and contains 24 elements
: So x^4+10*x^2-96*x-71 is very special case of quadric polynomials, and this is the reason why Risch algorithm in the 71 case gives the answer "yes", and in the 72 case gives the answer "no".
: I have tried Maple v. 11 with input:
: simplify(convert(int(x/sqrt(x^4+10*x^2-96*x-71),x),radical));
: The answer also contains "EllipticF" and "EllipticPi". So Maple also does not understand that antiderivative for x/sqrt(x^4+10*x^2-96*x-71) can be written using elementary functions.
: Do you agree with my argumentation?
: Sorry for my bad English.
: [[User:Gaz v pol|Gaz v pol]] ([[User talk:Gaz v pol|talk]]) 18:14, 18 April 2008 (UTC)
:: What the original writer of the article was ''trying'' to say is probably correct. What the article is really saying (i.e. that no system can find an antiderivative---no mention of elementary functions) is incorrect (Mathematica does find an antiderivative, but not in terms of elementary functions). This article needs a big cleanup, but I dare not touch it because this is a very complicated mathematical topic that I know nothing about (I came here to learn a little about it :) ). If you are familiar with the topic, it would be great if you cleaned it up a bit (and made it more precise)! <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/83.166.219.47|83.166.219.47]] ([[User talk:83.166.219.47|talk]]) 15:41, 6 June 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:::Just FYI, this is how complex this is: https://math.stackexchange.com/questions/681893/how-to-integrate-int-fracx-sqrtx410x2-96x-71dx Stackexchange cannot be used on wikipedia though. [[Special:Contributions/109.252.90.67|109.252.90.67]] ([[User talk:109.252.90.67|talk]]) 03:54, 28 November 2021 (UTC)
::::This craziness can be finally solved by Mathematica 13: https://www.wolframcloud.com/obj/d9af14f6-3b98-43c4-b996-11dedc9d9f10 [[Special:Contributions/2A00:1370:812D:5272:8FD:D915:7268:189C|2A00:1370:812D:5272:8FD:D915:7268:189C]] ([[User talk:2A00:1370:812D:5272:8FD:D915:7268:189C|talk]]) 16:55, 11 December 2021 (UTC)
== Unsolved Integral ==
The last example says that no software is known to be able to solve it, however it appears sympy(which uses the Risch algorithm), can: http://dpaste.com/81951/ <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.113.195.217|128.113.195.217]] ([[User talk:128.113.195.217|talk]]) 16:52, 2 October 2008 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
See http://live.sympy.org/ to try it.
--[[Special:Contributions/91.39.86.160|91.39.86.160]] ([[User talk:91.39.86.160|talk]]) 10:22, 3 October 2008 (UTC)
:I profiled the code and it seems that it is indeed the rich algorithm that computes this one (i.e., it is not some special case in the code). This is interesting, because SymPy cannot even do the other one on this page (maybe because it is not so easy in the elementary case and it doesn't know about the special functions that Maple and Mathematica produce). I will update the article. <span style="color:#008888;">[[User:Asmeurer|<span style="color:#008888;">Asmeurer</span>]] ([[User talk:Asmeurer|<span style="color:#008888;">talk</span>]] ♬ [[Special:Contributions/Asmeurer|<span style="color:#008888;">contribs</span>]])</span> 16:09, 9 October 2009 (UTC)
== Issues with section [[Risch algorithm#Description|Description]]? ==
The section says:
:"[[Liouville]] formulated the problem solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution ''g'' to the equation ''g'' ′ = ''f'' then for constants α<sub>''i''</sub> and elementary functions ''u<sub>i</sub>'' and ''v'' the solution is of the form
::<math> f = \sum_{i<n} \alpha_i \frac{u_i^{\prime}}{u_i} + v^\prime \,.</math>"
#<math>f</math> should be already known, we seek <math>g</math> (see also [[#Possibly an error?|above]]).
#What does <math>n</math> (the upper bound for the sum index) stand for?? I assume it just indicates that the index set is finite, but in that case I don't understand the following: "Risch developed a method that allows one to only consider a finite set of elementary functions of Liouville's form."
Can anybody enlighten me on this? --[[User:Berntie|Berntie]] ([[User talk:Berntie|talk]]) 20:19, 4 October 2008 (UTC)
== Claims ==
The article claims that only Axiom can solve a certain integral, and that a second is unsolvable by any present CAS. I made a page [[User:CRGreathouse/Risch]] on my userspace to record my test of those claims: regardless of the need for [[WP:V]], I'd be happier if I knew the claims in the article were true.
It seems that the first claim holds: I was not able to find any CAS other than Axiom solving the first integral, not even the new version of Mathematica. The second claim is false, as SymPy solves it fairly quickly.
I would prefer to take examples out of published papers, because those may have claims like "no CAS known to the authors can solve this". For the time being, I think we should leave the first integral but remove the claim on the second (and maybe remove it outright).
[[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 05:43, 14 May 2009 (UTC)
: Hello CRGreathouse! I was the person who added both these examples. At the time of adding it was true (we have tested almost all available CAS's). However, as you wrote, now the second example can be solved by SymPy. That's very interesting. I do not trust that any software has implemented the Risch algorighm in full now. But I will test current version of SymPy and try to give you better example. Thank you.[[User:Gaz v pol|Gaz v pol]] ([[User talk:Gaz v pol|talk]]) 22:28, 17 May 2009 (UTC)
:: I'm almost certain that SymPy doesn't have a full implementation of the Risch algorithm -- and as you can see in my page or try yourself, it can't handle your first example.
:: Would you give the results (here or on my page) for Maple and MathCad? Those two seem like the only other ones with a reasonable chance at solving hard integrals.
:: [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 00:56, 18 May 2009 (UTC)
::: It seems that I will have access to Maple 13 only at about 20'th of June (Maple 12 cannot solve this). I will send you info about whether Maple 13 can do this when I will have access. Sorry for the delay. [[User:Gaz v pol|Gaz v pol]] ([[User talk:Gaz v pol|talk]]) 11:02, 1 June 2009 (UTC)
:::: Not a problem. Would you also paste the Maple command you're using on [[User:CRGreathouse/Risch|my page]]? That way others can verify it more easily. I look forward to seeing what Maple 13 can do when you get access. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 15:08, 1 June 2009 (UTC)
::::: I checked with Maple 13 under Windows 7 today. Results: first integral - with EllipticF (so Maple does not make use of the Galois group of the polynomial under sqrt), second - no success, third - full success. I have added results to your page, but not to the table (sorry, I feel not comfort with editing html). I can also check any other integral on Maple 13 by your request. Also I have tried SymPy with simular integrals but with change x to x-1. It gives me error. Either I have done something wrong with syntax (that's possible), or they just added this particular integral to their table :-). I suggest the following to be written on the page: 1'st integral can be done only by Axiom, second only by SymPy, and their sum can be done by no software as of June 2008. What do you think about this idea?[[User:Gaz v pol|Gaz v pol]] ([[User talk:Gaz v pol|talk]]) 15:38, 10 June 2009 (UTC)
:::::: Sounds good to me. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 16:17, 11 June 2009 (UTC)
::::: That integral is NOT in SymPy's heuristic table (otherwise, it wouldn't take so long to compute it :). It is being computed by SymPy's implementation of Bronstein's poor-man's integrator, which is based on the Risch-Norman algorithm. Actually, I wonder if we should be looking at the poor-man's integrator here (the original code is in Maple syntax).
::::: But if you are looking for more examples of hard integrals, you might try some of the other ones from Bronstein's integration tutorial (see the references of this article, it's freely downloadable on his website).
::::: And by the way, I got the integral with x + 1 to work just fine.<span style="color:#008888;">[[User:Asmeurer|<span style="color:#008888;">Asmeurer</span>]] ([[User talk:Asmeurer|<span style="color:#008888;">talk</span>]] ♬ [[Special:Contributions/Asmeurer|<span style="color:#008888;">contribs</span>]])</span> 00:57, 14 November 2010 (UTC)
== Decidability unknown for elementary functions ==
But isn’t <math>|x|=\sqrt{x^2}</math> elementary presentable? --[[User:Chricho|Chricho ∀]] ([[User talk:Chricho|talk]]) 23:07, 26 June 2012 (UTC)
:The problem is that there are 2 square roots to each number, and the choice between them cannot be controlled. So <math>\sqrt{x^2}</math> could also mean <math>x</math>, or <math>-x</math>--[[Special:Contributions/77.126.235.228|77.126.235.228]] ([[User talk:77.126.235.228|talk]]) 14:34, 13 May 2013 (UTC)
::I agree with Chriko. Nowadays the <math>\sqrt{}</math> symbol is most widely used to mean "the positive square root of". An example of this is the quadratic formula. If the symbol were used to signify both the positive and negative square root we wouldn't need the plus or minus sign before it. Also <math>\sqrt{x}</math> would not be a function if that symbol were used for both the positive and negative square root. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/98.232.93.206|98.232.93.206]] ([[User talk:98.232.93.206|talk]]) 05:22, 20 October 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== A New Algorithm ==
It's possible we need a new algorithm. Since this topic about symbolic integration algorithms is connected to differential Galois theory, maybe we need one that uses Galois groups and it's generated permutations. Galois group would be relatively easy to implement, perhaps using set from C++ would be a good idea. We also need to generate a constructor which tests that E is an extension to F. For more information look at [[Galois group|this]] [[User:Gave232|Gave232]] ([[User talk:Gave232|talk]]) 22:49, 15 July 2013 (UTC)Gave232
== Inaccurate statement ==
"the indefinite integral of a rational function is a rational function and a finite number of constant multiples of logarithms of rational functions."
Unless they are including complex logarithms, you also need to consider inverse tangents, which are the result of irreduceable quadratic factors in the denominator.
For example, the integral of (x^3+x-1)/(x^4+x^2) is ln|x|+1/x+arctanx+C
[[Special:Contributions/98.232.93.206|98.232.93.206]] ([[User talk:98.232.93.206|talk]]) 05:14, 20 October 2013 (UTC)
: Complex logarithms are included. They are also allowed in the definition of an [[elementary function]]. — [[User:Pt|Pt]] <sub>[[User_talk:Pt|(T)]]</sub> 13:20, 20 April 2015 (UTC)
== Missing Algorithm ==
An adequate description of the Risch Algorithm seems to be missing ... from the article about the Risch Algorithm. Bah, minor detail. [[Special:Contributions/88.130.29.105|88.130.29.105]] ([[User talk:88.130.29.105|talk]]) 07:27, 18 April 2015 (UTC)
:Can you use AGI level GPT 4 to create small outline of the algorithm? [[Special:Contributions/2A00:1370:8184:1CE9:15B1:85BD:FE6A:1AB6|2A00:1370:8184:1CE9:15B1:85BD:FE6A:1AB6]] ([[User talk:2A00:1370:8184:1CE9:15B1:85BD:FE6A:1AB6|talk]]) 20:48, 24 March 2023 (UTC)
| |||