> < ^ 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,

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;

> < [top]