Incorrect results from NaturalPartialOrder

[wilfwilson]

Let es be the semilattice of idempotents of the symmetric inverse monoid of degree 3:

gap> S := Semigroup(SymmetricInverseMonoid(3));;
gap> es := IdempotentGeneratedSubsemigroup(S);; 

es is mathematically an inverse semigroup, but GAP doesn't know yet that it's inverse. Therefore the method for NaturalPartialOrder that applies is the one on line 31 of attrinv.gi.

The following is what NaturalPartialOrder should actually show:

gap> es := Elements(es);; n := Size(es);;
gap> List([1..n], i -> Filtered([1..n], j -> i <> j and es[j] = es[i] * es[j]));
[ [  ], [ 1 ], [ 1 ], [ 1, 2, 3 ], [ 1 ], [ 1, 3, 5 ], [ 1, 2, 5 ], 
  [ 1, 2, 3, 4, 5, 6, 7 ] ]

(Since es is a semilattice, x NaturalLeq y if and only if x * y = x).

Bu the method gives an incorrect result:

gap> po := NaturalPartialOrder(es);
[ [  ], [ 1 ], [ 1 ], [ 1, 2, 3 ], [ 1 ], [ 1, 3, 5 ], [ 1, 5 ],
  [ 1, 2, 3, 4, 5, 6, 7 ] ]

This is wrong since 2 should be an entry of po[7], but it isn't:

gap> es[7] * es[2] = es[2];
true
gap> 2 in po[7];
false

If we instead represent es by block bijections, then we should expect the same answer (up to a permutation). But it's totally different:

gap> es := IdempotentGeneratedSubsemigroup(S);;
gap> es := AsSemigroup(IsBlockBijectionSemigroup, es);;
gap> NaturalPartialOrder(es);
[ [  ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2, 3, 4, 5, 6, 7 ] ]

The culprit is line 50 in attrinv.gi:

p := Sortex(elts, IsGreensDGreaterThanFunc(S)) ^ -1;

We're trying to pre-sort the elements by D-order, but according to the documentation Sortex (and Sort, etc) require a strict less-than function to work (I'm unsure whether they work with less than or equal). It seems like they certainly don't work with greater-than.

I'll do what I can to fix/improve the code.

[wilfwilson]

(This bug is what is causing Travis to fail for my PR #388).

[james-d-mitchell]

Resolved by #390