IteratorOfRightCongruences is generating relations which are not congruences

[joe-dw]

Specifically, if G is the graph inverse semigroup of Digraph([] , [1], [1]), then it generates the congruence with parts

[ [ All elements except ] , [ e_2 e_1 ^ -1] ]

Which is not closed, for instance (e_1 , e_2) * e_1^-1 = (e_1e_1^-1, e_2 e_1 ^ -1)

I will look further into this

[james-d-mitchell]

Thanks for the report @joe-dw, the issue is likely in the method for EquivalenceRelationPartition rather than the code actually generating things that aren't congruences.

[reiniscirpons]

Bonjour, I can't seem to reproduce, in particular when running

G := GraphInverseSemigroup(Digraph([[], [1], [1]]));
iter := IteratorOfRightCongruences(G);              
for cong in iter do
  Print(EquivalenceRelationPartitionWithSingletons(cong), "\n");
od;

I get the following output:

[ [ e_1, e_2, v_1, v_2, v_3, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ] ]
[ [ e_1, e_2, v_1, v_2, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_3 ] ]
[ [ e_1, e_2, v_1, v_3, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ] ]
[ [ e_1, e_2, v_1, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ], [ v_3 ] ]
[ [ e_1, e_2, v_1 ], [ v_2, e_1^-1, e_1e_1^-1, e_2e_1^-1 ], [ v_3, e_2^-1, e_1e_2^-1, e_2e_2^-1 ], [ 0 ] ]
[ [ e_1, e_2, v_1 ], [ v_2, e_1^-1, e_1e_1^-1, e_2e_1^-1 ], [ v_3 ], [ e_2^-1, e_1e_2^-1, e_2e_2^-1 ], [ 0 ] ]
[ [ e_1, e_2, v_1 ], [ v_2 ], [ v_3, e_2^-1, e_1e_2^-1, e_2e_2^-1 ], [ e_1^-1, e_1e_1^-1, e_2e_1^-1 ], [ 0 ] ]
[ [ e_1, e_2, v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1, e_1e_1^-1, e_2e_1^-1 ], [ e_2^-1, e_1e_2^-1, e_2e_2^-1 ], [ 0 ] ]
[ [ e_1, e_2, v_2, v_3, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ e_1^-1 ], [ e_2^-1 ] ]
[ [ e_1, e_2, v_2, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ] ]
[ [ e_1, e_2, v_3, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2 ], [ e_1^-1 ], [ e_2^-1 ] ]
[ [ e_1, e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2, e_1e_1^-1, e_2e_1^-1 ], [ v_3, e_1e_2^-1, e_2e_2^-1 ] ]
[ [ e_1, e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2, e_1e_1^-1, e_2e_1^-1 ], [ v_3 ], [ e_1e_2^-1, e_2e_2^-1 ] ]
[ [ e_1, e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2 ], [ v_3, e_1e_2^-1, e_2e_2^-1 ], [ e_1e_1^-1, e_2e_1^-1 ] ]
[ [ e_1, e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2 ], [ v_3 ], [ e_1e_1^-1, e_2e_1^-1 ], [ e_1e_2^-1, e_2e_2^-1 ] ]
[ [ e_1, e_2, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ] ]
[ [ e_1, e_2 ], [ v_1 ], [ v_2, e_1e_1^-1, e_2e_1^-1 ], [ v_3, e_1e_2^-1, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ] ]
[ [ e_1, e_2 ], [ v_1 ], [ v_2, e_1e_1^-1, e_2e_1^-1 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_2^-1, e_2e_2^-1 ] ]
[ [ e_1, e_2 ], [ v_1 ], [ v_2 ], [ v_3, e_1e_2^-1, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_1^-1, e_2e_1^-1 ] ]
[ [ e_1, e_2 ], [ v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_1^-1, e_2e_1^-1 ], [ e_1e_2^-1, e_2e_2^-1 ] ]
[ [ e_1, v_1, v_2, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_3, e_2e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1, v_1, v_2, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_3 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2, v_3, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2, e_1^-1, e_1e_1^-1 ], [ e_2^-1, e_1e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2, v_3, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ], [ e_1^-1, e_1e_1^-1 ], [ e_2^-1, e_1e_2^-1 ] ]
[ [ e_1, v_1, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_2 ], [ v_3, e_2e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1, v_1, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_2 ], [ v_3 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2, e_1^-1, e_1e_1^-1 ], [ v_3 ], [ e_2^-1, e_1e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2 ], [ v_2, e_1^-1, e_1e_1^-1 ], [ v_3, e_2e_2^-1 ], [ e_2^-1, e_1e_2^-1 ], [ 0 ], [ e_2e_1^-1 ] ]
[ [ e_1, v_1 ], [ e_2 ], [ v_2, e_1^-1, e_1e_1^-1 ], [ v_3 ], [ e_2^-1, e_1e_2^-1 ], [ 0 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ], [ v_3 ], [ e_1^-1, e_1e_1^-1 ], [ e_2^-1, e_1e_2^-1 ] ]
[ [ e_1, v_1 ], [ e_2 ], [ v_2 ], [ v_3, e_2e_2^-1 ], [ e_1^-1, e_1e_1^-1 ], [ e_2^-1, e_1e_2^-1 ], [ 0 ], [ e_2e_1^-1 ] ]
[ [ e_1, v_1 ], [ e_2 ], [ v_2 ], [ v_3 ], [ e_1^-1, e_1e_1^-1 ], [ e_2^-1, e_1e_2^-1 ], [ 0 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1, v_2, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2, v_1 ], [ v_3, e_2^-1, e_2e_2^-1 ], [ e_1^-1, e_2e_1^-1 ] ]
[ [ e_1, v_2, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2, v_1 ], [ v_3 ], [ e_1^-1, e_2e_1^-1 ], [ e_2^-1, e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1, v_3, e_1^-1, e_2^-1, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2, e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1, v_3, e_1^-1, e_2^-1, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1, e_1^-1, e_2^-1, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2, e_1e_1^-1 ], [ v_3 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1, e_1^-1, e_2^-1, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ], [ v_3 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2, v_1 ], [ v_2 ], [ v_3, e_2^-1, e_2e_2^-1 ], [ e_1^-1, e_2e_1^-1 ] ]
[ [ e_1 ], [ e_2, v_1 ], [ v_2, e_1e_1^-1 ], [ v_3, e_2^-1, e_2e_2^-1 ], [ e_1^-1, e_2e_1^-1 ], [ 0 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1 ], [ v_2 ], [ v_3, e_2^-1, e_2e_2^-1 ], [ e_1^-1, e_2e_1^-1 ], [ 0 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2, v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1, e_2e_1^-1 ], [ e_2^-1, e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1 ], [ v_2, e_1e_1^-1 ], [ v_3 ], [ e_1^-1, e_2e_1^-1 ], [ e_2^-1, e_2e_2^-1 ], [ 0 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1, e_2e_1^-1 ], [ e_2^-1, e_2e_2^-1 ], [ 0 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1, v_2, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_1 ], [ v_3, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1, v_2, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_1 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_3, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2, e_1e_1^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, v_3, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2 ], [ e_1^-1 ], [ e_2^-1 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2, e_1e_1^-1 ], [ v_3, e_2e_2^-1 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2, e_1e_1^-1 ], [ v_3 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2 ], [ v_3, e_2e_2^-1 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1, e_1^-1, e_2^-1, 0 ], [ v_2 ], [ v_3 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_1 ], [ v_2 ], [ v_3, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1, 0, e_1e_1^-1, e_1e_2^-1 ], [ e_2 ], [ v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2, e_1e_1^-1 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2, 0, e_2e_1^-1, e_2e_2^-1 ], [ v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1 ], [ v_2, e_1e_1^-1 ], [ v_3, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1 ], [ v_2, e_1e_1^-1 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1 ], [ v_2 ], [ v_3, e_2e_2^-1 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ] ]
[ [ e_1 ], [ e_2 ], [ v_1 ], [ v_2 ], [ v_3 ], [ e_1^-1 ], [ e_2^-1 ], [ 0 ], [ e_1e_1^-1 ], [ e_1e_2^-1 ], [ e_2e_1^-1 ], [ e_2e_2^-1 ] ]

Note in particular that the only two index 2 right congruences in the above list are:

[ [ e_1, e_2, v_1, v_2, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_3 ] ]
[ [ e_1, e_2, v_1, v_3, e_1^-1, e_2^-1, 0, e_1e_1^-1, e_1e_2^-1, e_2e_1^-1, e_2e_2^-1 ], [ v_2 ] ]

neither of which separates e_2e_1^{-1} from the rest. I am on 4.16dev of gap (most recent commit) and the most recent commit c354521 of Semigroups.

@joe-dw could you run the gap code snippet above and post what you get? Also, what gap version and Semigroups version are you using?

[james-d-mitchell]

I'm also now not able to reproduce this, although I thought I could before. Not sure what to do next.