4 Transversals of subgroups

for a transversal ss and group element elt, returns the representative of the coset containing the element elt. The representative is unique, i.e. TransversalElt will return the same thing for different elements of the same coset.

For a transversal ss and group element g, the following relationship with TransversalElt (see TransversalElt) defines SiftOneLevel:

SiftOneLevel(ss, g) = g * TransversalElt(ss, g)

For some kinds of transversal TransversalElt is more efficient, for others SiftOneLevel is.

4.2 Transversals by Schreier tree

For transversals of stabiliser subgroups, we store a Schreier tree to allow us to find transversal elements.

Note: SiftOneLevel is more efficient that TransversalElt.

Transversals can be extended as more generators are found for the stabiliser. Orbit generators are generators for the original group, stored separately so we can add extra generators to form a shallower tree. Orbits are stored as hash tables.

creates a transversal by Schreier tree for the subgroup stabilising the point basePoint (an object, typically an integer or vector) inside the group generated by strongGens (a list of strong generators for the group). This is the only correct way to create a transversal by Schreier tree.

The elements used to compute the orbit ss. These will be generators for the larger group, however there will often be redundancies to keep the Schreier tree shallow.

Inverses of the orbit generators of the orbit ss.

The base point of transversal by Schreier tree ss, i.e. the point stabilised.

The identity of group ss.

Extend a transversal by Schreier tree st with new generators newGens.

gdc - Ideally, ExtendSchreierTransversal should be a field of the Schreier tree, chosen by SchreierTransversal().

gdc - This is the new function with the cube control tree.

EXPERIMENTAL IDEA: IT WOULD NEED TO BE TUNED. NOT CURRENTLY COMPETITIVE WITH METHOD BELOW.

gdc - This is the original function with the traditional control tree

BASED ON: CF94 ``A Random Base Change Algorithm for Permutation Groups'', G. Cooperman and L. Finkelstein, J. of Symbolic Computation 17, 1994, pp. 513--528

Complete the transversal. In order to ensure that the Schreier tree does not become too deep, the Extend... functions do not complete the transversal. Rather they extend it by depth one.

returns the preferred generators of the transversal by Schreier tree ss. The preferred generators are always used first when computing the Schreier tree.

The depth of Schreier tree ss.

4.3 Transversals by homomorphic images

For the transversal of the kernel of a homomorphism, a quotient group for the kernel of a homomorphism is stored. Transversal elements are computed by finding a chain for the image group and doing shadowed stripping.

Note: TransversalElt is more efficient that SiftOneLevel.

creates a hom transversal for the homomorphism h.

The homomorphism of hom transversal homtr.

The quotient group of hom transversal homtr.

The image group of hom transversal homtr.

4.4 Transversals by direct products

Stores projection and injection for a direct product. The chain subgroup is the kernel of the projection.

The projection of the direct product transversal dpt.

The injection of a direct product transversal dpt.

4.5 Transversals by Trivial subgroups

For use when our group is small enough to enumerate.

returns a transversal by trivial subgroup for the group G.

4.6 Transversals by sift functions

Given a group, subgroup, and sift function from group to subgroup that is constant on cosets, this defines a transversal. One typically prefers a normalized sift function that is the the identity map on subgroups. For situations when there is a non-group theoretic method for computing the transversal element, e.g. using row reduction for the stabiliser of an invariant subspace.

Note: SiftOneLevel is more efficient than TransversalElt.

returns a transversal by sift function.

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
May 2002