NrCongruenceClasses gives incorrect answer

[james-d-mitchell]

I get the following:

gap> S := SmallSemigroup(4, 126);;
gap> rho := SemigroupCongruence(S, [[S.1, S.2]]);;
gap> NrCongruenceClasses(rho);
1

But if I do:

gap> T := AsSemigroup(IsTransformationSemigroup, S);;
gap> rho := SemigroupCongruence(T, [[T.1 ^ 2, T.1 ^ 3]]);;
gap> NrCongruenceClasses(rho);
2

I believe that the latter is correct, and the former is incorrect, and so the bug might be in GAP and not Semigroups. Note that the two congruences defined here are the same, although they look different.

[mtorpey]

I'm investigating this now. It seems to be a problem with how congruences over smallsemi semigroups are processed - I think singletons are being excluded from NrEquivalenceClasses for some reason.

gap> S := SmallSemigroup(4, 126);;
gap> cong := SemigroupCongruence(S, [[S.1, S.2]]);;             
gap> classes := EquivalenceClasses(cong);
[ <congruence class of s1> ]
gap> Elements(classes[1]);
[ s1, s2, s3 ]
gap> S.4 in classes[1];
false

Probably this sort of semigroup somehow got left behind when we implemented new congruence stuff in Semigroups. I'll keep investigating and post here when I work out more.

[mtorpey]

Yep, this is a case of the GAP code being used instead of our code, and the GAP code being incorrect.

The congruences code for generating pairs in our package (congpairs.gi) only applies to semigroups that satisfy IsEnumerableSemigroupRep or IsFpSemigroup or IsFreeSemigroup. Since small semigroups (IsSmallSemigroup) don't satisfy these, and since the one in question isn't simple or inverse or anything else useful, we just fall back to the code in GAP.

The code in GAP isn't totally stupid, but the method for EquivalenceClasses doesn't return singletons (it's like NonTrivialEquivalenceClasses in our package). That would be a reasonable choice, but it doesn't match what's written in the GAP manual, and it doesn't match what we do in Semigroups. Hence when you call NrCongruenceClasses it gets a list with just one class in it, and returns the number 1. All the right pairs are in the congruence, it's just the list of classes that's wrong.

One thing we could do is change the NrEquivalenceClasses method in cong.gi to check the number of elements which aren't represented in the EquivalenceClasses list. But that does seem like a bit of a hack...

[james-d-mitchell]

Let's go ahead with the hack solution @mtorpey, it'll work properly with both definitions (including and excluding singletons).

[mtorpey]

I'll be doing this in the meeting this afternoon.

[mtorpey]

This is done, by PR #462. I've tested it and your original post gives 2 both times. I'm closing this.