## #365 orderlessp not transitive

closed
nobody
7
2009-12-28
2003-07-23
No

l: [z+x*(x+2)+v+1,z+x^2+x+v+1,z+(x+1)^2+v];

orderlessp(l[1],l[2]) =&gt; True
orderlessp(l[2],l[3]) =&gt; True
orderlessp(l[1],l[3]) =&gt; False !!!

More concise example:

q: x^2;
r: (x+1)^2;
s: x*(x+2);

orderlessp(q,r) =&gt; true
orderlessp(r,s) =&gt; true
orderlessp(s,q) =&gt; true

That is, s&lt;q&lt;r&lt;s.

The problem is somewhere in the internal great function,
which by the way does some strange things, in
particular: why does ordlist have an explicit check for
mplus: (RETURN (COND ((= L2 0) (EQ CX 'MPLUS))

(Thanks to Barton for his contributions to tracking this
down.)

Maxima 5.9.0 GCL 2.5.0

## Discussion

• Stavros Macrakis - 2003-07-25

Logged In: YES
user_id=588346

This not only screws up SORT etc., but even basic
simplification, since simplus, simptimes, etc. depend on great:

q+r+s =&gt; (x+1)^2+x^2+x*(x+2)
q+s+r =&gt; x^2+x*(x+2)+(x+1)^2

(q+s+r)-(q+s+r) =&gt; x^2-x^2
(q+s+r)-(s+q+r) =&gt; x^2-x^2

(q+r+s)-(q+s+r) =&gt; x (x + 2) - x (x + 2)

• Stavros Macrakis - 2003-08-05

Logged In: YES
user_id=588346

More amusing consequences:

q+r+s =&gt; (x+1)^2+x^2+x*(x+2)
expand(%,0,0) =&gt; x^2+x*(x+2)+(x+1)^2
expand(%,0,0) =&gt; x*(x+2)+(x+1)^2+x^2
expand(%,0,0) =&gt; (x+1)^2+x^2+x*(x+2)

q+r+s-r-q-s =&gt; (x+1)^2+x^2+x*(x+2)-(x+1)^2-x^2-x*
(x+2)
expand(%,0,0) =&gt; x^2-x^2
expand(%,0,0) =&gt; 0

I haven't found an example where simptimes fails, though.

Fateman reports that this bug is also found in commercial
Macsyma 2.4, and calls it a Methuselah bug because it has
persisted for so long -- presumably it has been around for 30+
years.

• Wolfgang Jenkner - 2003-08-08

Logged In: YES
user_id=581700

This one doesn't even involve MEXPT (I found it while checking one of
the cases needed for proving that ORDLIST implements a consistent way
of extending a given total order on a set of simplified expressions to
their simplified sums and products. So it doesn't...)

(C1) orderlessp(t/2,t);
(D1) TRUE
(C2) orderlessp(t,t+1/4);
(D2) TRUE
(C3) orderlessp(t/2,t+1/4);
(D3) FALSE

The point is that t/2 is ((MTIMES SIMP) ((RAT SIMP) 1 2) |\$t|) and,
lexicographically, we have (t, 1/2) &lt; (t, 1), (t, 0) &lt; (t, 1/4) and
(t, 1/2, *) &gt; (t, 1/4, +). So t corresponds to (t, 1) in the first
comparison and to (t, 0) in the second comparison. Trouble.

Floats instead of rational numbers give the same results, by the way.

This one is more like Stavros's examples.

(C1) orderlessp((x+1)^2,x^2-1);
(D1) TRUE
(C2) orderlessp(x^2-1,x^2);
(D2) TRUE
(C3) orderlessp((x+1)^2,x^2);
(D3) FALSE

Maybe powers whose exponents are positive integers should be treated
like products. Actually, ORDMEXPT does this already but it isn't
always called by ORDFN, for whatever reason. Anyway, here is the
patch I'm currently experimenting with (it solves all the issues
reported by Stavros and also the last example above, but in light of
the other example it is certainly far from being a complete solution.
It might even be totally wrong since I have no reason to believe that
it is more than a simple palliative and that it would make things more
consistent).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cut ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Index: simp.lisp
===================================================================
RCS file: /cvsroot/maxima/maxima/src/simp.lisp,v
retrieving revision 1.5
diff -C2 -r1.5 simp.lisp
*** simp.lisp 5 Mar 2003 01:36:26 -0000 1.5
--- simp.lisp 8 Aug 2003 19:10:57 -0000
***************
*** 1848,1854 ****
((MEMQ CX '(MPLUS MTIMES))
(COND ((MEMQ CY '(MPLUS MTIMES)) (ORDLIST (CDR X) (CDR Y) CX CY))
! ((ALIKE1 (SETQ U (CAR (LAST X))) Y) (NOT (ORDHACK X)))
! ((AND (EQ CX 'MPLUS) (EQ CY 'MEXPT) (MPLUSP (CADR Y)))
(NOT (ORDMEXPT Y X)))
(T (GREAT U Y))))
((MEMQ CY '(MPLUS MTIMES)) (NOT (ORDFN Y X)))
--- 1848,1854 ----
((MEMQ CX '(MPLUS MTIMES))
(COND ((MEMQ CY '(MPLUS MTIMES)) (ORDLIST (CDR X) (CDR Y) CX CY))
! ((AND (EQ CX 'MPLUS) (EQ CY 'MEXPT))
(NOT (ORDMEXPT Y X)))
+ ((ALIKE1 (SETQ U (CAR (LAST X))) Y) (NOT (ORDHACK X)))
(T (GREAT U Y))))
((MEMQ CY '(MPLUS MTIMES)) (NOT (ORDFN Y X)))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cut ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Robert Dodier - 2006-07-08
• labels: --> Lisp Core

• Robert Dodier - 2006-07-08

Logged In: YES
user_id=501686

Increasing the priority on this one -- potential for subtle
breakage in various contexts.

• Robert Dodier - 2006-07-08
• priority: 5 --> 7

• Dan Gildea - 2009-12-14

I think these issues are resolved in simp.lisp rev 1.93.

• Dan Gildea - 2009-12-14
• status: open --> pending

• SourceForge Robot - 2009-12-28
• status: pending --> closed

• SourceForge Robot - 2009-12-28

This Tracker item was closed automatically by the system. It was
previously set to a Pending status, and the original submitter
did not respond within 14 days (the time period specified by