Fix associativity problems in domain constructions.

[ThomasBreuer]

This is a follow-up of pull request #4373, which itself fixes #4030.

Currently there are quite a few situations where GAP creates domains that claim to be associative although associativity does not hold for all triples of elements.

gap> T:= [ [ 1, 2, 6, 5, 4, 3 ], [ 2, 1, 4, 2, 2, 5 ], [ 6, 5, 1, 6, 6, 4 ],
>          [ 5, 6, 3, 4, 1, 2 ], [ 4, 3, 2, 1, 5, 6 ], [ 3, 4, 5, 3, 3, 1 ] ];;
gap> M:= MagmaByMultiplicationTable( T );
<magma with 6 generators>
gap> SemigroupByGenerators( M );
<semigroup with 6 generators>
gap> MonoidByGenerators( M );
<monoid with 6 generators>
gap> GroupByGenerators( M );
<group with 6 generators>
gap> Group( Elements( M ) );
<group with 6 generators>

It is not clear to me where the associativity checks should be inserted. Perhaps the real question is about the documentation: For group constructions, we have the plain function Group and the operations GroupByGenerators and GroupWithGenerators. The function Group calls IsGeneratorsOfMagmaWithInverses in order to check whether the given generators are allowed, and then calls GroupByGenerators. The two operations do not perform such checks. (The latter is crucial for example in situations where functions such as GL construct groups from huge matrices, which one does not want to check for invertibility. Note that we do not have something such as GroupNC or GroupByGeneratorsNC.) I think the associativity checks should happen where also the invertibility is checked, and the whole setup should become documented --thus now is the last chance to revise something.

[wilfwilson]

Thank you for raising this issue.

I'll note that the manual entries for the functions Semigroup and Monoid explicitly state that they don't test for associativity:

It is not checked whether the underlying multiplication is associative, use Magma and IsAssociative if you want to check whether a magma is in fact a semigroup.

It is not checked whether the underlying multiplication is associative, use MagmaWithOne and IsAssociative if you want to check whether a magma-with-one is in fact a monoid.

[ThomasBreuer]

I think it would be desirable if Semigroup, Monoid, and Group (and their underlying operations) would behave compatibly.

In the current setup, this would mean that the documentation of Group should state that the function makes no associativity checks, and how one can force such a check before creating the group object. The documentation of the three SomethingByGenerators functions should also state that they do not perform checks for associativity, or existence of an identity or inverses.

In this setup, the contradictory objects shown above arise from user errors, not from GAP errors. (Dangerous?)

I think GAP users do not expect this. A clean approach in the spirit of GAP would be to offer Group and GroupNC, etc., but currently we have only the NC variants, with wrong names.

How shall we proceed?

[wilfwilson]

The most important things are that:

1. The documentation matches the behaviour, and is clear and explicit about the behaviour.
2. The functions for the different kinds of objects (groups, monoids, semigroups) are consistent in what they do and don't test.
3. The functions give descriptive error messages when they perform a test that fails.

I hope that that is not controversial.

This is my opinion:

I think that it is dangerous for the most visible user-facing, friendly, 'default' functions (Group, Monoid, Semigroup) to produce wrong results (as in the first post of this issue), even if it is because of user error. Therefore, I think these functions should test for associativity (and invertibility, for Group), and I think that NC versions should be introduced which do not perform these checks. I would be happy for this to apply to SomethingByGenerators too.

The NC versions should be mentioned in the documentation for the non-NC versions. Furthermore, perhaps Group (etc.) should give an Info statement if associativity is not already known, perhaps with a hint about the existence of the NC version, in case this associativity test is lengthy.

My (very possibly erroneous) assumption is that most beginner users of GAP will be creating groups/monoids/semigroups out of objects that have an inherently associative multiplication, and therefore will not suffer undue performance problems with this change. On the other hand, more advanced users will know to (consult the documentation and) try an NC version if they encounter unsatisfactory performance due to associativity checks.