> < ^ Date: Tue, 24 Nov 1998 10:47:21 +0000 (GMT)
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
< ^ Subject: Re: Schreier generators

Dear Gap-Forum,

J"urgen Ecker asked:

is there a function in GAP4 which explicitely computes a set of Schreier
generators, given a group (by a set of generators) and a set of right
coset representatives?

(In a private mail J"urgen clarified that he is interested in getting a
small subset of the Schreier generators which are sufficient to generate the
subgroup and that he is mainly interested in permutation groups.)

There is no predefined function that does this (this problem might come in
many variations, depending on whether you want a particular transversal or
whether you want all Schreier generators, so I have difficulties of
imagining a suitable definition of such an operation), but it is quite easy
to build this functionality yourself:

For `RightTransversal's in permutation groups and Pc groups the function
`PositionCanonical' will return the position of the representative which
defines the same coset (this is a feature which is new in GAP4).
Using this operation we can use a simple loop to get
all Schreier generators:

function AllSchreierGenerators(gens,transversal)
local sgens,t,g,e,p;
sgens:=[];
for t in transversal do
for g in gens do
e:=t*g;
p:=PositionCanonical(transversal,e); # representative index
Add(sgens,e/t[p]); # probably also store which Schreier generator
od;
od;
return sgens;
end;

What I don't know is whether you also want to know how each of the elements
is expressed as a Schreier generator, if yes you will have to add some
code.

The list <sgens> computed by this function is (by Schreier's theorem) a
generating set for the subgroup but it might be very redundant. If you only
want to get a small subset that generates the whole group I would suggest
the following approach:

 U:=TrivialSubgroup();
 for t in transversal do
   for g in gens do
     e:=t*g;
     p:=PositionCanonical(transversal,e); # representative index
     if not e/t[p] in U then
       # we found a new one, add to list
Add(sgens,e/t[p]);
     fi; 
   od;
 od;

Again, you might want to use a slight variation to keep track how these
elments are actually expressed as Schreier generators.

I hope this is of help,

Alexander


> < [top]