4 Transversals of subgroups

This chapter describes the category of transversals of subgroups. This category has representations: TransvBySchreierTree, TransvByHomomorphism, TransvByDirProd, TransvByTrivSubgrp, TransvBySiftFunct.

The functions and operations described in this chapter have been added very recently and are still undergoing development. It is conceivable that names of variants of the functionality might change in future versions. If you plan to use these functions in your own code, please contact us.

Sections

  1. General operations on transversals
  2. Transversals by Schreier tree
  3. Transversals by homomorphic images
  4. Transversals by direct products
  5. Transversals by Trivial subgroups
  6. Transversals by sift functions

4.1 General operations on transversals

Every kind of transversal has the following common operations/attributes: Size, Enumerator, Iterator, Random, TransversalElt, SiftOneLevel.

  • TransversalElt( ss, elt ) O

    Return representative of the coset containing the given element. The representative is unique, ie. TransversalElt will return the same thing for different elements of the same coset.

  • SiftOneLevel( ss, elt ) O

    SiftOneLevel( tr, g ) = g TransversalElt( tr, g ). For some kinds of transversal TransversalElt is more efficient, for others SiftOneLevel is.

    4.2 Transversals by Schreier tree

    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.

  • SchreierTransversal( basePoint, Action, strongGens ) F

    Create a transversal by Schreier tree for the subgroup stabilising basePoint inside the group generated by strongGens. This is the only correct way to create a transversal by Schreier tree.

  • OrbitGenerators( ss ) O

    The elements used to compute the orbit. This will be a generator for the larger group, homever it will often by redundant to keep the Schreier tree shallow.

  • OrbitGeneratorsInv( ss ) O

    Inverses of the orbit generators

  • BasePointOfSchreierTransversal( ss ) O

    The base point of a transversal by Schreier tree, ie. the point stabilised.

  • One( ss ) A

    The group identity.

  • ExtendSchreierTransversal( ss, newGens ) F
  • ExtendSchreierTransversal( ss, newGens, newGensInv ) F

    Extend a tranversal by Schreier tree with new generators

  • ExtendSchreierTransversalShortCube( ss, newGens ) F
  • ExtendSchreierTransversalShortCube( ss, newGens, newGensInv ) F

    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.

  • ExtendSchreierTransversalShortTree( ss, newGens ) F
  • ExtendSchreierTransversalShortTree( ss, newGens, newGensInv ) F

    gdc - This is the original function with the traditional control tree BASED ON: ``A Random Base Change Algorithm for Permutation Groups'', G. Cooperman and L. Finkelstein, J. of Symbolic Computation 17, 1994, pp. 513--528

  • CompleteSchreierTransversal( ss ) F

    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.

  • PreferredGenerators( ss ) A

    Returns the preferred generators. The preferred generators are always used first when computing the Schreier tree.

  • SchreierTreeDepth( ss ) F

    The depth of the Schreier tree.

    4.3 Transversals by homomorphic images

    Transversal of the kernel of a homomorphism. Stores a quotient group for the kernel of a homomorphism; Transversal elements are computed by finding a chain for the image group and doing shadowed stripping. Note: TransversalElt is more efficient that SiftOneLevel

  • HomTransversal( h ) F

    Create a hom transversal for the given homomorphism.

  • Homomorphism( homtr ) O

    The homomorphism of a hom transversal.

  • QuotientGroup( homtr ) A

    The quotient group of a hom transversal

  • ImageGroup( homtr ) O

    The image group of a hom transversal.

    4.4 Transversals by direct products

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

  • DirProdTransversal( proj, inj ) F

    Create a direct product transversal.

  • Projection( dpt ) O

    Projection of a direct product transversal.

  • Injection( dpt ) O

    Injection of a direct product transversal.

    4.5 Transversals by Trivial subgroups

    For use when our group is small enough to efficiently enumerate.

  • TransversalByTrivial( G ) F

    Create a transversal by trivial subgroup

    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. eg. using row reduction for the stabiliser of an invariant subspace. Note: SiftOneLevel is more efficient than TransversalElt.

  • TransversalBySiftFunction( supergroup, subgroup, sift ) F

    Create a transversal by sift function

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

    GAP 4 manual
    September 2000