Re: Re: another Bug in Reduce ?

*To*: mathgroup at smc.vnet.net*Subject*: [mg60565] Re: [mg60533] Re: another Bug in Reduce ?*From*: Adam Strzebonski <adams at wolfram.com>*Date*: Tue, 20 Sep 2005 05:19:47 -0400 (EDT)*References*: <dgit7h$2ag$1@smc.vnet.net> <200509190845.EAA23572@smc.vnet.net> <ED1C56B6-A552-4CA6-A365-562B710B4271@mimuw.edu.pl>*Reply-to*: adams at wolfram.com*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote: > > On 19 Sep 2005, at 17:45, Maxim wrote: > >> On Sun, 18 Sep 2005 05:16:33 +0000 (UTC), Peter Pein <petsie at dordos.net> >> wrote: >> >> >>> Dear group, >>> >>> in message <dba4l5$elr$1 at smc.vnet.net> (07/16 2005), Mukhtar Bekkali >>> described a problem which involved Root[.] in dependance of a >>> parameter. >>> >>> This revealed another difference in the Reduce algorithms of versions >>> 5.1 and 5.2. >>> >>> Please have a look at >>> http://people.freenet.de/Peter_Berlin/Mathe/ReduceBug/ReduceBug.nb or >>> http://people.freenet.de/Peter_Berlin/Mathe/ReduceBug/ReduceBug.html. >>> >>> In this case, version 5.1 did the better Job (and faster too). >>> >>> Peter >>> >>> P.S. the strange looking test for the root being real became necessary, >>> because Im[#]==0& did not work. (?) >>> >>> >> >> It seems that Reduce has problems with multiple roots: >> >> In[1]:= $Version >> >> Out[1]= "5.2 for Microsoft Windows (June 20, 2005)" >> >> In[2]:= Reduce[Root[#^3 + p*# - p - 1&, 2] == >> Root[#^3 + p*# - p - 1&, 3], Reals] (* /. p -> -3 *) >> >> Out[2]= False >> >> In[3]:= Reduce[Root[#^3 + p*# - p - 1&, 3] > 0] (* /. p -> -3 *) >> >> Out[3]= p < -3 || -3 < p < -3/4 > > > > > The problem here seems to be with CylindricalDecomposition. This gives > the right answer: > > > CylindricalDecomposition[y^3 + p*y - p - 1 == 0, {p, y}] > > > (p < -3 && (y == (-(1/2))*Sqrt[-4*p - 3] - 1/2 || > y == 1 || y == (1/2)*Sqrt[-4*p - 3] - 1/2)) || > (p == -3 && (y == -2 || y == 1)) || > (-3 < p < -(3/4) && (y == (-(1/2))*Sqrt[-4*p - 3] - > 1/2 || y == (1/2)*Sqrt[-4*p - 3] - 1/2 || > y == 1)) || (p == -(3/4) && (y == -(1/2) || > y == 1)) || (p > -(3/4) && y == 1) > > we see that the cylindrical has cylinders for p<-3, -3<p<(-3/4) and > single points for p=-3, p=-3/4. These correspond to multiple roots. > However, when we look at the way in which these solutions appear in the > cylindrical decomposition we see (p == -3 && (y == -2 || y == 1)) > whereas the actual solution is (p == -3 && (y == -2 || y == 1 || y== > 1)) and similarly (y == -(1/2) || y == 1)) while the solution is (y == > -(1/2) || y == 1) || y== -(1/2)). CylindricalDecomposition does not show multiplicities. I don't think the notion of solution multiplicity is even well defined for a general system of equations and inequalities... > So maybe this explains what we see here: > > > CylindricalDecomposition[Root[#1^3 + p*#1 - p - 1 & , 3] - Root[#1^3 + > p*#1 - p - 1 & , 2] == q, {p, q}] > > (p < -3 && q == (1/2)*Sqrt[-4*p - 3] - 3/2) || (-3 < p < -(3/4) && q == > 3/2 - (1/2)*Sqrt[-4*p - 3]) > > Note that the case p=-3 does not appear. This seems to be due to the > fact that in the above solution there appear only two roots for the > case p=-3 and there is not third one. Now look at the next output: > > > CylindricalDecomposition[Root[#1^3 + p*#1 - p - 1 & , 1] - Root[#1^3 + > p*#1 - p - 1 & , 2] == q, {p, q}] > > > (p <= -3 && q == (-(1/2))*Sqrt[-4*p - 3] - 3/2) || (-3 < p < -(3/4) && > q == -Sqrt[-4*p - 3]) || (p == -(3/4) && q == -(3/2)) > > > Now the case p== -3/4 does appear but look at the value of q. It is > -3/2 which is the difference -1/2 -1. But this is not the difference > between the first and the third root! So it looks like we are seeing > the cause of the bug: it comes form the fact that > CylindricalDecomposition forgets about double roots as in the above > example. It was a bug in the CAD code handling Root objects with parameters. Thank you for isolating it. I have fixed it in the development version. A piece of code which required input preprocessed with Factor was being called without the preprocessing. In effect, if the defining polynomial of a Root object with parameters given in the input was not staying exactly the same after applying Factor to it, CAD could get root multiplicities wrong. In your example the polynomial has two factors In[2]:= #1^3 + p*#1 - p - 1//Factor 2 Out[2]= (-1 + #1) (1 + p + #1 + #1 ) In the original example Mathematica 5.2 (but not Mathematica 5.1) Root function collects coefficients in the defining polynomial wrt. powers of #1 In[1]:= Root[-160 + 783*x + 54*x^2 - 1059*#1 - 540*x*#1 + 504*#1^2 + 80*#1^3 &, 3][[1, 1]]//InputForm Out[1]//InputForm= -160 + 783*x + 54*x^2 + (-1059 - 540*x)*#1 + 504*#1^2 + 80*#1^3 which uncovers the bug in CAD, because Factor gives a completely expanded form In[2]:= Factor[%]//InputForm Out[2]//InputForm= -160 + 783*x + 54*x^2 - 1059*#1 - 540*x*#1 + 504*#1^2 + 80*#1^3 > > As for the rest of the problems they seem to me very difficult to deal > with. Essentially the algorithms used by Reduce, > CylindricalAlgebraicDecomposition and Quantifier ELimination are purely > algebraic; they work for polynomial expressions. It seems to me that > all other types of expressions have to be deal with by heuristic > methods and probably can never be made fully reliable (which is not to > say they can't be made better). > Cylindrical algebraic decomposition can handle real algebraic functions (Root objects and radical expressions) in full generality. It should always give the correct answer (provided there are no bugs...). Best Regards, Adam Strzebonski Wolfram Research

**References**:**Re: another Bug in Reduce ?***From:*Maxim <ab_def@prontomail.com>