#3072 orderlessp/great not transitive (2)

[David Scherfgen]

(This is a follow-up bug to https://sourceforge.net/p/maxima/bugs/365.)

orderlessp is still not transitive, causing the simplifier to enter a cycle when presented with certain expressions, with the order of factors or summands rotating. One consequence of this is (probably) that fullratsimp never stops sometimes, because the expression keeps changing.

An example for non-transitivity is:

(%i1) orderlessp(A(w*(x-1)), x);
(%o1) true
(%i2) orderlessp(x, A(x-1));
(%o2) true
(%i3) orderlessp(A(w*(x-1)), A(x-1));
(%o3) false

Comment by Robert Dodier:
I believe the bug originates from this:

> (%i1) ?great(x, A(x-1));
> (%o1)                                false
> (%i2) ?great(A(x-1), A(w*(x-1)));
> (%o2)                                false
> (%i3) ?great(A(w*(x-1)), x);
> (%o3)                                false

which implies these three terms have equal rank, so sorting them in
SIMPTIMES won't change their order, whatever it happens to be.

Or, written in a different way:

(%i1) [X,Y,Z]:[x,A(x-1),A(w*(x-1))]$

(%i2) ?great(Y,X);
(%o2) true

(%i3) ?great(Z,Y);
(%o3) true

(%i4) ?great(Z,X);
(%o4) false

So Y>X and Z>Y, but not Z>X!

[Dan Gildea]

[af38d28ca56623451bb94db9afb47eb3c405f82a]
use ordhack consistently whenever we see mplus/mtimes

[David Scherfgen]

Re-opening this ticket because unfortunately orderlessp is still not transitive, as shown by Stavros Macrakis:

The following triples are all cycles in orderlessp in Head:
sqrt(2), (1-sqrt(2))^x, log(1-sqrt(2))
sqrt(2), (1-sqrt(2))^x, log(2)
sqrt(2), (1-sqrt(2))^x, log(log(1-sqrt(2)))
sqrt(2), (1-sqrt(2))^x, log(log(2))
sqrt(2), (1-sqrt(2))^x, (1-sqrt(2))^(x+1)log(2)log(1-sqrt(2))
-sqrt(2), (1-sqrt(2))^x, log(1-sqrt(2))
-sqrt(2), (1-sqrt(2))^x, log(2)
-sqrt(2), (1-sqrt(2))^x, log(log(1-sqrt(2)))
-sqrt(2), (1-sqrt(2))^x, log(log(2))
-sqrt(2), (1-sqrt(2))^x, (1-sqrt(2))^(x+1)log(2)log(1-sqrt(2))
1-sqrt(2), (1-sqrt(2))^x, (1-sqrt(2))^(x+1)log(2)log(1-sqrt(2))
1-sqrt(2), (1-sqrt(2))^x, log(1-sqrt(2))
1-sqrt(2), (1-sqrt(2))^x, log(2)
1-sqrt(2), (1-sqrt(2))^x, log(log(1-sqrt(2)))
1-sqrt(2), (1-sqrt(2))^x, log(log(2))

A test has been added to the test suite.

[Dan Gildea]

Here is a proposal that would resolve the non-transitive case above,
resolve bug [#3237], and generally simplify the logic of orderlessp:

diff --git a/src/simp.lisp b/src/simp.lisp
index 1e26675..8720949 100644
--- a/src/simp.lisp                                                                          
+++ b/src/simp.lisp                                                                          
@@ -3097,14 +3097,7 @@
        ((member (caar e) '(mplus mtimes) :test #'eq)
         (let ((u (car (last e))))
           (cond ((eq u a) (not (ordhack e))) (t (great u a)))))
-       ((eq (caar e) '%del))                                                                
-       ((prog2 (setq e (car (margs e)))        ; use first arg of e                         
-            (and (not (atom e)) (member (caar e) '(mplus mtimes) :test #'eq)))              
-        (let ((u (car (last e))))              ; and compare using                          
-          (cond ((eq u a) (not (ordhack e)))   ; same procedure as above                    
-                (t (great u a)))))                                                          
-       ((eq e a))                                                                           
-       (t (great e a))))                                                                    
+       (t t)))         ; other more complex expression is greater than atom                 

This causes a total of 78 failures in the test suite, which are mostly syntactic. Any feedback on this idea?

[David Scherfgen]

This particular bug is fixed in current Maxima, therefore closing the ticket.