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

Thomas Breuer thomas.breuer at math.rwth-aachen.de
Tue Oct 5 14:55:57 BST 2004

Dear GAP Forum,

Alastair Donaldson wrote

> 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?

In general there is not a unique largest subgroup of G
that does not map i to j.
For example, consider G a symmetric group on at least three points,
then the point stabilizers of i and j are two different subgroups
with the required property.

More generally, a collection of examples of subgroups with this propertyy
are the setwise stabilizers of those subsets of the moved points of G
that contain i but not j.
(Warwick Harvey mentioned stabilizers in his message.)

Interesting subgroups of this kind are the block stabilizers of
(maximal) blocks of imprimitivity containing i but not j;
if the group acts primitively then one gets just the point stabilizers
this way.

These subgroups can be computed quite efficiently.

By the way, the fact that a group contains an element that maps i to j
does not depend on the fact that the given generating set contains
an element with this property;
so omitting all generators with this property does not necessarily
yield a generating set for a group in which i and j lie in different
(And on the other hand, the subgroup obtained this way may be smaller
than the stabilizers mentioned above.)

All the best,

More information about the Forum mailing list