Documentation: Clarify meaning of `IsAssocWord`, `IsAssocWordWithOne`, `IsAssocWordWithInverse`

[TWiedemann]

Somewhat related to #5991.

The documentation claims that

IsAssocWord is the category of associative words in free semigroups, IsAssocWordWithOne is the category of associative words in free monoids (which admit the operation One (31.10-2) to compute an identity), IsAssocWordWithInverse is the category of associative words in free groups (which have an inverse).

I think this should imply that any x (except possibly the empty word) can satisfy at most one of the statements IsAssocWord(x), IsAssocWordWithOne(x), IsAssocWordWithInverse(x): Free groups are neither free monoids nor free semigroups, and free monoids are not free semigroups. However, this is not the case:

gap> F := FreeGroup(2);;
gap> IsAssocWord(F.1);
true
gap> IsAssocWordWithInverse(F.1);
true
gap> IsAssocWordWithOne(F.1);
true

Indeed, the relevant definitions in the code are the following: https://github.com/gap-system/gap/blob/8c0b08cd9b029c711b742c36626915b3c56a3a14/lib/word.gd#L141-L144 https://github.com/gap-system/gap/blob/8c0b08cd9b029c711b742c36626915b3c56a3a14/lib/wordass.gd#L109-L114 https://github.com/gap-system/gap/blob/8c0b08cd9b029c711b742c36626915b3c56a3a14/lib/grpfree.gd#L29

I think the documentation should state that

• IsAssocWordWithInverse is the category of elements of free groups,
• IsAssocWordWithOne is the category of elements of free groups and free monoids,
• IsAssocWord is the category of elements of free groups, free monoids and free semigroups.

@ThomasBreuer Is this correct?

[ThomasBreuer]

What about the following:

Elements of free groups lie in IsAssocWordWithInverse. Elements of free monoids lie in IsAssocWordWithOne. Elements of free semigroups lie in IsAssocWord.

Or perhaps it is better to talk about groups/monoids/semigroups created with FreeGroup/FreeMonoid/FreeSemigroup, since the monoid generated by the free generators of a free group is a free monoid, and the semigroup generated by the free generators of a free monoid or a free group is a free semigroup.

[TWiedemann]

What about the following:

Elements of free groups lie in IsAssocWordWithInverse. Elements of free monoids lie in IsAssocWordWithOne. Elements of free semigroups lie in IsAssocWord.

That would be inconsistent with the way it works for nonassociative words, however, wouldn't it? There IsNonAssocWordWithInverseand IsNonAssocWordWithOne imply IsNonAssocWord.

Since we already have IsElementOfFreeGroup, I would find it more natural to call the filters you describe IsElementOfFreeGroup/Monoid/Semigroup and to let IsAssocWord include IsAssocWordWithOne/Inverse and to let IsAssocWordWithOne include IsAssocWordWithInverse.

Or perhaps it is better to talk about groups/monoids/semigroups created with FreeGroup/FreeMonoid/FreeSemigroup, since the monoid generated by the free generators of a free group is a free monoid, and the semigroup generated by the free generators of a free monoid or a free group is a free semigroup.

Good point. Similarly, Z is isomorphic to the free group on one generator, but its elements should not be regarded as associative words.

[ThomasBreuer]

Similarly, Z is isomorphic to the free group on one generator, but its elements should not be regarded as associative words.

On the one hand, one has to distinguish between abstract/mathematical properties (like being a free group) and properties inherited by a particular implementation of elements (like being a permutation group). On the other hand, for example GAP's definition of IsFreeGroup does not express the abstract property but simply describes a group whose elements are suitable words. (Note that in most cases, calling IsFreeGroup for an object does not trigger a computation, the only part of IsFreeGroup that can be computed because it is not yet known is whether the argument is associative.)

[ThomasBreuer]

Elements of free groups lie in IsAssocWordWithInverse. Elements of free monoids lie in IsAssocWordWithOne. Elements of free semigroups lie in IsAssocWord.

That would be inconsistent with the way it works for nonassociative words, however, wouldn't it? There IsNonAssocWordWithInverse and IsNonAssocWordWithOne imply IsNonAssocWord.

We have the implications IsAssocWordWithInverse => IsAssocWordWithOne => IsAssocWord, and we have the implication IsNonAssocWordWithOne => IsNonAssocWord. (There is no IsNonAssocWordWithInverse. And IsElementOfFreeGroup is an undocumented synonym of IsAssocWordWithInverse.)

Perhaps the point is that for example the element x^-1, where x is a generator of a free group, lies in IsAssocWord but will not appear as an element of a free semigroup? I see no problem with that.

From my point of view, the IsX filters in question shall express that multiplication of two objects in the filter is supported, the IsXWithOne filters shall express that additionally One is supported, and the IsXWithInverse filters shall express that additionally Inverse is supported. In order to model the situation that invertibility can/shall be checked only at runtime, "support for Inverse" does not mean that the existence of an inverse is guaranteed. Ideally, the meaning should be that calling Inverse with an object that has the IsXWithInverse filter yields fail if no inverse exists, that is, one can rely on not getting an error message.

However, we are not in this ideal situation. In some cases, methods for inverting have been installed independent of the filter setup. An example is the \^ method for IsNonassocWord mentioned in #5991. In other cases, IsMultiplicativeElementWithInverse is set for an object that is not invertible but calling Inverse with this objects throws an error. A prominent example are matrices that are implemented as plain lists: Even non-square matrices lie in the filter IsMultiplicativeElementWithInverse; this is because we want the filter for square matrices, and we cannot distinguish square and non-square matrices via their types (for performance reasons). Trying to invert a square singular matrix yields fail, trying to invert a non-square matrix throws an error.

gap> Inverse( [ [ 0 ] ] );
fail
gap> Inverse( [ [ 0, 1 ] ] );
Error, Matrix INV: <mat> must be square (not 1 by 2) in
[...]