Re: Re: another Bug in Reduce ?
- To: mathgroup at smc.vnet.net
- Subject: [mg60543] Re: [mg60533] Re: another Bug in Reduce ?
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 20 Sep 2005 05:18:57 -0400 (EDT)
- References: <dgit7h$2ag$1@smc.vnet.net> <200509190845.EAA23572@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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)). 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. 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). Andrzej Kozlowski > > Sometimes it is not clear what the expected result of Reduce is. In > more > complicated cases it is necessary to take into account the assumptions > used by Reduce: > > In[4]:= Reduce[Im[Sqrt[x]] == 0, Reals] > > Out[4]= True > > Specifying the domain Reals tells Reduce to assume that all functions > return real values, and that includes Sqrt. So this seems logical, > although then it is hard to understand why the following example works > differently: > > In[5]:= Reduce[Im[Sqrt[x]] == 0, x, Reals] > > Out[5]= x >= 0 > > This also means that we can arrive at a contradiction if we combine > those > inconsistent results: > > In[6]:= Reduce[ForAll[x, Sqrt[x] >= 0, Im[Sqrt[x]] == 0], Reals] > > Out[6]= False > > The next example is clearly incorrect in any case, because for x == > 1 or x > == -1 all the powers are real-valued and the equation holds: > > In[7]:= Reduce[((-1)^x)^(1/x) == -1, x, Reals] > > Out[7]= False > > Another potential problem is that for some values of the parameters > the > relations may contain indeterminate quantities: > > In[8]:= Reduce[ForAll[x, 1/x == a/x]] > > Out[8]= False > > In[9]:= Reduce[!ForAll[x, 1/x == a/x]] > > Out[9]= -1 + a != 0 > > At first glance, there seems to be a contradiction: we start with the > negation of the input and do not obtain the negation of the output. > Moreover, ForAll[x, 1/x == a/x] /. a -> 1 returns True, so again In > [8] and > Out[8] are not equivalent. However, we can look at it another way: > 1/x == > a/x is not true for all x because it is not true for x == 0, where > we get > the relation ComplexInfinity == ComplexInfinity, not True. The > negation > becomes Exists[x, 1/x != a/x], and for this to be true there must > exist a > value of x such that 1/x != a/x explicitly evaluates to True. But > we can > find such value of x only if a != 1. So from this point of view both > Out[8] and Out[9] are correct. Although here again there are some > inconsistencies: > > In[10]:= Reduce[ForAll[x, 1/(x + a) != 0]] > > Out[10]= True > > In[11]:= Reduce[ForAll[x, 1/(x + a) != 0], Reals] > > Out[11]= False > > Also it's unclear how Reduce works with relations which involve > infinities: > > In[12]:= Reduce[a*Infinity < 0] > > Out[12]= a < 0 > > In[13]:= Reduce[a*Infinity > 0] > > Out[13] = False > > Finally, there still exist quite a few of old bugs in Reduce (I > think most > of them have been there since version 5.0): > > In[14]:= Reduce[x^2 == 2*y^2, Integers] (* /. x|y -> 0 *) > > Out[14]= False > > In[15]:= Reduce[i >= 0 && j >= 0 && k <= 0 && j == k, Integers] > (* /. {i -> 1, j|k -> 0} *) > > Out[15]= i == 0 && j == 0 && k == 0 > > Some of those bugs also seem to be related to the real/complex domain > assumptions: > > In[16]:= Reduce[t == -I*Log[a] && t > 0 && a > 0, {t, a}] > > Out[16]= t == Pi && a == -1 > > In[17]:= Reduce[t == -I*Log[a] && t > 0 && a < 0, {t, a}] > > Out[17]= False > > Curiously, Out[16] is the correct answer for In[17] and Out[17] is the > correct answer for In[16]. > > In[18]:= Reduce[Cos[a*Pi] < 0 && Element[a, Integers]] > > Out[18]= False > > The last one is particularly surprising; in version 5.0 the > algorithms for > solving trigonometric equations and inequalities contained a large > number > of trivial errors, and up to now only a small fraction of them have > been > fixed. > > Maxim Rytin > m.r at inbox.ru > >
- References:
- Re: another Bug in Reduce ?
- From: Maxim <ab_def@prontomail.com>
- Re: another Bug in Reduce ?