[Date Index] [Thread Index] [Author Index]

Re: another Bug in Reduce ?

• To: mathgroup at smc.vnet.net
• Subject: [mg60533] Re: another Bug in Reduce ?
• From: Maxim <ab_def at prontomail.com>
• Date: Mon, 19 Sep 2005 04:45:49 -0400 (EDT)
• References: <dgit7h$2ag$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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

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

• Follow-Ups:
  • Re: Re: another Bug in Reduce ?
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>