Dear GAP-Forum,
Guido Helmers asked:
My problem is the following:
I try to find all the triples of generators of the two-dimensional
special linear group over a finite field (say G:= SL(2, GF(p^n))),
upto automorpism of these triples, and such that the product of the
three generators equals 1; my question is:
I assume that you want to classify these triples regarding the ordering
(i.e. [a,b,c] will be different than [c,b,a]), otherwise things become a bit
more complicated.
For a fixed finite group G (in my case a matrix group); a fixed number m (in my case 2 or 3); and fixed numbers a1,..am (dividing Size(G)), what is the quickest way to find, for example, the set (1) {{g1,..,gm} \in Gx..xG| <g1,..,gm>=G and ord(gi)=ai for all i} (2) {{g1,..,gm} \in Gx..xG| <g1,..,gm>=G and g1...gm=1 and ord(gi)=ai for all i}or, if no function exists which returns such m-tuples given a1,..,am
(3) to find the set of ALL m-tuples of generators of G
Marston Conder already mentioned that in case (2) it is of sufficient to
classify m-1-tuples and take g_m to be the inverse of the product (one can
then discard those m,-q-tuples whose product does not have the right order).
He also mentioned that this classification for pairs means to classify
g_1 up to conjugacy and then for each g_1 the possible g_2 up to C(g_1)
conjugacy.
These classes under a subgroup can be obtained by taking
representatives h_2 of all classes and then conjugating each h_2 with
representatives of the double cosets C(h_2)\G/C(g_1).
This process then must be iterated for m-tuples for m>2.
I happen to have written such an algorithm for pairs some months ago for
someone else. I append its code, it should be easy to adapt it to find only
generators of restricted orders.
(Blatant self-advertisement:
If you are able to read German, you can find a more detailled description
of such an algorithm in my PhD thesis (section V.5), which you can find at
http://www-gap.dcs.st-and.ac.uk/~ahulpke/paper/prom.ps.gz)
An algorithm of this type (working for arbitrary m-tuples) is for example
also used by GAP to compute the automorphism group in the nonsolvable case.
If this would be of help, I can tell you how to interface to this algorithm
directly. (If interested send me an eMail.)
I hope this is of help,
Alexander Hulpke
# g: permutation group or Ag group
# this function computes the automorphism group of g and then classifies all
# generating pairs of g up to automorphisms.
# ahulpke, 2-dec-1997
GeneratingPairsModuloAut := function(g)
local a, # automorphism group
ap, # perm rep.
agensimgs,# images of the generators in perm rep
ahom, # a->ap
dom, # Elements(g)
orb,transversal,s,img, # orbit-stabilizer algorithm
i,j,k, # loop
dc, # double cosets
cl, # a-classes
p, # position, pairs
e1,e2; # generators
a:=AutomorphismGroup(g);
ap:=a.permGroup;# mapping into permutation group
# we can cheaply compute preimages under this hom, for images the function
# 'PermAutImg' is much better, however.
agensimgs:= List(a.generators,i->PermAutImg(a.elms,i));
ahom:=GroupHomomorphismByImages(a,ap,a.generators,agensimgs);
ahom.isMapping:=true;# compute automorphism-fused classes via orbit/stabilizer algorithm # cl is a list with entries [representative\in g, stabilizer in perm rep] dom:=Elements(g); cl:=[]; while Length(dom)>0 do orb:=[dom[1]]; transversal:=[()]; # permutation transversal! s:=TrivialSubgroup(ap); i:=1; while i<=Length(orb) do for j in [1..Length(a.generators)] do img:=orb[i]^a.generators[j]; p:=Position(orb,img); if p<>false then # grow stabilizer s:=Closure(s,transversal[i]*agensimgs[j]/transversal[p]); else # grow orbit Add(orb,img); Add(transversal,transversal[i]*agensimgs[j]); fi; od; i:=i+1; if Length(orb)*Size(s)=Size(ap) then i:=Length(orb)+1; # break if we know we are finished fi; od; Add(cl,[orb[1],s]); dom:=Difference(dom,orb); od;#classify pairs up to conjugacy p:=[]; for i in cl do e1:=i[1]; for j in cl do # calculate double cosets in permutation rep. dc:=DoubleCosets(ap,j[2],i[2]);
# transfer representatives back dc:=List(dc,i->PreImagesRepresentative(ahom,Representative(i))); for k in dc do e2:=j[1]^k; if Size(Subgroup(g,[e1,e2]))=Size(g) then # generating pair, store preimages Print("Found pair ",[e1,e2],"\n"); Add(p,[e1,e2]); fi; od; od; od; return p; end;