[GAP Forum] How does the function "Minimum()" work?/Is CrcString deterministic?

[Alexander Hulpke]

Dear Forum, Dear Will Chen,

> However, in order to efficiently compute actions on representatives of
> equivalence classes, I'm using "Minimum" to choose "minimal
> representatives".
> 
> Ie, I often turn orbits consisting of elements of G into lists and then
> consider their minimum.
> 
> If O is an orbit of elements of G under some action, then what does
> Minimum(List(O)) really do? Is this minimum guaranteed to be unique? When I
> create the group G, is every element of G secretly assigned an integer
> "size", and Minimum is just tapping into that data?

GAP internally defines a total order for all (well, up to omissions and exceptions) objects, using the < and = operators.
Functions such as `Sort’, `Minimum’ etc. then just rely on this ordering.

For some objects (such as rational numbers, but *not* real cyclotomics) the ordering used coincides with the natural order, for some objects (polynomials, pemutations) it is based on a lexicographic ordering using the internal representation. For objects that do not have a unique representation (subgroups or cosets, say) the comparison is typically aiming to compare as sets of elements. This can come at a notable time cost (e.g. to compare permutation groups a lexicographically minimal generating set is computed). In some cases (e.g. elements of finitely presented groups) this can mean that the ordering used is dependent on the particular instance of the objects — Two different finitely presented groups with the same presentation might end up with incompatible element ordering.

If you have a collection of objects and want to know whether the `<‘ comparison is quick (say to choose whether sorting is worth), you can use `CanEasilySortElements’. For example (permutations are compared on their lexicographic image list. Elemebnts of an fp group require work):

gap> CanEasilySortElements(AlternatingGroup(5));
true
gap> CanEasilySortElements(Image(IsomorphismFpGroup(AlternatingGroup(5))));
false

> For example, when I type in PSU(n,q) or PSL(n,q) or AlternatingGroup(n),
> GAP seems to represent them as permutation groups. Is the representation of
> these common groups as permutation groups deterministic? When I type in
> PSU(...) or PSL(...), will I always get the same permutation group?

Within one release of GAP the construction is deterministic. If you are looking beyond one release we do not actively plan to change the choice of generators (and are not aware of any reason why we should do so), but neither have made a commitment to fix the current generators in perpetuity.

If you want to publish work that depends on a choice of generators, I would either describe the generators by properties or use ``standard’’ generators as have been classified in the literature, e.g.

MR1409225 (98e:20025) Reviewed 
Wilson, Robert A.(4-BIRM-SM)
Standard generators for sporadic simple groups. 
J. Algebra 184 (1996), no. 2, 505–515. 

Best,

   Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke