[GAP Forum] Ordering of group elements

[Alexander Hulpke]

Dear Forum,

William DeMeo wrote:
> Suppose instead we want the 8 element cyclic group to be represented
> with one generator.  We can do this as follows:
> 
> gap> f:= FreeGroup("x");
> <free group on the generators [ x ]>
> 
> gap> g:= f/[f.1^8];
> <fp group on the generators [ x ]>
> 
> gap> Elements(g);
> [ <identity ...>, x, x^2, x^4, x^3, x^-3, x^-2, x^-1 ]
> 
> AsSet or AsList or AsSortedList or AsSSortedList all give the same
> ordering of the group elements as does the Elements function.
> 

The comparison for elements of a finitely presented group is somewhat complicated because one cannot always guarantee an easy normal form. In particular we do not guarantee that such an element ordering is stable between different runs of GAP by default.

The questions are probably answered most easily by explaining what GAP does:

When asking to compare elements of an fp group, GAP will by default try to construct a faithful permutation representation (or isomorphism to a pc group). Comparison of elements then is based on the same comparison for the images of the elements. 
In the example this permutation representation probably does not use the default numbering:
gap> IsomorphismPermGroup(g);
[ x ] -> [ (1,2,4,6,8,7,5,3) ]
and thus looks strange.

What one could do it to tell GAP (before the first element comparison) to use normal forms:
gap> SetReducedMultiplication(g);

Then element comparison is instead based on comparison of the normal forms and might look more plausible. (The normal form uses a monoid with x^-1<x and length-lex ordering.)

gap> Elements(g);
[ <identity ...>, x^-1, x, x^-2, x^2, x^-3, x^3, x^4 ]

If you wanted a bespoke ordering, you could create a function fct(left,right) that implements this ordering and then (before ever asking for the ordering) install it as FpElementComparisonMethod for the elements family. E.g.

gap> a:=(1,2,3,4,5,6,7,8);
(1,2,3,4,5,6,7,8)
gap> myiso:=GroupHomomorphismByImages(g,Group(a),[g.1],[a]);;
gap> fct:=function(left,right) return Image(myiso,left)<Image(myiso,right);end;
function( left, right ) ... end
gap> SetFpElmComparisonMethod(FamilyObj(One(g)),fct);

gap> Elements(g);
[ <identity ...>, x, x^2, x^3, x^4, x^5, x^6, x^7 ]


Alternatively, you could install a bespoke normal form method (SetFpElementNFFunction) and force reduced multiplication (which then would use your normal form).

Admittedly either looks a bit overkill for cyclic groups, but the machinery is ste up for arbitrary finitely presented groups for whom this is a hard problem.

Best,

  Alexander Hulpke


> 
> Finally, here are my questions:
> 
> 
> Question 1: Why is the default ordering of the elements not one of the
> alternatives below?
> 
> [ <identity ...>, x, x^2, x^3, x^4, x^-3, x^-2, x^-1 ]
> 
> or
> 
> [ <identity ...>, x, x^2, x^3, x^4, x^5, x^6, x^7 ]
> 
> 
> Question 2: Suppose our application requires the group elements be
> listed in this "natural" way.  Is it possible to do this without
> having to inspect each group we use by hand?  In other words, is it
> possible to anticipate the ordering that GAP will use for a given
> group, so that we can write our programs accordingly?
> 
> 
> Question 3: Is there no conventional or "natural" ordering of elements
> for certain groups, in particular the cyclic groups?  And why does GAP
> prefer ...x^2, x^4, x^3... over ...x^2, x^3, x^4... in the example
> above?
> 
> 
> As another example, here is the cyclic group of order 16:
> 
> gap> g:= f/[f.1^16];
> <fp group on the generators [ x ]>
> 
> gap> Elements(g);
> [ <identity ...>, x, x^2, x^4, x^8, x^3, x^5, x^9, x^6, x^10, x^12,
> x^7, x^11, x^13, x^14, x^15 ]
> 
> 
> Thank you in advance for any suggestions or advice.  If there is no
> general way to anticipate how GAP will order elements of a group, then
> any comments on GAP's choice of element ordering for particular
> examples (like cyclic groups or symmetric groups) would be very much
> appreciated.
> 
> 
> Sincerely,
> 
> William
> 
> 
> --
>  William DeMeo
>  Department of Mathematics
>  University of South Carolina
>  1523 Greene Street
>  Columbia, SC 29208
>  USA
> 
>  phone: 803-261-9135
>  http://williamdemeo.org
>  http://williamdemeo.github.io/CV
> --
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum