[GAP Forum] Computing a subgroup of G which does not map i to j
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
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