<html><head><title>[new] 4 Transversals of subgroups</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>4 Transversals of subgroups</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP004.htm#SECT001">General operations on transversals</a> <li> <A HREF="CHAP004.htm#SECT002">Transversals by Schreier tree</a> <li> <A HREF="CHAP004.htm#SECT003">Transversals by homomorphic images</a> <li> <A HREF="CHAP004.htm#SECT004">Transversals by direct products</a> <li> <A HREF="CHAP004.htm#SECT005">Transversals by Trivial subgroups</a> <li> <A HREF="CHAP004.htm#SECT006">Transversals by sift functions</a> </ol><p> <p> This chapter describes the category of transversals of subgroups. This category has the following representations: <code>TransvBySchreierTree</code>, <code>TransvByHomomorphism</code>, <code>TransvByDirProd</code>, <code>TransvByTrivSubgrp</code>, <code>TransvBySiftFunct</code>. <p> <strong>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.</strong> <p> <p> <h2><a name="SECT001">4.1 General operations on transversals</a></h2> <p><p> Every kind of transversal has the following common operations/attributes: <code>Size</code>, <code>Enumerator</code>, <code>Iterator</code>, <code>Random</code>, <code>TransversalElt</code>, <code>SiftOneLevel</code>. <p> <a name = "SSEC001.1"></a> <li><code>TransversalElt( </code><var>ss</var><code>, </code><var>elt</var><code> ) O</code> <p> for a transversal <var>ss</var> and group element <var>elt</var>, returns the representative of the coset containing the element <var>elt</var>. The representative is unique, i.e. <code>TransversalElt</code> will return the same thing for different elements of the same coset. <p> <a name = "SSEC001.2"></a> <li><code>SiftOneLevel( </code><var>ss</var><code>, </code><var>g</var><code> ) O</code> <p> For a transversal <var>ss</var> and group element <var>g</var>, the following relationship with <code>TransversalElt</code> (see <a href="CHAP004.htm#SSEC001.1">TransversalElt</a>) defines <code>SiftOneLevel</code>: <p> <code>SiftOneLevel(</code><var>ss</var><code>, </code><var>g</var><code>) = </code><var>g</var><code> * TransversalElt(</code><var>ss</var><code>, </code><var>g</var><code>)</code> <p> For some kinds of transversal <code>TransversalElt</code> is more efficient, for others <code>SiftOneLevel</code> is. <p> <p> <h2><a name="SECT002">4.2 Transversals by Schreier tree</a></h2> <p><p> For transversals of stabiliser subgroups, we store a Schreier tree to allow us to find transversal elements. <p> <strong>Note:</strong> <code>SiftOneLevel</code> is more efficient that <code>TransversalElt</code>. <p> 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. <p> <a name = "SSEC002.1"></a> <li><code>SchreierTransversal( </code><var>basePoint</var><code>, </code><var>Action</var><code>, </code><var>strongGens</var><code> ) F</code> <p> creates a transversal by Schreier tree for the subgroup stabilising the point <var>basePoint</var> (an object, typically an integer or vector) inside the group generated by <var>strongGens</var> (a list of strong generators for the group). This is the only correct way to create a transversal by Schreier tree. <p> <a name = "SSEC002.2"></a> <li><code>OrbitGenerators( </code><var>ss</var><code> ) O</code> <p> The elements used to compute the orbit <var>ss</var>. These will be generators for the larger group, however there will often be redundancies to keep the Schreier tree shallow. <p> <a name = "SSEC002.3"></a> <li><code>OrbitGeneratorsInv( </code><var>ss</var><code> ) O</code> <p> Inverses of the orbit generators of the orbit <var>ss</var>. <p> <a name = "SSEC002.4"></a> <li><code>BasePointOfSchreierTransversal( </code><var>ss</var><code> ) O</code> <p> The base point of transversal by Schreier tree <var>ss</var>, i.e. the point stabilised. <p> <a name = "SSEC002.5"></a> <li><code>One( </code><var>ss</var><code> ) A</code> <p> The identity of group <var>ss</var>. <p> <a name = "SSEC002.6"></a> <li><code>ExtendSchreierTransversal( </code><var>st</var><code>, </code><var>newGens</var><code> ) F</code> <li><code>ExtendSchreierTransversal( </code><var>st</var><code>, </code><var>newGens</var><code>, </code><var>newGensInv</var><code> ) F</code> <p> Extend a transversal by Schreier tree <var>st</var> with new generators <var>newGens</var>. <p> <a name = "SSEC002.7"></a> <li><code>ExtendSchreierTransversalShortCube( </code><var>ss</var><code>, </code><var>newGens</var><code> ) F</code> <li><code>ExtendSchreierTransversalShortCube( </code><var>ss</var><code>, </code><var>newGens</var><code>, </code><var>newGensInv</var><code> ) F</code> <p> gdc - Ideally, <code>ExtendSchreierTransversal</code> should be a field of the Schreier tree, chosen by <code>SchreierTransversal()</code>. <p> gdc - This is the new function with the cube control tree. <p> EXPERIMENTAL IDEA: IT WOULD NEED TO BE TUNED. NOT CURRENTLY COMPETITIVE WITH METHOD BELOW. <p> <a name = "SSEC002.8"></a> <li><code>ExtendSchreierTransversalShortTree( </code><var>ss</var><code>, </code><var>newGens</var><code> ) F</code> <li><code>ExtendSchreierTransversalShortTree( </code><var>ss</var><code>, </code><var>newGens</var><code>, </code><var>newGensInv</var><code> ) F</code> <p> gdc - This is the original function with the traditional control tree <p> BASED ON: <a href="biblio.htm#CF94"><cite>CF94</cite></a> ``A Random Base Change Algorithm for Permutation Groups'', G. Cooperman and L. Finkelstein, J. of Symbolic Computation 17, 1994, pp. 513--528 <p> <a name = "SSEC002.9"></a> <li><code>CompleteSchreierTransversal( </code><var>ss</var><code> ) F</code> <p> Complete the transversal. In order to ensure that the Schreier tree does not become too deep, the <code>Extend...</code> functions do not complete the transversal. Rather they extend it by depth one. <p> <a name = "SSEC002.10"></a> <li><code>PreferredGenerators( </code><var>ss</var><code> ) A</code> <p> returns the preferred generators of the transversal by Schreier tree <var>ss</var>. The preferred generators are always used first when computing the Schreier tree. <p> <a name = "SSEC002.11"></a> <li><code>SchreierTreeDepth( </code><var>ss</var><code> ) F</code> <p> The depth of Schreier tree <var>ss</var>. <p> <p> <h2><a name="SECT003">4.3 Transversals by homomorphic images</a></h2> <p><p> 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. <p> <strong>Note:</strong> <code>TransversalElt</code> is more efficient that <code>SiftOneLevel</code>. <p> <a name = "SSEC003.1"></a> <li><code>HomTransversal( </code><var>h</var><code> ) F</code> <p> creates a hom transversal for the homomorphism <var>h</var>. <p> <a name = "SSEC003.2"></a> <li><code>Homomorphism( </code><var>homtr</var><code> ) O</code> <p> The homomorphism of hom transversal <var>homtr</var>. <p> <a name = "SSEC003.3"></a> <li><code>QuotientGroup( </code><var>homtr</var><code> ) A</code> <p> The quotient group of hom transversal <var>homtr</var>. <p> <a name = "SSEC003.4"></a> <li><code>ImageGroup( </code><var>homtr</var><code> ) O</code> <p> The image group of hom transversal <var>homtr</var>. <p> <p> <h2><a name="SECT004">4.4 Transversals by direct products</a></h2> <p><p> Stores projection and injection for a direct product. The chain subgroup is the kernel of the projection. <p> <a name = "SSEC004.1"></a> <li><code>Projection( </code><var>dpt</var><code> ) O</code> <p> The projection of the direct product transversal <var>dpt</var>. <p> <a name = "SSEC004.2"></a> <li><code>Injection( </code><var>dpt</var><code> ) O</code> <p> The injection of a direct product transversal <var>dpt</var>. <p> <p> <h2><a name="SECT005">4.5 Transversals by Trivial subgroups</a></h2> <p><p> For use when our group is small enough to enumerate. <p> <a name = "SSEC005.1"></a> <li><code>TransversalByTrivial( </code><var>G</var><code> ) F</code> <p> returns a transversal by trivial subgroup for the group <var>G</var>. <p> <p> <h2><a name="SECT006">4.6 Transversals by sift functions</a></h2> <p><p> 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. <p> <strong>Note:</strong> <code>SiftOneLevel</code> is more efficient than <code>TransversalElt</code>. <p> <a name = "SSEC006.1"></a> <li><code>TransversalBySiftFunction( </code><var>supergroup</var><code>, </code><var>subgroup</var><code>, </code><var>sift</var><code> ) F</code> <p> returns a transversal by sift function. <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>