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

[Thomas Breuer]

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
orbits.
(And on the other hand, the subgroup obtained this way may be smaller
than the stabilizers mentioned above.)

All the best,
Thomas