> < ^ Date: Thu, 09 Jul 1998 09:37:11 +0100 (BST)
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
^ Subject: re: generators of SL(2, GF(q))

Dear GAP-Forum,

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.

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
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;
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");