MaximalSubsemigroups for Inverse Semigroups

Issue #63 resolved
wilfwilson
created an issue

The issue which arised at the end of Wednesday's meeting, and James recommended I raise an issue:

Calling MaximalSubsemigroups of this inverse semigroup gives an error:

gap> S:=Semigroup(
>  [ PartialPerm( [ 1, 2, 3, 4, 5 ], [ 2, 6, 4, 1, 5 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5 ], [ 4, 1, 6, 3, 2 ] ),
>  PartialPerm( [ 1, 2, 5 ], [ 4, 3, 2 ] ),
>  PartialPerm( [ 1, 2, 6 ], [ 2, 1, 3 ] ),
>  PartialPerm( [ 1, 2, 4, 5, 6 ], [ 4, 1, 3, 5, 2 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 5, 4, 1, 3 ] ),
>  PartialPerm( [ 2, 3, 4 ], [ 5, 2, 1 ] ),
>  PartialPerm( [ 1, 2, 3 ], [ 2, 1, 6 ] ) ]);;
gap> MaximalSubsemigroups(S);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `[]' on 2 arguments called from
htvalue( oht, lambda( x ) ) called from
Enumerate( data, infinity, lookfunc ) called from
gens[i] in s called from
SemigroupByGenerators( out, arg[i] ) called from
Semigroup( V, tuples, rec(
    small := true ) ) called from
...  at line 26 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

This was the first time I ran MaximalSubsemigroups algorithm on an inverse semigroup of partial permutations.

This problem is in the maximal branch

Comments (7)

  1. James Mitchell repo owner

    This boils down to:

    gap> S:=Semigroup(PartialPerm( [ 1, 2, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ] ) );
    <trivial partial perm group on 5 pts with 0 generators>
    gap> T:=Monoid(S,  PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 5, 4, 1, 3 ] ));
    <commutative partial perm monoid on 6 pts with 1 generator>
    gap> GeneratorsOfSemigroup(T);
    [ <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]>, [6,3,4,1,2,5] ]
    

    The generators of T should be

    <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]>, 
    <identity partial perm on [ 1, 2, 4, 5, 6 ]>, 
    [6,3,4,1,2,5] 
    
  2. James Mitchell repo owner

    The same bug affects InverseSemigroup and InverseMonoid

    gap> S:=InverseSemigroup(PartialPerm( [ 1, 2, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ] ) );
    <trivial partial perm group on 5 pts with 0 generators>
    gap> T:=InverseMonoid(S,  PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 5, 4, 1, 3 ] ));
    <inverse partial perm monoid on 6 pts with 1 generator>
    gap> One(T);
    <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]>
    gap> One(S);
    <identity partial perm on [ 1, 2, 4, 5, 6 ]>
    gap> One(S) in T;
    false
    

    This is a bug in the library code, which I've fixed but will push tomorrow, when I've added some tests, and checked the old tests.

  3. James Mitchell repo owner

    I fixed the particular bug that cased the original error, but then discovered another bug, which boils down to:

    gap> gens:=[ PartialPerm( [ 1, 2, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ] ), 
    >  PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 5, 4, 1, 3 ] ) ];;
    gap> s:=Semigroup(gens[1]);
    <trivial partial perm group on 5 pts with 0 generators>
    gap> o:=LambdaOrb(s);
    <open orbit, 1 points with Schreier tree with log>
    gap> Enumerate(o);
    <closed orbit, 2 points with Schreier tree with log>
    gap> AddGeneratorsToOrbit(o, [gens[2]]);
    <closed orbit, 12 points with Schreier tree with log>
    gap> s:=Semigroup(gens[1]);
    <trivial partial perm group on 5 pts with 0 generators>
    gap> gens[1] in s;
    true
    gap> o:=LambdaOrb(s);
    <closed orbit, 2 points with Schreier tree with log>
    gap> AddGeneratorsToOrbit(o, [gens[2]]);
    <closed orbit, 8 points with Schreier tree with log>
    gap> 
    

    I think this is triggered by the Orb package not closing the log properly when it is looking for something in Enumerate. I will investigate more.

  4. Log in to comment