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) 
     ```


CC:  @kcrisman

Component: **symbolics**

Keywords: **inequality, solver, maxima**

Author: **Burcin Erocal, Ralf Stephan**

Branch/Commit: **[u/rws/7660-1](https://github.com/sagemath/sagetrac-mirror/tree/u/rws/7660-1) @ [`37c5190`](https://github.com/sagemath/sagetrac-mirror/commit/37c5190e9fdc3a6195a564fd3e61f2eaa06bb892)**

_Issue created by migration from https://trac.sagemath.org/ticket/7660_

[sagetrac-tnv]

comment:5

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 #11309 ?

[kini]

comment:6

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]

comment:7

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]

comment:8

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]

comment:9

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]

comment:10

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.

[sagetrac-robert-dodier]

comment:11

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]

comment:12

Attachment: trac_7660-inequality_arithmetic.patch.gz

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.

[rwst]

comment:15

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.

[rwst]

Branch: u/rws/ticket/7660

[rwst]

Commit: d2801be

[rwst]

Changed keywords from none to inequality, solver, maxima

[rwst]

New commits:

d2801be

[mq]: trac_7660-inequality_arithmetic.patch

[rwst]

comment:18

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. (catch maxima RuntimeErrors and rethrow usefully #15902)
  `

[rwst]

Work Issues: fix bug

[sagetrac-git]

Changed commit from d2801be to 39d85bf

[sagetrac-git]

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

39d85bf

Merge branch 'ticket/7660' into tmp

[fchapoton]

comment:61

does not apply

[sagetrac-git]

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

352c685

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

[sagetrac-git]

Changed commit from 2edba4d to 352c685

[fchapoton]

comment:64

does not apply

[rwst]

comment:65

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

[rwst]

Changed branch from public/7660 to u/rws/7660-1

[rwst]

Changed commit from 352c685 to bb1aae0

[rwst]

New commits:

bb1aae0

7660: fix arithmetic with equations and inequalities

[fchapoton]

comment:68

does not apply

[sagetrac-git]

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

37c5190

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

[sagetrac-git]

Changed commit from bb1aae0 to 37c5190