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

[wh at icparc.ic.ac.uk]

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