[GAP Forum] sorted index of group element

[Alexander Konovalov]

On 23 Feb 2013, at 19:02, Cotton Seed <cotton at alum.mit.edu> wrote:

> Is there way to get the sorted index of a group element?  More
> specifically, let G be a group, and g an element of G.  Is there a function
> that will give me the index i so that MagmaElement(G,i) = g?  Thanks!
> 
> Best,
> Cotton


Dear Cotton,

Let me first start with a hint how the source code of the MagmaElement 
function may be explored to find an answer, and then suggest a more 
efficient approach.

First, looking at the code of MagmaElement function - this may be done by 
typing `ViewSource(MagmaElement);' in GAP - you may spot the call to 
AsSSortedList:

InstallGlobalFunction( MagmaElement, function( M, i )
   M:= AsSSortedList( M );
   if Length( M ) < i then
     return fail;
   else
     return M[i];
   fi;
end );

Thus, MagmaElement returns the i-th element of AsSSortedList(M), where 
the latter contains all elements of M in strictly sorted order, w.r.t. 
the canonical ordering defined on M (depending on the type of M). 
Therefore, the index in which you're interested will be returned by 

Position( AsSSortedList( G ), g ) 

For example,

gap> G:=SmallGroup(8,3);
<pc group of size 8 with 3 generators>
gap> g:=Random(G);
f1*f3
gap> s:=AsSSortedList(G);;
gap> Position(s,g);
6
gap> MagmaElement(G,6);
f1*f3
gap> MagmaElement(G,6)=g;
true

Creating the list of all elements may not be very efficient, especially
when the group is very large. However, if the method for `Enumerator' 
exists for such a group (see `?Enumerator), then there is another
approach. Enumerator(G) need not to store its elements explicitly, 
but it knows how to determine the i-th element and the position of a 
given object. For example, this works:

gap> S:=SymmetricGroup(50);
Sym( [ 1 .. 50 ] )
gap> g:=Random(S);
(1,40,16,24,8,21,19,39,20,12,28,6)(2,5,49,3,45,4,30,25,13,11,47,44,36,9,50,43,
18,32)(7,46,22,15,35,41)(10,14,48,26,17)(23,42,33,29,37,38,27)
gap> enum:=Enumerator(S);
<enumerator of perm group>
gap> pos:=Position(enum,g);
19748951512546719853008099372809900742253637283670495935197327991
gap> enum[pos]=g;
true

while AsSSortedList(S) will run out of memory. There are methods for 
enumerators of various types of algebraic structures defined in the
GAP library.

Please note that the order in which MagmaElement and Enumerator will
sort elements of a domain sometimes may be different: the one for 
MagmaElement is determined by the '\<' relation defined on the domain, 
while the one for Enumerator depends on the algorithm used to enumerate
elements of a domain of some particular type. For example,

gap> F:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> AssignGeneratorVariables(F);
#I  Assigned the global variables [ a, b ]
gap> G:=F/[a^32,b^2,b^-1*a*b*a];
<fp group on the generators [ a, b ]>
gap> First([1..Size(G)],i -> not MagmaElement(G,i)=Enumerator(G)[i]);
3
gap> MagmaElement(G,3);
b
gap> Enumerator(G)[3];
a^-1

However, in most applications it is not the particular order that matters,
but the ability to determine the position of an element in the fixed 
list of elements, and to retrieve the i-th element of that list.

Hope this helps,
Alexander