On 23 Feb 2013, at 19:02, Cotton Seed<cot...@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@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
