arithmetic with equations and inequalities confusing

[burcin]

Equations and relations should behave like this: equations:

• (a==b) +-*/ c same as:
  • (a==b).add_to_both_sides(c)
  • (a==b).subtract_from_both_sides(c)
  • (a==b).multiply_both_sides(c)
  • (a==b).divide_both_sides(c)
  • False if */0
• (a==b)^c --> a^c == b^c
• f(a==b) --> f(a)==f(b)

relations:

• (a<b) +- c same as:
  • (a<b).add_to_both_sides(c)
  • (a<b).subtract_from_both_sides(c)
• (a<b) */ c same as:
  • a*/c > b*/c for c real and negative, or if c is assumed negative
  • a*/c < b*/c for c real and positive, or if c is assumed positive
  • False if c=0 or assumed zero
  • if c contains variables (and no assumptions exist about it) raise ArithmeticError: missing assumption: is ...>0?
  • if c contains no variables ArithmeticError: multiplication of inequality with irreal
• (a<b)^c --> (a<b)^c
• f(a<b) --> f(a<b)

Original description:

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.

[rws]

OK that patch applies cleanly with patch -l. It results in

sage: var('x')
x
sage: x>1
x > 1
sage: ie=_
sage: ie*-1
-(x > 1)
sage: solve(_,x)
...
RuntimeError: ECL says: THROW: The catch MACSYMA-QUIT is undefined.

I refrained from starting any doctests.

[rws]

New commits:

​d2801be

[mq]: trac_7660-inequality_arithmetic.patch

[rws]

Here are the statements sent via maxima_eval("#$%s$"%statement):

Before:

sage: solve(-(x > 1),x)
sage0 : (x)*(-1) > -1
sage1 : solve_rat_ineq(sage0)
_tmp_ : sage1
kill(sage1)
kill(sage0)
[[x < 1]]

After:

sage: solve(-(x > 1),x)
sage12 : (x > 1)*(-1) = 0
sage13 : x
sage14 : solve(sage12,sage13)
kill(sage13)
kill(sage14)
_tmp_ : [x>1=0]          <---------?
kill(sage12)

Apparently, Sage's last statement sent is the result itself (no idea why), and maxima then barfs because it can't digest its own output. In maxima:

(%i11) solve((x > 1)*(-1) = 0,x);
(%o11)                            [x > 1 = 0]
(%i12) [x>1=0];
incorrect syntax: Found logical expression where algebraic expression expected
[x>1=
   ^

In summary there are three problems:

• 46 doctests fail in symbolic alone
• maxima can't handle the formal expressions generated via this patch, and solve() will fail because it uses maxima solve() and not solve_rat_ineq() (probably because the expression looks like an algebraic). However:

  sage: solve_ineq((x>1)*(-1),[x,y])
  #0: solve_rat_ineq(ineq=-(x > 1))
  ...
  TypeError: ECL says: Error executing code in Maxima: solve_rat_ineq:  -(x > 1)  is not an inequality.
  

So maxima refuses to handle the formal expression generated by this patch, and this means they cannot be solved, regardless of method called. So, in addition, solve() should be changed to do simplification of these expressions before handing them on. This special simplification avoids all issues raised in comment:10. It can be implemented after this ticket (#15906).

• calculus.py:symbolic_expression_from_maxima_string() should catch maxima RuntimeErrors from ecl.c and rethrow them with meaningful information. (#15902)

`

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​39d85bf

Merge branch 'ticket/7660' into tmp

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ea75f5b

fix relational.add/sub/mul/div_both_sides(); fix doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​de2f0a0

Merge branch 'develop' (6.2.beta4) into ticket/7660

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c75a38e	Merge branch 'develop' into rev/7660
​5d93415	Merge branch 'develop' into rev/7660

[aapitzsch]

Please use python3 compatible raise TypeError syntax.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cb6af46	Merge branch 'develop' into t/7660/ticket/7660
​30cc860	7660: replace old-style exception strings

[rws]

Replying to aapitzsch:

Please use python3 compatible raise TypeError syntax.

Done. Still, doctests fail in expression.pyx.

[rws]

This came up again in ​http://ask.sagemath.org/question/25217/how-to-do-operations-that-change-a-relation/

[jdemeyer]

I'm just now looking at this ticket and personally I don't like to lose the ability to compute with relations. I think that the fact that (a == b)^2 returns a^2 == b^2 is a feature, not a bug. I'd say it's up to the user to ensure that the operation makes sense.

Would it be possible to keep the old behaviour for equalities == at least?

[rws]

Let's start this fresh. To summarize, what's wanted is the following:

equations:

• (a==b) +-*/ c same as:
  • (a==b).add_to_both_sides(c)
  • (a==b).subtract_from_both_sides(c)
  • (a==b).multiply_both_sides(c)
  • (a==b).divide_both_sides(c)
  • False if */0
• (a==b)^c --> a^c == b^c
• f(a==b) --> f(a==b)

relations:

• (a<b) +- c same as:
  • (a<b).add_to_both_sides(c)
  • (a<b).subtract_from_both_sides(c)
• (a<b) */ c same as:
  • a*/c > b*/c for c real and negative, or if c is assumed negative
  • a*/c < b*/c for c real and positive, or if c is assumed positive
  • False if c=0
• (a<b)^c --> (a<b)^c
• f(a<b) --> f(a<b)

Question: Real or: if coerced to the reals successfully? A followup extension would be like Maxima's ineq package, i.e., ask before doing a sign switch.

[jdemeyer]

Replying to rws:

• f(a==b) --> f(a==b)

What does f(a==b) even mean? I would go for f(a) == f(b).

relations:

• (a<b) */ c same as:
  • a*/c > b*/c for c real and negative, or if c is assumed negative
  • a*/c < b*/c for c real and positive, or if c is assumed positive
  • False if c=0

What if neither of the above conditions is true? raise ArithmeticError in that case?

[rws]

Replying to jdemeyer:

• (a<b) */ c

What if neither of the above conditions is true? raise ArithmeticError in that case?

Not if c contains variables. Is there even a way of determining this?

[jdemeyer]

Replying to rws:

Not if c contains variables.

What would you propose that x * (y < z) answers then (where x, y and z are variables)?

[rws]

Replying to jdemeyer:

What would you propose that x * (y < z) answers then (where x, y and z are variables)?

Since this ticket will check for assumptions, if there is none we should raise an ArithmeticError demanding one.

[jdemeyer]

So my statement to raise ArithmeticError if neither condition is true still remains.

[jdemeyer]

Replying to burcin:

• if c contains variables (and no assumptions exist about it) raise ArithmeticError: missing assumption: is ...>0?
• if c contains no variables ArithmeticError: multiplication of inequality with irreal

I think it will be easier if these are just one case.

[rws]

Since the f() stuff requires changes in function base classes, and assumptions are also an involvement, I'll leave both to followup tickets. Please review.

---

New commits:

​855fba8	7660: power of inequality no longer distributes over sides
​47251f2	7660: switch inequality sign with negative reals, False if zero; provide original behaviour in mul/div_both_sides()
​efeab1c	7660: same with division
​14ede75	7660: add errors; fix some doctests

[jdemeyer]

Why convert to RR? I would simply use

if right == 0:
    ...
elif right >= 0:
    ...
elif right <= 0:
    ...
else:
    raise ArithmeticError(...)

This handles non-constant symbolic expressions also.

[rws]

Replying to jdemeyer:

Why convert to RR? I would simply use

if right == 0:
    ...
elif right >= 0:
    ...
elif right <= 0:
    ...
else:
    raise ArithmeticError(...)

This handles non-constant symbolic expressions also.

Seems we have to open a ticket?

sage: def f(ex):
    if ex==0:
        print 'zero'
    elif ex<0:
        print 'minus'
    else:
        print 'else'
....:         
sage: ex=-I
sage: f(ex)
minus
sage: bool(-I<0)
True
sage: bool(I>0)
True

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​37f8ba4	Merge branch 'develop' into t/7660/public/7660
​d89485d	7660: last fixes

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​17c4e8a

Merge branch 'develop' into t/7660/public/7660

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​463a676

Merge branch 'develop' into t/7660/public/7660

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​32f923d

Merge branch 'develop' into t/7660/public/7660

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7be8930

Merge branch 'develop' into t/7660/public/7660

[rws]

@aapitzsch Are you willing to review this issue?

[aapitzsch]

Replying to rws:

@aapitzsch Are you willing to review this issue?

No. Sorry for the noise.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​60ac718

Merge branch 'develop' into t/7660/public/7660

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​aebaf17

missing change due to incomplete merge conflict

[rws]

Relevant doctest fail in src/sage/misc/sageinspect.py

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b769b4b	Merge branch 'develop' into t/7660/public/7660
​2edba4d	7660: fix last line test again

[chapoton]

does not apply

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​352c685

Merge branch 'develop' into t/7660/public/7660

[chapoton]

does not apply

[rws]

In the course of this ticket already 12 merge commits were added. The branch has 8 so I'm doing a squash.

[rws]

New commits:

​bb1aae0

7660: fix arithmetic with equations and inequalities

[chapoton]

does not apply

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​37c5190

Merge branch 'develop' into t/7660/7660-1