arithmetic with inequalities confusing

[burcin]

From the following sage-devel thread:

 http://groups.google.com/group/sage-devel/t/951d510c814f894f

Arithmetic with inequalities can be confusing, since Sage does nothing to keep the inequality correct. For example:

On Thu, 10 Dec 2009 00:37:10 -0800 (PST) 
 	"marik@mendelu.cz" <marik@mendelu.cz> wrote: 
 	 
 	> sage: f = x + 3 < y - 2 
 	> sage: f*(-1) 
 	> -x - 3 < -y + 2 

It seems MMA doesn't apply any automatic simplification in this case:

On Thu, 10 Dec 2009 09:54:36 -0800 
William Stein <wstein@gmail.com> wrote: 
 
> Mathematica does something weird and formal: 
>  
> In[1]:= f := x+3 < y-2; 
> In[3]:= f*(-1) 
> Out[3]= -(3 + x < -2 + y) 

Maple acts more intuitively, though the way formal products are printed leaves something to be desired, IMHO:

On Thu, 10 Dec 2009 14:15:53 -0800 
William Stein <wstein@gmail.com> wrote: 
 
> Here is what Maple does: 
>  
> flat:release_notes wstein$ maple 
>     |\^/|     Maple 13 (APPLE UNIVERSAL OSX) 
> ._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple 
> Inc. 2009 \  MAPLE  /  All rights reserved. Maple is a trademark of 
>  <____ ____>  Waterloo Maple Inc. 
>       |       Type ? for help. 
> > f := x < y;   
>                                   f := x < y 
>  
> > f*(-3);   
>                                   -3 y < -3 x 
>  
> > f*z;   
>                                   *(x < y, z) 
>  
> > f*a;   
>                                   *(x < y, a) 

We should multiply both sides of the inequality only if the argument is a real number (as opposed to a symbol with real domain), and invert the relation when the argument is negative.

Note that GiNaC leaves everything formal, like MMA, by default:

ginsh - GiNaC Interactive Shell (ginac V1.5.3) 
  __,  _______  Copyright (C) 1999-2009 Johannes Gutenberg University Mainz, 
 (__) *       | Germany.  This is free software with ABSOLUTELY NO WARRANTY. 
  ._) i N a C | You are welcome to redistribute it under certain conditions. 
<-------------' For details type `warranty;'. 
 
Type ?? for a list of help topics. 
> f= x < y; 
x<y 
> f*-1; 
-(x<y) 
> f*-5; 
-5*(x<y) 
> f*-z; 
-z*(x<y) 
> f*z; 
z*(x<y) 

[tnv]

sage: -1*(x < y)
-x < -y

this is quite dangerous (I encountered it as a bug in a project). Hopefully someone will try to fix this soon. Could it be related to this  http://trac.sagemath.org/sage_trac/ticket/11309 ?

[kini]

I propose the following: a*(x<y) should not be simplified, ever, other than simplifying a, x, or y individually. Are there any problems with this?

[kcrisman]

Given the ticket description details above and the discussion at #11309 and here, I think that Burcin's original proposal of

• keeping the same if we know a is positive
• reversing if we know a is negative (presumably in both of these cases only if a is coerced to the reals successfully, as Burcin says)
• (not in original but reasonable) return something like False for < and = for <= if a=0?
• returning something formal otherwise

seems best. It does seem reasonable to multiply by -1, after all, and tnv is right that this should either reverse the inequality or remain formal.

[kini]

It doesn't seem at all reasonable to me to distribute multiplication over a relation. When you distribute multiplication over addition, the addition expression (a+b) lives in the same space as a and b individually. This is not the case with (x<y) and x and y.

There is no mathematical rationale for saying that (-1)*(x<y) is -x < -y or -x > -y or anything other than just (-1)*(x<y). I'm sure many can recall when they first learned basic algebra that their teacher was careful to say "we multiply both sides of the equation by c", not "we multiply the equation by c", just as he or she was careful to say "we multiply both the numerator and denominator of the fraction by c", rather than the dangerous "we multiply the fraction by c"!

If we allow multiplication to distribute over x<y as if it were a two-coordinate vector, do we want other similarities with vector arithmetic to come into play? Should (a+b)*(x<y) be equal to a*(x<y) + b*(x<y)? Now we have addition and presumably subtraction of relational expressions. What is 0*(x<y)? What is (x<y) + (z>y)? Should we attempt to reverse inequalities to make them match up when adding them? Do we then end up with (x+y<y+z), or (y+z>x+y)? Or, do we conclude that (z>y) is equal to (-1)*(-z<-y), and so (x<y) + (z>y) == (x<y) - (-z<-y) == (x+z<2y)? Going beyond vector-like arithmetic, what happens when you add a scalar to a relational expression? What is (x<y) + 3?

I think the most sensible answer to all the above questions is the following: we should not perform arithmetic on relational expressions; when asked to do so, we should return a purely formal expression.

If the title of this ticket disagrees with that answer, I can make another ticket to implement it, but I'm just wondering if anyone disagrees with me strongly about this.

[kcrisman]

Well, we could go to the Ginac/Mathematica way too, instead of the Maple way. But now that #11309 is on the way in, probably it's time to deal with this. FWIW, Maxima seems to go that way as well.

(%i1) x<y;
(%o1)                                x < y
(%i2) a:x<y;
(%o2)                                x < y
(%i3) a;
(%o3)                                x < y
(%i4) -1*a;
(%o4)                              - (x < y)
(%i5) b*a;
(%o5)                              b (x < y)

Maybe Burcin has a comment; I don't have that strong of feelings, though I'm partial to

• (x<y)+3 == x+3<y+3
• 0*(x<y) is False

but those may just be sentimental, as you suggest.

[kini]

Honestly I thought the most likely response would be 0*(x<y) == 0. False is an even stranger result because now you have (x<y) == (1+0)*(x<y) == (x<y) + False, so either False is now another additive identity (on relations, anyway), thus breaking the universality of ? - ? = 0, or False == 0, which is another can of worms...

And if (x<y)+3 == (x+3<y+3), then presumably 3 == (3<3) == False...?

None of this makes any sense, IMHO. I think it would be best to go the Mathematica/GiNaC/Maxima way, as shown in your Maxima output, rather than the Maple way.

[robert_dodier]

For the record, Maxima has a share package which implements arithmetic on inequalities.

(%i1) load (ineq);
(%o1) /home/robert/maxima/maxima-git/maxima-code/share/simplification/ineq.mac
(%i2) e:a < b;
(%o2)                                a < b
(%i3) x*e;
Is  x  positive, negative, or zero?
p;
(%o3)                              a x < b x
(%i4) x*e;
Is  x  positive, negative, or zero?
n;
(%o4)                              a x > b x
(%i5) x*e;
Is  x  positive, negative, or zero?
z;
(%o5)                              (a < b) x

I gather that's similar to what Maple does.

[burcin]

prototype patch

[burcin]

attachment:trac_7660-inequality_arithmetic.patch comments out a few lines in _add_, _mul_, etc., methods of symbolic expressions to pass the arithmetic on to GiNaC directly. I don't have time to test this and verify that it returns sensible answers, however we decide to define "sensible". Please test, see what doctests fail and try to produce horrific wrong results.

Quite a few doctests and some documentation will have to change to match this new design decision. I'd like to make sure we agree on the behavior before trying to produce a clean patch. Of course, I'd appreciate help with the documentation in any case.