[GAP Forum] Computing a subgroup of G which does not map i to j

Alastair Donaldson ally at dcs.gla.ac.uk
Tue Oct 5 10:47:08 BST 2004

Thanks to everyone for their useful comments on my problem.  I appreciate 
that the set of elements that doesn't map i to j is not in general a 
group, and I'm sure that I do need a group for my purposes.

As someone pointed out I could just use the stabiliser of i, but this 
would potentially eliminate a lot of the group which I could have safely 
used, so a larger group would be preferrable.

I'm going to experiment with the various possibilities which have been 
proposed and I'll let the forum know if I have any success...


Ally Donaldson

On Fri, 1 Oct 2004 wh at icparc.ic.ac.uk wrote:

> Hi Alastair,
> As Dima Pasechnik noted, in general the set of elements which do not map i
> to j do not form a group.
> Do you really want a group of such elements?
> If not: there is one coset of the stabiliser of i which contains all the
> elements of G that map i to j; thus the elements that do not map i to j are
> all the other cosets.
> If so: if j = i there is nothing you can do.  :)  Otherwise, the stabiliser
> of i is a subgroup of G that does not map i to j.  There may be a larger
> subgroup with this property, depending on your group, consisting of this
> stabiliser and some of its cosets.  One naive way to look for a larger
> subgroup is to try adding to the stabiliser a representative for one of its
> cosets, and see whether j is in i's orbit in the resulting group.  If it is,
> try another representative.  If not, you have a larger subgroup with the
> desired property.  Repeat with a representative of a coset which is disjoint
> from the new subgroup until further enlargement is not possible.  Lots of
> optimisations possible.  E.g. exploiting the fact that you can't put more
> than half the cosets of the stabiliser of i into the subgroup without
> necessarily including j in i's orbit (this assumes j appears in i's orbit in
> G, which you say is true for your case).  There may be much better
> approaches, but my knowledge of group theory is limited to the fairly simple
> stuff.  :)
> Cheers,
> Warwick
> On Fri, Oct 01, 2004 at 03:30:04PM +0100, Alastair Donaldson wrote:
> > Dear GAP forum
> > 
> > I have the following problem:  I have a permutation group G acting on the 
> > set 1..n, given by a set of generators.
> > 
> > I've discovered that one of the generators of G maps a certain value i to 
> > a certain value j, and that this is not suitable for my purposes.
> > 
> > I want a subgroup of G which does not map i to j.  I could throw away all 
> > generators that map i to j, but I'd probably lose most of the group then.
> > 
> > Is there an efficient way to compute generators for a "large" subgroup of 
> > G which has no element that maps i to j?
> > 
> > Thanks
> > 
> > Alastair.
> > 
> > _______________________________________________
> > Forum mailing list
> > Forum at mail.gap-system.org
> > http://mail.gap-system.org/mailman/listinfo/forum

More information about the Forum mailing list