[GAP Forum] sorted index of group element

[Vipul Naik]

Hi,

I'm not able to run ViewSource on GAP -- it does not recognize the command.

I'm using GAP 4.5.6.

Vipul

* Quoting Alexander Konovalov who at 2013-02-24 20:38:44+0000 (Sun) wrote
> 
> 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
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum