Dear Gap-Forum,

Daniel Ruberman asked:

Dear Gap Forum: Is there an algorithm implemented in GAP for finding a
presentation for a finite permutation group, given its generators? I've
looked in the manual as best I can but didn't locate any relevant command.

At the moment, there is no 'official' command for computing a presentation
for a permutation group. However the routine which checks, whether a
'GroupHomomorphismByImages' is indeed an homomorphism basically computes a
presentation and can be almost abused for our purpose. Anyhow we need to
almost duplicate the routine, as we are forced otherwise to check inclusion in
subgroups of the free group (Instead of building a relator subgroup, we will
just create a relator list).
The following code will do this task (it is mainly 'borrowed' from the
homomorphism routines), it will also be included in the next version:

#############################################################################

CoKernelGens := function ( hom )
    local   C,          # cokernel of <hom>, result
            stb,        # stabilizer in the chain of <hom>
            bpt,        # basepoint of stabilizer
            elm,        # one schreier generator
            img,        # image of <elm> under <hom>
            i, k,       # loop variables
            oldhom;

# make sure we have a stabilizer chain for <hom>
if not IsBound( hom.stabilizer ) then
hom.operations.MakeMapping( hom );
fi;

# loop over the stabilizer chain
C := [];
oldhom:= hom;
while hom.generators <> [] do

# for all orbit points
for i in hom.orbit do

># and all generators
>for k in [ 1 .. Length(hom.generators) ] do

>># make the schreier generator and its image
>>img := hom.transimages[i];
>>elm := hom.transversal[i];
>>while i^elm <> hom.orbit[1] do
>> img := img * hom.transimages[i^elm];
>> elm := elm * hom.transversal[i^elm];
>>od;
>>img := img^-1 * hom.genimages[k];
>>elm := elm^-1 * hom.generators[k];

# divide the schreier generator through the stabilizer chain
stb := hom;
while stb.generators <> []
  and IsBound(stb.transversal[stb.orbit[1]^elm])  do
    bpt := stb.orbit[1];
    while bpt ^ elm <> bpt  do
        img := img * stb.transimages[bpt^elm];
        elm := elm * stb.transversal[bpt^elm];
    od;
    stb := stb.stabilizer;
od;

>># if the image is not trivial add it to the cokernel
>>if not img in C then
>> Add(C,img);
>>fi;

od;

od;

# go down to the next stabilizer
hom := hom.stabilizer;

od;

# return the cokernel
return Difference(C,[IdWord]);

end;

#############################################################################
##
#F  PermGroupOps.FpGroup( <U> ) . . . . . . . . . . presentation of a PermGrp
##
PermGroupOps.FpGroup := function( arg )
local U,gens,h,F;

# check trivial case
U:=arg[1];
if 0 = Length(U.generators) then
F:=FreeGroup(0);
F.relators:=[];
F.bijection:=GroupHomomorphismByImages(F,U,[],[]);
return F;
fi;

# Try to find suitable names for this generators.
if Length(arg) = 2 then
gens:=WordList(Length(U.generators), arg[2] );
else
gens:=WordList(Length(U.generators), "F" );
fi;

# compute the presentation
F:=Group( gens, IdWord );
h:=GroupHomomorphismByImages(U,F,U.generators,gens);
F.relators:=CoKernelGens(h);
h:=GroupHomomorphismByImages(F,U,gens,U.generators);
h.isMapping:=true;
h.isHomomorphism:=true;
F.bijection:=h;

# Return the presenation.
return F;

end;

#############################################################################

If you call F:=FpGroup(G);
then generators correspond (you might use F.bijection for automatic mapping)
and F.relators is a set of defining relators for the permutation group <G>.

Hope this helps,

Alexander Hulpke