Incorrect results in MaximalSubsemigroups

[wilfwilson]

Whilst investigating the maximal subsemigroups of the inverse monoid PORI_n, I have discovered a problem with my code.

There are maximal subsemigroups of PORI_n which arise from the group of units (no problem there), and some which arise from the D-classes of elements of rank n-1 (these are the problem ones). The MaximalSubsemigroups code is missing some maximal subsemigroups of this type which intersect every H-class. Since it does not find them, it believes that the subsemigroup formed by removing this entire D-class is maximal, which is not the case.

I currently do not know why this is occurring. I hope it's nothing disastrous.

gap> S := Monoid( [ PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 2, 3, 4, 5, 6, 1 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5 ], [ 1, 2, 3, 4, 6 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 6 ], [ 1, 2, 3, 4, 5 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 6, 5, 4, 3, 2, 1 ] ) ] );; # PORI_6
gap> U := InverseMonoid( [ PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 6, 1, 2, 3, 4, 5 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 3, 2, 1, 6, 5, 4 ] ),
>  PartialPerm( [ 2, 3, 4, 5, 6 ], [ 2, 3, 4, 5, 6 ] ),
>  PartialPerm( [ 2, 3, 5, 6 ], [ 6, 5, 4, 3 ] ),
>  PartialPerm( [ 2, 3, 4, 6 ], [ 5, 4, 1, 6 ] ) ] );;
gap> IsMaximalSubsemigroup(S, U);
true
gap> U in MaximalSubsemigroups(S);
false
gap> V := InverseMonoid( [ PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 2, 3, 4, 5, 6, 1 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 6, 5, 4, 3, 2, 1 ] ),
>  PartialPerm( [ 1, 2, 3, 4 ], [ 1, 4, 3, 2 ] ),
>  PartialPerm( [ 1, 2, 3, 4 ], [ 3, 2, 6, 5 ] ),
>  PartialPerm( [ 1, 2, 3, 4 ], [ 3, 5, 6, 1 ] ) ] );;
gap> IsMaximalSubsemigroup(S, V);
false
gap> V in MaximalSubsemigroups(S);
true
gap> IsSubsemigroup(U, V);
true

[wilfwilson]

Also, for PORI_16, there should (I believe) be two maximal subsemigroups arising from the 2nd D-class. It finds the first, max_1, but not the second, max_2.

gap> PORI_16 := Monoid(
> [ PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
>      [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16 ],
>      [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ] ) ] );;
gap> max_1 := InverseMonoid(
> [ PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16 ],
>      [ 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
>      [ 3, 2, 1, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ],
>      [ 4, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6 ] ) ] );;
gap> max_2 := InverseMonoid(
> [ PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
>      [ 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
>      [ 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] ),
>   PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ],
>      [ 13, 15, 16, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ] ),
>   PartialPerm( [ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16 ],
>      [ 1, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2 ] ) ] );;

[james-d-mitchell]

Any idea what's going on? Have you checked that you get the same (wrong) results in Semigroups 2.8.1? Could this be caused by some unrelated problem in unstable-3.0?

[wilfwilson]

I haven't looked deeply into the problem yet, but I'm pretty sure it's my fault. PORI_16 has 9,617,257,185 elements so there's no chance that it would terminate in 2.8.1. So I can't verify the situation there. However PORI_6 only has 5059 elements, and so I can confirm that 2.8.1 gives the correct result.

That's not too surprising, since almost none of the maximal subsemigroups code from 2.8.1 is present in unstable-3.0. The relevant case now involves calculating the maximal subsemigroups of a Rees 0-matrix semigroup which contain a particular set of elements. This is the most complicated part of the algorithm and the only part which we don't have written up formally, so I think it's most likely that I've just coded something wrongly here.

I'll sort it out tomorrow.

[wilfwilson]

More details:

gap> G := Group([(1, 5, 4, 3, 2), (1, 5)(2, 4)]);; # D_5
gap> mat := [
> [(), 0, 0, 0, 0, 0],
> [0, (), 0, 0, 0, 0],
> [0, 0, (), 0, 0, 0],
> [0, 0, 0, (), 0, 0],
> [0, 0, 0, 0, (), 0],
> [0, 0, 0, 0, 0, ()]];; # Normalized matrix
gap> R := ReesZeroMatrixSemigroup(G, mat);;

R is (isomorphic to) the principal factor of the J-class of PORI_6 containing elements of rank 5

gap> gens := [
>  RMSElement(R, 1,(),6),
>  RMSElement(R, 1,(1,5,4,3,2),2),
>  RMSElement(R, 1,(1,5,4,3,2),3),
>  RMSElement(R, 1,(1,5,4,3,2),4),
>  RMSElement(R, 1,(1,5,4,3,2),5),
>  RMSElement(R, 1,(1,5)(2,4),1),
>  RMSElement(R, 2,(1,2,3,4,5),1),
>  RMSElement(R, 3,(1,2,3,4,5),1),
>  RMSElement(R, 4,(1,2,3,4,5),1),
>  RMSElement(R, 5,(1,2,3,4,5),1),
>  RMSElement(R, 6,(),1)];;
gap> M := Semigroup(gens);;
gap> IsMaximalSubsemigroup(R, M);
true
gap> ForAll(HClasses(R), x -> not IsEmpty(Intersection(x, M)));
true
gap> contain := [
>  RMSElement(R, 1,(1,5)(2,4),6),
>  RMSElement(R, 1,(),6),
>  RMSElement(R, 2,(1,2,3,4,5),1),
>  RMSElement(R, 2,(),5),
>  RMSElement(R, 3,(),2),
>  RMSElement(R, 3,(1,3)(4,5),4),
>  RMSElement(R, 4,(),3),
>  RMSElement(R, 4,(1,3)(4,5),3),
>  RMSElement(R, 5,(1,3)(4,5),4),
>  RMSElement(R, 5,(),2),
>  RMSElement(R, 6,(1,5,4,3,2),5),
>  RMSElement(R, 6,(),1)];;
gap> IsSubset(M, contain);
true

M is a maximal subsemigroup of R which intersects every H-class of R non-trivially, and which contains the set contain...

gap> max := MaximalSubsemigroups(R, rec(types := [6], contain := contain));
[  ]
gap> M in max;
false

...but M is not found by the MaximalSubsemigroups code. The following line executes correctly:

gap> M in MaximalSubsemigroups(R, rec(types := [6]));
true

Therefore the error is in the handling of finding those maximal subsemigroups of types 6 which contain a given set, as I expected.

[wilfwilson]

Fixed by PR 232.