[GAP Forum] sorted index of group element

Sandeep Murthy sandeepr.murthy at gmail.com
Mon Feb 25 20:23:28 GMT 2013


Hi,

Perhaps PageSource( func ) is the function that is
relevant here.

The PageSource method, which accepts a function name,
will display its source code in a page-view:

gap> PageSource( MagmaElement );
Showing source in /Applications/GAP/gap4r5/lib/grptbl.gi (from line 162)

#############################################################################
##
#F  MagmaElement( <M>, <i> ) . . . . . . . . . .  <i>-th element of 
magma <M>
##
InstallGlobalFunction( MagmaElement, function( M, i )
     M:= AsSSortedList( M );
     if Length( M ) < i then
       return fail;
     else
       return M[i];
     fi;
end );


#############################################################################
##
#F  MagmaByMultiplicationTableCreator( <A>, <domconst> )
##
InstallGlobalFunction( MagmaByMultiplicationTableCreator,
     function( A, domconst )
     local F,      # the family of objects
           n,      # dimension of `A'
           range,  # the range `[ 1 .. n ]'
           elms,   # sorted list of elements
           M;      # the magma, result

     # Check that `A' is a valid multiplication table.
     if IsMatrix( A ) then
       n:= Length( A );
   -- <space> page, <n> next line, <b> back, <p> back line, <q> quit --

Sincerely, Sandeep.


Vipul Naik wrote:
> 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
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum



More information about the Forum mailing list