<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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
90
