This section describes the various homomorphisms that are treated specially for permutation groups.
GroupHomomorphisByImages( P, H, gens, imgs )
The group homomorphism of a permutation group P into another group H
is handled especially by GroupHomomorphisByImages
. Below we describe
how the various mapping functions are implemented for such a group
homomorphism ghom. The mapping functions not mentioned below are
implemented by the default functions described in
GroupHomomorphismByImages.
To work with ghom, a stabilizer chain for the source of ghom is
computed and stored as ghom.orbit
, ghom.transversal
,
ghom.stabilizer
. For every stabilizer stab in the stabilizer chain
there is a list parallel to stab.generators
, which is called
stab.genimages
, and contains images of the generators. The
stabilizer chain is computed with a random Schreier Sims algorithm, using
the size of the source to know when to stop.
IsMapping( ghom )
To test if ghom is a (single valued) mapping, all Schreier generatores are computed. Each Schreier generator is then reduced along the stabilizer chain. Because the chain is complete, each one must reduce to the identity. Parallel the images of the strong generators are multiplied. If they also reduce to the identity (in the range), ghom is a function, otherwise the remainders form a normal generating set for the subgroup of images of the identity of the source.
Image( ghom, elm )
The image of an element elm can be computed by reducing the element along the stabilizer chain, and at each step multiplying the corresponding images of the strong generators.
CompositionMapping( hom, ghom )
The composition of an arbitrary group homomorphism hom and ghom the
stabilizer chain of ghom is copied. On each level the images of the
generators in stab.genimages
are replaced by their images under
hom.
OperationHomomorphism( P, Operation( P, list ) )
The operation of a permutation group P on a list list of integers is
handled especially by OperationHomomorphism
. (Note that list must be
a union of orbits of P for Operation
to work.) We call the resulting
homomorphism a transitive constituent homomorphism. Below we describe
how the various mapping functions are implemented for a transitive
constituent homomorphism tchom. The mapping functions not mentioned
below are implemented by the default functions described in
OperationHomomorphism.
Image( tchom, elm )
The image of an element is computed by restricting elm to list (see
RestrictedPerm) and conjugating the restricted permutation with
tchom.conperm
, which maps it to a permutation that operates on
[1..Length(list)]
instead of list.
Image( tchom, H )
The image of a subgroup H is computed as follows. First a stabilizer chain for H is computed. This stabilizer chain is such that the base starts with points in list. Then the images of the strong generators of sub form a strong generating set of the image.
PreImages( tchom, H )
The preimage of a subgroup H is computed as follows. First a stabilizer chain for the source of tchom is computed. This stabilizer chain is such that the base starts with the point in list. Then the kernel of tchom is a stabilizer in this stabilizer chain. The preimages of the strong generators for H together with the strong generators for the kernel form a strong generating set of the preimage subgroup.
OperationHomomorphism( P, Operation( P, blocks, OnSets ) )
The operation of a permutation group P on a block system blocks (see
Blocks) is handled especially by OperationHomomorphism
. We call the
resulting homomorphism a blocks homomorphism. Below we describe how
the various mapping functions are implemented for a blocks homomorphism
bhom. The mapping functions not mentioned below are implemented by the
default functions described in OperationHomomorphism.
Image( bhom, elm )
To compute the image of an element elm under bhom, the record for
bhom contains a list bhom.reps
, which contains for each point in
the union of the blocks the position of this block in blocks. Then the
image of an element can simply be computed by applying the element to a
representative of each block and using bhom.reps
to find in which
block the image lies.
Image( bhom, H )
PreImage( bhom, elm )
PreImage( bhom, H )
Kernel( bhom )
The image of a subgroup, the preimage of an element, and the preimage of a subgroup are computed by rather complicated algorithms. For a description of these algorithms see But85a.
GAP 3.4.4