Bug in ClosureSemigroup?

Issue #47 resolved
wilfwilson
created an issue

I'm finding some subtle weirdness. I'm playing with the MaximalSubsemigroups code, and I tried a random example (the S below). The 3rd maximal subsemigroup of the output, which I call T, returns false on IsMaximalSubsemigroup, however it clearly is maximal.

gap> S:=Semigroup([ Transformation( [ 1, 2, 4, 6, 1, 6 ] ),
> Transformation( [ 1, 6, 1, 1, 6, 5 ] ),
> Transformation( [ 2, 6, 2, 4, 3, 2 ] ),
> Transformation( [ 4, 1, 3, 6, 1, 5 ] ),
> Transformation( [ 4, 1, 4, 2, 4, 2 ] ),
> Transformation( [ 6, 6, 4, 6, 1, 1 ] ) ]);
<transformation semigroup on 6 pts with 6 generators>
gap> Size(S);
1720
gap> T:=MaximalSubsemigroups(S)[3];;
gap> T;
<transformation semigroup on 6 pts with 9 generators>
gap> Size(T);
1718
gap> IsMaximalSubsemigroup(S,T);
false
gap> IsSemigroup(T);
true
gap> Size(Semigroup(T));
1718
gap> IsMaximalSubsemigroup(S,Semigroup(T));
true
gap> IsMaximalSubsemigroup(S,T);           
false
gap> w:=Filtered(S, x-> not(x in T or Semigroup(T, x)=S));
[ Transformation( [ 1, 5, 4, 6, 1, 6 ] ) ]
gap> w in T;
false
gap> w in Semigroup(T);
true

I can't make sense of it. T arises as the sole maximal subsemigroup corresponding to the maximal regular D-class, D-class with index 4, and is the type where you take a maximal subgroup of the principal factor.

I can only imagine that the bug comes from specifying the semigroup in the MaximalSubsemigroups code, and hence would be at this point:

Append(gens2, List(classes{po[i]}, Representative));
V:=SemigroupIdealByGenerators(S, gens2);
Add(out, Semigroup(GeneratorsOfSemigroup(V), 
OnTuples(Filtered(GeneratorsOfSemigroup(U), 
x-> not IsMultiplicativeZero(U, x)), inj), rec(small:=true)));

For the record, T is:

gap> T:=Semigroup([ Transformation( [ 1, 5, 3, 4, 5 ] ),
> Transformation( [ 6, 4, 3, 5, 4, 1 ] ),
> Transformation( [ 1, 2, 4, 6, 1, 6 ] ),
> Transformation( [ 1, 5, 1, 6, 3, 1 ] ),
> Transformation( [ 4, 1, 6, 5, 4, 5 ] ),
> Transformation( [ 2, 6, 2, 4, 3, 2 ] ),
> Transformation( [ 2, 1, 2, 4, 4, 2 ] ),
> Transformation( [ 4, 5, 4, 4, 5, 3 ] ),
> Transformation( [ 4, 4, 4, 5, 4, 3 ] ),
> Transformation( [ 6, 1, 6, 6, 4, 6 ] ),
> Transformation( [ 5, 6, 6, 6, 6, 1 ] ),
> Transformation( [ 4, 4, 5, 4, 3, 3 ] ) ]);

Although if you specify T like that, everything plays nicely.

Comments (8)

  1. James Mitchell repo owner

    Just to mention that this appears not to be connected with the maximal subsemigroups code but is probably an error in ClosureSemigroup:

    gap> S:=Semigroup([ Transformation( [ 1, 2, 4, 6, 1, 6 ] ),
    > Transformation( [ 1, 6, 1, 1, 6, 5 ] ),
    > Transformation( [ 2, 6, 2, 4, 3, 2 ] ),
    > Transformation( [ 4, 1, 3, 6, 1, 5 ] ),
    > Transformation( [ 4, 1, 4, 2, 4, 2 ] ),
    > Transformation( [ 6, 6, 4, 6, 1, 1 ] ) ]);
    <transformation semigroup on 6 pts with 6 generators>
    gap> T:=Semigroup([ Transformation( [ 1, 5, 3, 4, 5 ] ),
    > Transformation( [ 6, 4, 3, 5, 4, 1 ] ),
    > Transformation( [ 1, 2, 4, 6, 1, 6 ] ),
    > Transformation( [ 1, 5, 1, 6, 3, 1 ] ),
    > Transformation( [ 4, 1, 6, 5, 4, 5 ] ),
    > Transformation( [ 2, 6, 2, 4, 3, 2 ] ),
    > Transformation( [ 2, 1, 2, 4, 4, 2 ] ),
    > Transformation( [ 4, 5, 4, 4, 5, 3 ] ),
    > Transformation( [ 4, 4, 4, 5, 4, 3 ] ),
    > Transformation( [ 6, 1, 6, 6, 4, 6 ] ),
    > Transformation( [ 5, 6, 6, 6, 6, 1 ] ),
    > Transformation( [ 4, 4, 5, 4, 3, 3 ] ) ]);
    <transformation semigroup on 6 pts with 12 generators>
    gap> IsMaximalSubsemigroup(S, T);
    true
    gap> T:=Semigroup(T, rec(small:=true));
    <transformation semigroup on 6 pts with 11 generators>
    gap> IsMaximalSubsemigroup(S, T);
    false
    gap> w:=Filtered(S, x-> not(x in T or Semigroup(T, x)=S));                   
    [ Transformation( [ 5, 6, 1, 4, 5, 4 ] ) ]
    gap> w in T;
    false
    gap> IsMaximalSubsemigroup(S, Semigroup(T, w[1]));
    true
    gap> Size(Semigroup(T, w[1]));
    1718
    gap> w[1] in T;
    false
    gap> T:=Semigroup(T, rec(small:=true));
    <transformation semigroup on 6 pts with 10 generators>
    gap> Size(T);
    1718
    gap> w[1] in T;
    true
    gap> IsMaximalSubsemigroup(S, T);                 
    false
    gap> w:=Filtered(S, x-> not(x in T or Semigroup(T, x)=S));
    [ Transformation( [ 1, 5, 4, 6, 1, 6 ] ) ]
    
  2. James Mitchell repo owner

    resolves Issue #47.

    This was caused by a bug in ClosureSemigroup which assume that if the rank of an R-class rep was greater than the maximum rank of the collection being added, then we hadn't seen an R-class rep with the same rho-value before.

    → <<cset 9ec23e5e00b9>>

  3. Log in to comment