<html><head><title>[ref] 45 Finitely Presented Groups</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP044.htm">Previous</a>] [<a href ="CHAP046.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>45 Finitely Presented Groups</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP045.htm#SECT001">Creating Finitely Presented Groups</a>
<li> <A HREF="CHAP045.htm#SECT002">Comparison of Elements of Finitely Presented Groups</a>
<li> <A HREF="CHAP045.htm#SECT003">Preimages in the Free Group</a>
<li> <A HREF="CHAP045.htm#SECT004">Operations for Finitely Presented Groups</a>
<li> <A HREF="CHAP045.htm#SECT005">Coset Tables and Coset Enumeration</a>
<li> <A HREF="CHAP045.htm#SECT006">Standardization of coset tables</a>
<li> <A HREF="CHAP045.htm#SECT007">Coset tables for subgroups in the whole group</a>
<li> <A HREF="CHAP045.htm#SECT008">Augmented Coset Tables and Rewriting</a>
<li> <A HREF="CHAP045.htm#SECT009">Low Index Subgroups</a>
<li> <A HREF="CHAP045.htm#SECT010">Converting Groups to Finitely Presented Groups</a>
<li> <A HREF="CHAP045.htm#SECT011">New Presentations and Presentations for Subgroups</a>
<li> <A HREF="CHAP045.htm#SECT012">Preimages under Homomorphisms from an FpGroup</a>
<li> <A HREF="CHAP045.htm#SECT013">Quotient Methods</a>
<li> <A HREF="CHAP045.htm#SECT014">Abelian Invariants for Subgroups</a>
<li> <A HREF="CHAP045.htm#SECT015">Testing Finiteness of Finitely Presented Groups</a>
</ol><p>
<p>
A <strong>finitely presented group</strong> (in short: FpGroup) is a group generated by a
finite set of <strong>abstract generators</strong> subject to a finite set of <strong>relations</strong>
that these generators satisfy. Every finite group can be represented as a
finitely presented group, though in almost all cases it is computationally
much more efficient to work in another representation (even the regular
permutation representation).
<p>
Finitely presented groups are obtained by factoring a free group by a set
of relators. Their elements know about this presentation and compare
accordingly.
<p>
So to create a finitely presented group you first have to generate a free
group (see <a href="CHAP035.htm#SSEC002.1">FreeGroup</a> for details).
Then a list of relators is constructed as words in the generators of the
free group and is factored out to obtain the finitely presented group. Its
generators <strong>are</strong> the images of the free generators. So for example to create
the group
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"> 〈<i>a</i>, <i>b</i> | <i>a</i><sup>2</sup>, <i>b</i><sup>3</sup>, (<i>a</i>·<i>b</i>)<sup>5</sup> 〉</td></tr></table></td></tr></table>
you can use the following commands:
<pre>
gap> f := FreeGroup( "a", "b" );;
gap> g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];
<fp group on the generators [ a, b ]>
</pre>
<p>
Note that you cannot call the generators by their names. These names are
not variables, but just display figures. So, if you want to access the
generators by their names, you first have to introduce the respective
variables and to assign the generators to them.
<p>
<pre>
gap> GeneratorsOfGroup( g );
[ a, b ]
gap> a;
Variable: 'a' must have a value
gap> a := g.1;; b := g.2;; # assign variables
gap> GeneratorsOfGroup( g );
[ a, b ]
gap> a in f;
false
gap> a in g;
true
</pre>
<p>
To relieve you of the tedium of typing the above assignments, <strong>when working
interactively</strong>, there is the function <code>AssignGeneratorVariables</code>
(see <a href="CHAP035.htm#SSEC002.5">AssignGeneratorVariables</a>).
<p>
Note that the generators of the free group are different from the
generators of the FpGroup (even though they are displayed by the same
names). That means that words in the generators of the free group are not
elements of the finitely presented group. Vice versa elements of the
FpGroup are not words.
<p>
<pre>
gap> a*b = b*a;
false
gap> (b^2*a*b)^2 = a^0;
true
</pre>
<p>
Such calculations comparing elements of an FpGroup may run into problems:
There exist finitely
presented groups for which no algorithm exists (it is known that no such
algorithm can exist) that will tell for two arbitrary words in the
generators whether the corresponding elements in the FpGroup are equal.
<p>
Therefore the methods used by <font face="Gill Sans,Helvetica,Arial">GAP</font> to compute in finitely
presented groups may run into warning errors, run out of memory or run
forever. If the FpGroup is (by theory) known to be finite the
algorithms are guaranteed to terminate (if there is sufficient memory
available), but the time needed for the calculation cannot be bounded a
priori. See <a href="CHAP045.htm#SECT005">Coset Tables and Coset Enumeration</a> and
<a href="CHAP045.htm#SECT015">Testing Finiteness of Finitely Presented Groups</a>.
<p>
<pre>
gap> (b^2*a*b)^2;
b^2*a*b^3*a*b
gap> a^0;
<identity ...>
</pre>
<p>
A consequence of our convention is that elements of finitely presented
groups are not printed in a unique way. See also <code>SetReducedMultiplication</code>.
<p>
<a name = ""></a>
<li><code>IsSubgroupFpGroup( </code><var>H</var><code> ) C</code>
<p>
returns <code>true</code> if <var>H</var> is a finitely presented group or a subgroup of a
finitely presented group.
<p>
<a name = ""></a>
<li><code>IsFpGroup( </code><var>G</var><code> ) F</code>
<p>
is a synonym for <code>IsSubgroupFpGroup(</code><var>G</var><code>)</code> and <code>IsGroupOfFamily(</code><var>G</var><code>)</code>.
<p>
Free groups are a special case of finitely presented groups, namely finitely
presented groups with no relators.
<p>
Another special case are groups given by polycyclic presentations. <font face="Gill Sans,Helvetica,Arial">GAP</font>
uses a special representation for these groups which is created in a
different way. See chapter <a href="CHAP044.htm">Pc Groups</a> for details.
<p>
<a name = ""></a>
<li><code>InfoFpGroup V</code>
<p>
The info class for functions dealing with finitely presented groups is
<code>InfoFpGroup</code>.
<p>
<p>
<h2><a name="SECT001">45.1 Creating Finitely Presented Groups</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code></code><var>F</var><code>/</code><var>rels</var><code></code>
<p>
creates a finitely presented group given by the presentation
〈<i>gens</i> | <i>rels</i> 〉 where <var>gens</var> are the generators of the free
group <var>F</var>.
Note that relations are entered as <strong>relators</strong>, i.e., as words in the
generators of the free group. To enter an equation use the quotient
operator, i.e., for the relation <i>a</i><sup><i>b</i></sup> = <i>ab</i> one has to enter
<code>a^b/(a*b)</code>.
<p>
<pre>
gap> f := FreeGroup( 3 );;
gap> f / [ f.1^4, f.2^3, f.3^5, f.1*f.2*f.3 ];
<fp group on the generators [ f1, f2, f3 ]>
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>FactorGroupFpGroupByRels( </code><var>G</var><code>, </code><var>elts</var><code> ) F</code>
<p>
returns the factor group <var>G</var>/<var>N</var> of <var>G</var> by the normal closure N of
<var>elts</var> where <var>elts</var> is expected to be a list of elements of <var>G</var>.
<p>
<p>
<h2><a name="SECT002">45.2 Comparison of Elements of Finitely Presented Groups</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code></code><var>a</var><code> = </code><var>b</var><code></code>
<p>
Two elements of a finitely presented group are equal if they are equal in
this group. Nevertheless they may be represented as different words in the
generators. Because of the fundamental problems mentioned in the
introduction to this chapter such a test may take very long and cannot be
guaranteed to finish.
<p>
The method employed by <font face="Gill Sans,Helvetica,Arial">GAP</font> for such an equality test use the underlying
finitely presented group. First (unless this group is known to be infinite)
<font face="Gill Sans,Helvetica,Arial">GAP</font> tries to find a faithful permutation representation by a bounded
Todd-Coxeter. If this fails, a Knuth-Bendix (see <a href="CHAP051.htm#SECT005">Rewriting Systems and the Knuth-Bendix Procedure</a>) is attempted and the words are compared via their
normal form.
<p>
If only elements in a subgroup are to be tested for equality it thus can be
useful to translate the problem in a new finitely presented group by
rewriting (see <a href="CHAP045.htm#SSEC010.1">IsomorphismFpGroup</a>);
<p>
The equality test of elements underlies many ``basic'' calculations, such as
the order of an element, and the same type of problems can arise there.
In some cases, working with rewriting systems can still help to solve the
problem. The ``kbmag' package provides such functionality, see the package
manual for further details.
<p>
<a name = "SSEC002.2"></a>
<li><code></code><var>a</var><code> < </code><var>b</var><code></code>
<p>
Problems get even worse when trying to compute a total ordering on the
elements of a finitely presented group. As any ordering that is guaranteed
to be reproducible in different runs of <font face="Gill Sans,Helvetica,Arial">GAP</font> or even with different groups
given by syntactically equal presentations would be prohibitively expensive
to implement, the ordering of elements is depending on a method chosen by
<font face="Gill Sans,Helvetica,Arial">GAP</font> and not guaranteed to stay the same when repeating the construction
of an FpGroup. The only guarantee given for the <code><</code>
ordering for such elements is that it will stay the same for one family
during its lifetime. The attribute <code>FpElmComparisonMethod</code> is used to obtain
a comparison function for a family of FpGroup elements.
<p>
<a name = "SSEC002.3"></a>
<li><code>FpElmComparisonMethod( </code><var>fam</var><code> ) A</code>
<p>
If <var>fam</var> is the elements family of a finitely presented group this
attribute returns a function <code>smaller(</code><var>left</var><code>, </code><var>right</var><code>)</code> that will be
used to compare elements in <var>fam</var>.
<p>
<a name = "SSEC002.4"></a>
<li><code>SetReducedMultiplication( </code><var>f</var><code> ) F</code>
<li><code>SetReducedMultiplication( </code><var>e</var><code> ) F</code>
<li><code>SetReducedMultiplication( </code><var>fam</var><code> ) F</code>
<p>
for an fp group <var>f</var>, an element <var>e</var> of it or the family <var>fam</var> of its
elements
this function will force immediate reduction when multiplying, keeping
words short at extra cost per multiplication.
<p>
<p>
<h2><a name="SECT003">45.3 Preimages in the Free Group</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code>FreeGroupOfFpGroup( </code><var>G</var><code> ) A</code>
<p>
returns the underlying free group for the finitely presented group <var>G</var>.
This is the group generated by the free generators provided by
<code>FreeGeneratorsOfFpGroup(</code><var>G</var><code>)</code>.
<p>
<a name = "SSEC003.2"></a>
<li><code>FreeGeneratorsOfFpGroup( </code><var>G</var><code> ) A</code>
<a name = "SSEC003.2"></a>
<li><code>FreeGeneratorsOfWholeGroup( </code><var>U</var><code> ) O</code>
<p>
<code>FreeGeneratorsOfFpGroup</code> returns the underlying free generators
corresponding to the generators of the finitely presented group <var>G</var>
which must be a full fp group.
<p>
<code>FreeGeneratorsOfWholeGroup</code> also works for subgroups of an fp group and
returns the free generators of the full group that defines the family.
<p>
<a name = "SSEC003.3"></a>
<li><code>RelatorsOfFpGroup( </code><var>G</var><code> ) A</code>
<p>
returns the relators of the finitely presented group <var>G</var> as words in the
free generators provided by <code>FreeGeneratorsOfFpGroup(</code><var>G</var><code>)</code>.
<p>
<pre>
gap> f := FreeGroup( "a", "b" );;
gap> g := f / [ f.1^5, f.2^2, f.1^f.2*f.1 ];
<fp group on the generators [ a, b ]>
gap> Size( g );
10
gap> FreeGroupOfFpGroup( g ) = f;
true
gap> FreeGeneratorsOfFpGroup( g );
[ a, b ]
gap> RelatorsOfFpGroup( g );
[ a^5, b^2, b^-1*a*b*a ]
</pre>
<p>
Elements of a finitely presented group are not words, but are represented
using a word from the free group as representative. The following two
commands obtain this representative, respectively create an element in the
finitely presented group.
<p>
<a name = "SSEC003.4"></a>
<li><code>UnderlyingElement( </code><var>elm</var><code> ) O</code>
<p>
Let <var>elm</var> be an element of a group whose elements are represented as
words with further properties. Then <code>UnderlyingElement</code> returns the word
from the free group that is used as a representative for <var>elm</var>.
<p>
<pre>
gap> w := g.1*g.2;
a*b
gap> IsWord( w );
false
gap> ue := UnderlyingElement( w );
a*b
gap> IsWord( ue );
true
</pre>
<p>
<a name = "SSEC003.5"></a>
<li><code>ElementOfFpGroup( </code><var>fam</var><code>, </code><var>word</var><code> ) O</code>
<p>
If <var>fam</var> is the elements family of a finitely presented group and <var>word</var>
is a word in the free generators underlying this finitely presented
group, this operation creates the element with the representative <var>word</var>
in the free group.
<p>
<pre>
gap> ge := ElementOfFpGroup( FamilyObj( g.1 ), f.1*f.2 );
a*b
gap> ge in f;
false
gap> ge in g;
true
</pre>
<p>
<p>
<h2><a name="SECT004">45.4 Operations for Finitely Presented Groups</a></h2>
<p><p>
Finitely presented groups are groups and so all operations for groups should
be applicable to them (though not necessarily efficient methods are
available.) Most methods for finitely presented groups rely on coset
enumeration. See <a href="CHAP045.htm#SECT005">Coset Tables and Coset Enumeration</a> for details.
<p>
The command <code>IsomorphismPermGroup</code> can be used to obtain a faithful
permutation representation, if such a representation of small degree exists.
(Otherwise it might run very long or fail.)
<pre>
gap> f := FreeGroup( "a", "b" );
<free group on the generators [ a, b ]>
gap> g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];
<fp group on the generators [ a, b ]>
gap> h := IsomorphismPermGroup( g );
[ a, b ] -> [ (1,2)(4,5), (2,3,4) ]
gap> u:=Subgroup(g,[g.1*g.2]);;rt:=RightTransversal(g,u);
RightTransversal(<fp group of size 60 on the generators [ a, b ]>,Group(
[ a*b ]))
gap> Image(ActionHomomorphism(g,rt,OnRight));
Group([ (1,2)(3,4)(5,7)(6,8)(9,10)(11,12), (1,3,2)(4,5,6)(7,8,9)(10,11,12) ])
</pre>
<p>
<p>
<h2><a name="SECT005">45.5 Coset Tables and Coset Enumeration</a></h2>
<p><p>
Coset enumeration (see <a href="biblio.htm#Neu82"><cite>Neu82</cite></a> for an explanation) is one of the
fundamental tools for the examination of finitely presented groups. This
section describes <font face="Gill Sans,Helvetica,Arial">GAP</font> functions that can be used to invoke a coset
enumeration.
<p>
Note that in addition to the built-in coset enumerator there is the <font face="Gill Sans,Helvetica,Arial">GAP</font>
package <font face="Gill Sans,Helvetica,Arial">ACE</font>. Moreover, <font face="Gill Sans,Helvetica,Arial">GAP</font> provides an interactive Todd-Coxeter
in the <font face="Gill Sans,Helvetica,Arial">GAP</font> package <font face="Gill Sans,Helvetica,Arial">ITC</font> which is based on the <font face="Gill Sans,Helvetica,Arial">XGAP</font>
package.
<p>
<a name = "SSEC005.1"></a>
<li><code>CosetTable( </code><var>G</var><code>, </code><var>H</var><code> ) O</code>
<p>
returns the coset table of the finitely presented group <var>G</var> on the cosets
of the subgroup <var>H</var>.
<p>
Basically a coset table is the permutation representation of the finitely
presented group on the cosets of a subgroup (which need not be faithful
if the subgroup has a nontrivial core). Most of the set theoretic and
group functions use the regular representation of <var>G</var>, i.e., the coset
table of <var>G</var> over the trivial subgroup.
<p>
The coset table is returned as a list of lists. For each generator of
<var>G</var> and its inverse the table contains a generator list. A generator
list is simply a list of integers. If <var>l</var> is the generator list for the
generator <var>g</var> and if <code></code><var>l</var><code>[</code><var>i</var><code>] = </code><var>j</var><code></code> then generator <var>g</var> takes the coset
<var>i</var> to the coset <var>j</var> by multiplication from the right. Thus the
permutation representation of <var>G</var> on the cosets of <var>H</var> is obtained by
applying <code>PermList</code> to each generator list (see <a href="CHAP040.htm#SSEC004.2">PermList</a>).
<p>
The coset table is standard (see below).
<p>
For finitely presented groups, a coset table is computed by a Todd-Coxeter
coset enumeration. Note that
you may influence the performance of that enumeration by changing the values
of the global variables <code>CosetTableDefaultLimit</code> and
<code>CosetTableDefaultMaxLimit</code> described below and that the options
described under <code>CosetTableFromGensAndRels</code> are recognized.
<p>
<pre>
gap> tab := CosetTable( g, Subgroup( g, [ g.1, g.2*g.1*g.2*g.1*g.2^-1 ] ) );
[ [ 1, 4, 5, 2, 3 ], [ 1, 4, 5, 2, 3 ], [ 2, 3, 1, 4, 5 ], [ 3, 1, 2, 4, 5 ] ]
gap> List( last, PermList );
[ (2,4)(3,5), (2,4)(3,5), (1,2,3), (1,3,2) ]
gap> PrintArray( TransposedMat( tab ) );
[ [ 1, 1, 2, 3 ],
[ 4, 4, 3, 1 ],
[ 5, 5, 1, 2 ],
[ 2, 2, 4, 4 ],
[ 3, 3, 5, 5 ] ]
</pre>
<p>
The last printout in the preceding example provides the coset table in the
form in which it is usually used in hand calculations: The rows correspond to
the cosets, the columns correspond to the generators and their inverses in
the ordering <i>g</i><sub>1</sub>, <i>g</i><sub>1</sub><sup>−1</sup>, <i>g</i><sub>2</sub>, <i>g</i><sub>2</sub><sup>−1</sup>. (See section <a href="CHAP045.htm#SECT006">Standardization of coset tables</a> for a description on the way the numbers are assigned.)
<p>
<a name = "SSEC005.2"></a>
<li><code>TracedCosetFpGroup( </code><var>tab</var><code>, </code><var>word</var><code>, </code><var>pt</var><code> ) F</code>
<p>
Traces the coset number <var>pt</var> under the word <var>word</var> through the coset
table <var>tab</var>. (Note: <var>word</var> must be in the free group, use
<code>UnderlyingElement</code> if in doubt.)
<p>
<pre>
gap> TracedCosetFpGroup(tab,UnderlyingElement(g.1),2);
4
</pre>
<p>
<a name = "SSEC005.3"></a>
<li><code>FactorCosetAction( </code><var>G</var><code>, </code><var>H</var><code> )</code>
<a name = "SSEC005.3"></a>
<li><code>FactorCosetOperation( </code><var>G</var><code>, </code><var>H</var><code> )</code>
<p>
returns the action of <var>G</var> on the cosets of the subgroup <var>H</var> of <var>G</var>.
<p>
<pre>
gap> u := Subgroup( g, [ g.1, g.1^g.2 ] );
Group([ a, b^-1*a*b ])
gap> FactorCosetAction( g, u );
[ a, b ] -> [ (2,4)(5,6), (1,2,3)(4,5,6) ]
</pre>
<p>
<a name = "SSEC005.4"></a>
<li><code>CosetTableBySubgroup( </code><var>G</var><code>, </code><var>H</var><code> ) O</code>
<p>
returns a coset table for the action of <var>G</var> on the cosets of <var>H</var>. The
columns of the table correspond to the <code>GeneratorsOfGroup(</code><var>G</var><code>)</code>.
<p>
<a name = "SSEC005.5"></a>
<li><code>CosetTableFromGensAndRels( </code><var>fgens</var><code>, </code><var>grels</var><code>, </code><var>fsgens</var><code> ) F</code>
<p>
is an internal function which is called by the functions <code>CosetTable</code>,
<code>CosetTableInWholeGroup</code> and others. It is, in fact, the proper working
horse that performs a Todd-Coxeter coset
enumeration. <var>fgens</var> must be a set of free generators and <var>grels</var> a set
of relators in these generators. <var>fsgens</var> are subgroup generators
expressed as words in these generators. The function returns a coset
table with respect to <var>fgens</var>.
<p>
<code>CosetTableFromGensAndRels</code> will call
<code>TCENUM.CosetTableFromGensAndRels</code>. This makes it possible to replace
the built-in coset enumerator with another one by assigning <code>TCENUM</code> to
another record.
<p>
The library version which is used by default performs a standard Felsch
strategy coset enumeration. You can call this function explicitly as
<code>GAPTCENUM.CosetTableFromGensAndRels</code> even if other coset enumerators
are installed.
<p>
The expected parameters are
<p>
<dl compact>
<dt> <var>fgens</var> <dd> generators of the free group <var>F</var>
<p>
<dt> <var>grels</var> <dd> relators as words in <var>F</var>
<p>
<dt> <var>fsgens</var> <dd> subgroup generators as words in <var>F</var>.
</dl>
<p>
<code>CosetTableFromGensAndRels</code> processes two options (see
chapter <a href="CHAP008.htm">Options Stack</a>):
<p>
<dl compact>
<dt> <code>max</code> <dd> The limit of the number of cosets to be defined. If the
enumeration does not finish with this number of cosets, an error is
raised and the user is asked whether she wants to continue. The
default value is the value given in the variable
<code>CosetTableDefaultMaxLimit</code>. (Due to the algorithm the actual
limit used can be a bit higher than the number given.)
<p>
<dt> <code>silent</code> <dd> if set to <code>true</code> the algorithm will not raise the error
mentioned under option <code>max</code> but silently return <code>fail</code>. This can be
useful if an enumeration is only wanted unless it becomes too big.
</dl>
<p>
<a name = "SSEC005.6"></a>
<li><code>CosetTableDefaultMaxLimit V</code>
<p>
is the default limit for the number of cosets allowed in a coset
enumeration.
<p>
A coset enumeration will not finish if the subgroup does not have finite
index, and even if it has it may take many more intermediate cosets than
the actual index of the subgroup is. To avoid a coset enumeration
``running away'' therefore <font face="Gill Sans,Helvetica,Arial">GAP</font> has a ``safety stop'' built in. This
is controlled by the global variable <code>CosetTableDefaultMaxLimit</code>.
<p>
If this number of cosets is reached, <font face="Gill Sans,Helvetica,Arial">GAP</font> will issue an error message
and prompt the user to either continue the calculation or to stop it.
The default value is 256000.
<p>
See also the description of the options to <code>CosetTableFromGensAndRels</code>.
<p>
<pre>
gap> f := FreeGroup( "a", "b" );;
gap> u := Subgroup( f, [ f.2 ] );
Group([ b ])
gap> Index( f, u );
Error, the coset enumeration has defined more than 256000 cosets
called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
TryCosetTableInWholeGroup( H ) called from
CosetTableInWholeGroup( H ) called from
IndexInWholeGroup( H ) called from
...
Entering break read-eval-print loop ...
type 'return;' if you want to continue with a new limit of 512000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk> quit;
</pre>
<p>
At this point, a <code>break</code>-loop (see Section <a href="CHAP006.htm#SECT004">Break Loops</a>) has been entered.
The line beginning <code>Error</code> tells you why this occurred. The next seven lines,
occur if <code>OnBreak</code> has its default value of <code>Where</code> (see <a href="CHAP006.htm#SSEC004.3">OnBreak</a>) and
explains, in this case, how <font face="Gill Sans,Helvetica,Arial">GAP</font> came to be doing a coset enumeration.
Then you are give a number of options of how to escape the <code>break</code>-loop:
you can either continue the calculation with a larger
number of permitted cosets, stop the calculation if you don't
expect the enumeration to finish (like in the example above), or continue
without a limit on the number of cosets. (Choosing the first option will,
of course, land you back in a <code>break</code>-loop. Try it!)
<p>
Setting <code>CosetTableDefaultMaxLimit</code> (or the <code>max</code> option value, for any
function that invokes a coset enumeration) to
<code>infinity</code> (or to 0) will force all coset enumerations to continue until
they either get a result or exhaust the whole available space.
For example, each of
<p>
<pre>
gap> CosetTableDefaultMaxLimit := 0;;
gap> Index( f, u );
</pre>
<p>
or
<p>
<pre>
gap> Index( f, u : max := 0 );
</pre>
<p>
have essentially the same effect as choosing the third option
(typing: <code>maxlimit := 0; return;</code>) at the <code>brk></code> prompt above (instead of
<code>quit;</code>).
<p>
<a name = "SSEC005.7"></a>
<li><code>CosetTableDefaultLimit V</code>
<p>
is the default number of cosets with which any coset table is
initialized before doing a coset enumeration.
<p>
The function performing this coset enumeration will automatically extend
the table whenever necessary (as long as the number of cosets does not
exceed the value of <code>CosetTableDefaultMaxLimit</code>), but this is an
expensive operation. Thus, if you change the value of
<code>CosetTableDefaultLimit</code>, you should set it to a number of cosets
that you expect to be sufficient for your subsequent coset enumerations.
On the other hand, if you make it too large, your job will unnecessarily
waste a lot of space.
<p>
The default value of <code>CosetTableDefaultLimit</code> is 1000.
<p>
<a name = "SSEC005.8"></a>
<li><code>MostFrequentGeneratorFpGroup( </code><var>G</var><code> ) F</code>
<p>
is an internal function which is used in some applications of coset
table methods. It returns the first of those generators of the given
finitely presented group <var>G</var> which occur most frequently in the
relators.
<p>
<a name = "SSEC005.9"></a>
<li><code>IndicesInvolutaryGenerators( </code><var>G</var><code> ) A</code>
<p>
returns the indices of those generators of the finitely presented group
<var>G</var> which are known to be involutions. This knowledge is used by
internal functions to improve the performance of coset enumerations.
<p>
<p>
<h2><a name="SECT006">45.6 Standardization of coset tables</a></h2>
<p><p>
For any two coset numbers <i>i</i> and <i>j</i> with <i>i</i> < <i>j</i> the first occurrence of
<i>i</i> in a coset table precedes the first occurrence of <i>j</i> with respect to
the usual row-wise ordering of the table entries. Following the notation of
Charles Sims' book on computation with finitely presented groups
<a href="biblio.htm#Sims94"><cite>Sims94</cite></a> we call such a table a <strong>standard coset table</strong>.
<p>
The table entries which contain the first occurrences of the coset numbers
<i>i</i> > 1 recursively provide for each <i>i</i> a representative of the
corresponding coset in form of a unique word <i>w</i><sub><i>i</i></sub> in the generators and
inverse generators of <i>G</i>. The first coset (which is <i>H</i> itself) can be
represented by the empty word <i>w</i><sub>1</sub>. A coset table is standard if and only
if the words <i>w</i><sub>1</sub>, <i>w</i><sub>2</sub>, ... are length-plus-lexicographic ordered (as
defined in <a href="biblio.htm#Sims94"><cite>Sims94</cite></a>), for short: <strong>lenlex</strong>.
<p>
We would like to warn you that this standardization of coset tables is
different from the concept that we have used in earlier <font face="Gill Sans,Helvetica,Arial">GAP</font> versions. That
old concept ignored the columns that correspond to inverse generators and
hence only considered words in the generators of <i>G</i>. We will call the old
standard the <strong>semilenlex</strong> standard as it would also work in the case of
semigroups where no inverses of the generators are known.
<p>
We have changed the convention from the semilenlex standard to the lenlex
standard because the definiton of a standard coset table in Sims' book tends
to become a kind of international standard. However, for reasons of upward
compatibility <font face="Gill Sans,Helvetica,Arial">GAP</font> still offers the possibility to switch back to the old
convention by just changing the value of the global variable
<code>CosetTableStandard</code> from its default value <code>"lenlex"</code> to <code>"semilenlex"</code>.
Then all implicit standardizations of coset tables will follow the old
convention. Setting the value of <code>CosetTableStandard</code> back to <code>"lenlex"</code>
again means switching back to the new convention.
<p>
<a name = "SSEC006.1"></a>
<li><code>CosetTableStandard V</code>
<p>
specifies the definiton of a <strong>standard coset table</strong>. It is used
whenever coset tables or augmented coset tables are created. Its value
may be <code>"lenlex"</code> or <code>"semilenlex"</code>. If it is <code>"lenlex"</code> coset tables
will be standardized using all their columns as defined in Charles Sims'
book (this is the new default standard of <font face="Gill Sans,Helvetica,Arial">GAP</font>). If it is <code>"semilenlex"</code>
they will be standardized using only their generator columns (this was
the original <font face="Gill Sans,Helvetica,Arial">GAP</font> standard). The default value of <code>CosetTableStandard</code> is
<code>"lenlex"</code>.
<p>
Independent of the current value of <code>CosetTableStandard</code> there is the
possibility to standardize (or restandardize) a coset table at any time using
the following function.
<p>
<a name = "SSEC006.2"></a>
<li><code>StandardizeTable( </code><var>table</var><code>, </code><var>standard</var><code> ) F</code>
<p>
standardizes the given coset table <var>table</var>. The second argument is
optional. It defines the standard to be used, its values may be
<code>"lenlex"</code> or <code>"semilenlex"</code> specifying the new or the old convention,
respectively. If no value for the parameter <var>standard</var> is provided the
function will use the global variable <code>CosetTableStandard</code> instead. Note
that the function alters the given table, it does not create a copy.
<p>
<pre>
gap> StandardizeTable( tab, "semilenlex" );
gap> PrintArray( TransposedMat( tab ) );
[ [ 1, 1, 2, 4 ],
[ 3, 3, 4, 1 ],
[ 2, 2, 3, 3 ],
[ 5, 5, 1, 2 ],
[ 4, 4, 5, 5 ] ]
</pre>
<p>
<p>
<h2><a name="SECT007">45.7 Coset tables for subgroups in the whole group</a></h2>
<p><p>
<a name = "SSEC007.1"></a>
<li><code>CosetTableInWholeGroup( </code><var> H </var><code> ) A</code>
<a name = "SSEC007.1"></a>
<li><code>TryCosetTableInWholeGroup( </code><var> H </var><code> ) O</code>
<p>
is equivalent to <code>CosetTable(</code><var>G</var><code>,</code><var>H</var><code>)</code> where <var>G</var> is the (unique)
finitely presented group such that <var>H</var> is a subgroup of <var>G</var>. It
overrides a <code>silent</code> option (see <a href="CHAP045.htm#SSEC005.5">CosetTableFromGensAndRels</a>) with
<code>false</code>.
<p>
The variant <code>TryCosetTableInWholeGroup</code> does not override the <code>silent</code>
option with <code>false</code> in case a coset table is only wanted if not too
expensive. It will store a result that is not <code>fail</code> in the attribute
<code>CosetTableInWholeGroup</code>.
<p>
<a name = "SSEC007.2"></a>
<li><code>SubgroupOfWholeGroupByCosetTable( </code><var>fpfam</var><code>, </code><var>tab</var><code> ) F</code>
<p>
takes a family of an fp group and a coset table <var>tab</var> and returns
the subgroup of fam!.wholeGroup defined by this coset table.
<p>
See also <code>CosetTableBySubgroup</code> (<a href="CHAP045.htm#SSEC005.4">CosetTableBySubgroup</a>).
<p>
<p>
<h2><a name="SECT008">45.8 Augmented Coset Tables and Rewriting</a></h2>
<p><p>
<a name = "SSEC008.1"></a>
<li><code>AugmentedCosetTableInWholeGroup( </code><var> H </var><code> [, </code><var>gens</var><code>] ) O</code>
<p>
For a subgroup <var>H</var> of a finitely presented group, this function returns
an augmented coset table. If a generator set <var>gens</var> is given, it is
guaranteed that <var>gens</var> will be a subset of the primary and secondary
subgroup generators of this coset table.
<p>
It is mutable so we are permitted to add further entries. However
existing entries may not be changed. Any entries added however should
correspond to the subgroup only and not to an homomorphism.
<p>
<a name = "SSEC008.2"></a>
<li><code>AugmentedCosetTableMtc( </code><var>G</var><code>, </code><var>H</var><code>, </code><var>type</var><code>, </code><var>string</var><code> ) F</code>
<p>
is an internal function used by the subgroup presentation functions
described in <a href="CHAP046.htm#SECT003">Subgroup Presentations</a>. It applies a Modified Todd-Coxeter
coset representative enumeration to construct an augmented coset table
(see <a href="CHAP046.htm#SECT003">Subgroup presentations</a>) for the given subgroup <var>H</var> of <var>G</var>. The
subgroup generators will be named <var>string</var>1, <var>string</var>2, ... .
<p>
The function accepts the options <code>max</code> and <code>silent</code> as described for the
function <code>CosetTableFromGensAndRels</code> (see <a href="CHAP045.htm#SSEC005.5">CosetTableFromGensAndRels</a>).
<p>
<a name = "SSEC008.3"></a>
<li><code>AugmentedCosetTableRrs( </code><var>G</var><code>, </code><var>table</var><code>, </code><var>type</var><code>, </code><var>string</var><code> ) F</code>
<p>
is an internal function used by the subgroup presentation functions
described in <a href="CHAP046.htm#SECT003">Subgroup Presentations</a>. It
applies the Reduced Reidemeister-Schreier
method to construct an augmented coset table for the subgroup of <var>G</var>
which is defined by the given coset table <var>table</var>. The new subgroup
generators will be named <var>string</var>1, <var>string</var>2, ... .
<p>
<a name = "SSEC008.4"></a>
<li><code>RewriteWord( </code><var>aug</var><code>, </code><var>word</var><code> ) F</code>
<p>
RewriteWord rewrites <var>word</var> (which must be a word in the underlying free
group with respect to which the augmented coset table <var>aug</var> is given) in
the subgroup generators given by the augmented coset table <var>aug</var>. It
returns a Tietze-type word (i.e. a list of integers), referring to the
primary and secondary generators of <var>aug</var>.
<p>
If <var>word</var> is not contained in the subgroup, <code>fail</code> is returned.
<p>
<p>
<h2><a name="SECT009">45.9 Low Index Subgroups</a></h2>
<p><p>
<a name = "I0"></a>
<a name = "SSEC009.1"></a>
<li><code>LowIndexSubgroupsFpGroupIterator( </code><var>G</var><code>[, </code><var>H</var><code>], </code><var>index</var><code>[, </code><var>excluded</var><code>] ) O</code>
<a name = "SSEC009.1"></a>
<li><code>LowIndexSubgroupsFpGroup( </code><var>G</var><code>[, </code><var>H</var><code>], </code><var>index</var><code>[, </code><var>excluded</var><code>] ) O</code>
<p>
These functions compute representatives of the conjugacy classes of
subgroups of the finitely presented group <var>G</var> that contain the subgroup
<var>H</var> of <var>G</var> and that have index less than or equal to <var>index</var>.
<p>
<code>LowIndexSubgroupsFpGroupIterator</code> returns an iterator (see <a href="CHAP028.htm#SECT007">Iterators</a>)
that can be used to run over these subgroups,
and <code>LowIndexSubgroupsFpGroup</code> returns the list of these subgroups.
If one is interested only in one or a few subgroups up to a given index
then preferably the iterator should be used.
<p>
If the optional argument <var>excluded</var> has been specified, then it is
expected to be a list of words in the free generators of the underlying
free group of <var>G</var>, and <code>LowIndexSubgroupsFpGroup</code> returns only those
subgroups of index at most <var>index</var> that contain <var>H</var>, but do not contain
any conjugate of any of the group elements defined by these words.
<p>
If not given, <var>H</var> defaults to the trivial subgroup.
<p>
The algorithm used finds the requested subgroups
by systematically running through a tree of all potential coset tables
of <var>G</var> of length at most <var>index</var> (where it skips all branches of that
tree for which it knows in advance that they cannot provide new classes
of such subgroups). The time required to do this depends, of course, on
the presentation of <var>G</var>, but in general it will grow exponentially with
the value of <var>index</var>. So you should be careful with the choice of
<var>index</var>.
<p>
<pre>
gap> li:=LowIndexSubgroupsFpGroup( g, TrivialSubgroup( g ), 10 );
[ Group(<fp, no generators known>), Group(<fp, no generators known>),
Group(<fp, no generators known>), Group(<fp, no generators known>) ]
</pre>
<p>
By default, the algorithm computes no generating sets for the subgroups.
This can be enforcd with <code>GeneratorsOfGroup</code>:
<pre>
gap> GeneratorsOfGroup(li[2]);
[ a, b*a*b^-1 ]
</pre>
<p>
If we are interested just in one (proper) subgroup of index at most 10,
we can use the function that returns an iterator.
The first subgroup found is the group itself,
except if a list of excluded elements is entered (see below),
so we look at the second subgroup.
<p>
<pre>
gap> iter:= LowIndexSubgroupsFpGroupIterator( g, 10 );;
gap> s1:= NextIterator( iter );; Index( g, s1 );
1
gap> IsDoneIterator( iter );
false
gap> s2:= NextIterator( iter );; s2 = li[2];
true
</pre>
<p>
As an example for an application of the optional parameter <var>excluded</var>, we
compute all conjugacy classes of torsion free subgroups of index at most
24 in the group <i>G</i> = 〈<i>x</i>,<i>y</i>,<i>z</i> | <i>x</i><sup>2</sup>, <i>y</i><sup>4</sup>, <i>z</i><sup>3</sup>, (<i>xy</i>)<sup>3</sup>, (<i>yz</i>)<sup>2</sup>, (<i>xz</i>)<sup>3</sup> 〉. It is know from theory that each torsion element of this
group is conjugate to a power of <i>x</i>, <i>y</i>, <i>z</i>, <i>xy</i>, <i>xz</i>, or <i>yz</i>.
(Note that this includes conjugates of <i>y</i><sup>2</sup>.)
<p>
<pre>
gap> F := FreeGroup( "x", "y", "z" );;
gap> x := F.1;; y := F.2;; z := F.3;;
gap> G := F / [ x^2, y^4, z^3, (x*y)^3, (y*z)^2, (x*z)^3 ];;
gap> torsion := [ x, y, y^2, z, x*y, x*z, y*z ];;
gap> SetInfoLevel( InfoFpGroup, 2 );
gap> lis := LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G ), 24, torsion );;
#I LowIndexSubgroupsFpGroup called
#I class 1 of index 24 and length 8
#I class 2 of index 24 and length 24
#I class 3 of index 24 and length 24
#I class 4 of index 24 and length 24
#I class 5 of index 24 and length 24
#I LowIndexSubgroupsFpGroup done. Found 5 classes
gap> SetInfoLevel( InfoFpGroup, 0 );
</pre>
<p>
If a particular image group is desired, the operation <code>GQuotients</code>
(see <a href="CHAP045.htm#SECT013">Quotient Methods</a>) can be useful as well.
<p>
<p>
<h2><a name="SECT010">45.10 Converting Groups to Finitely Presented Groups</a></h2>
<p><p>
<a name = "SSEC010.1"></a>
<li><code>IsomorphismFpGroup( </code><var>G</var><code> ) A</code>
<p>
returns an isomorphism from the given finite group <var>G</var> to a finitely
presented group isomorphic to <var>G</var>. The function first <strong>chooses a set of
generators of <var>G</var></strong> and then computes a presentation in terms of these
generators.
<p>
<pre>
gap> g := Group( (2,3,4,5), (1,2,5) );;
gap> iso := IsomorphismFpGroup( g );
[ (2,5,4,3), (1,2,3,4,5), (1,3,2,4,5) ] -> [ F1, F2, F3 ]
gap> fp := Image( iso );
<fp group of size 120 on the generators [ F1, F2, F3 ]>
gap> RelatorsOfFpGroup( fp );
[ F1^2*F2^2*F3*F2^-1, F2^-1*F1^-1*F2*F1*F2^-2*F3, F3^-1*F1^-1*F3*F1*F3^-1,
F2^5*F3^-5, F2^5*F3^-1*F2^-1*F3^-1*F2^-1, F2^-2*F3^2*F2^-2*F3^2 ]
</pre>
<p>
<a name = "SSEC010.2"></a>
<li><code>IsomorphismFpGroupByGenerators( </code><var>G</var><code>, </code><var>gens</var><code>[, </code><var>string</var><code>] ) A</code>
<a name = "SSEC010.2"></a>
<li><code>IsomorphismFpGroupByGeneratorsNC( </code><var>G</var><code>, </code><var>gens</var><code>, </code><var>string</var><code> ) A</code>
<p>
returns an isomorphism from a finite group <var>G</var> to a finitely presented
group <var>F</var> isomorphic to <var>G</var>. The generators of <var>F</var> correspond to the
<strong>generators of <var>G</var> given in the list <var>gens</var></strong>. If <var>string</var> is given it
is used to name the generators of the finitely presented group.
<p>
The NC version will avoid testing whether the elements in <var>gens</var>
generate <var>G</var>.
<p>
<pre>
gap> SetInfoLevel( InfoFpGroup, 1 );
gap> iso := IsomorphismFpGroupByGenerators( g, [ (1,2), (1,2,3,4,5) ] );
#I the image group has 2 gens and 5 rels of total length 39
[ (1,2), (1,2,3,4,5) ] -> [ F1, F2 ]
gap> fp := Image( iso );
<fp group of size 120 on the generators [ F1, F2 ]>
gap> RelatorsOfFpGroup( fp );
[ F1^2, F2^5, F2^-1*F1*F2^-1*F1*F2^-1*F1*F2^-1*F1,
F1*F2^-1*F1*F2*F1*F2^-1*F1*F2*F1*F2^-1*F1*F2,
F1*F2^2*F1*F2^-2*F1*F2^2*F1*F2^-2 ]
</pre>
<p>
The main task of the function <code>IsomorphismFpGroupByGenerators</code> is to find a
presentation of <var>G</var> in the provided generators <var>gens</var>. In the case of a
permutation group <var>G</var> it does this by first constructing a stabilizer chain
of <var>G</var> and then it works through that chain from the bottom to the top,
recursively computing a presentation for each of the involved stabilizers.
The method used is essentially an implementation of John Cannon's multi-stage
relations-finding algorithm as described in <a href="biblio.htm#Neu82"><cite>Neu82</cite></a> (see also
<a href="biblio.htm#Can73"><cite>Can73</cite></a> for a more graph theoretical description). Moreover, it makes
heavy use of Tietze transformations in each stage to avoid an explosion of
the total length of the relators.
<p>
Note that because of the random methods involved in the construction of the
stabilizer chain the resulting presentations of <var>G</var> will in general be
different for repeated calls with the same arguments.
<p>
<pre>
gap> M12 := MathieuGroup( 12 );
Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6),
(1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
gap> gens := GeneratorsOfGroup( M12 );;
gap> iso := IsomorphismFpGroupByGenerators( M12, gens );;
#I the image group has 3 gens and 23 rels of total length 680
gap> iso := IsomorphismFpGroupByGenerators( M12, gens );;
#I the image group has 3 gens and 22 rels of total length 604
</pre>
<p>
Also in the case of a permutation group <var>G</var>, the function
<code>IsomorphismFpGroupByGenerators</code> supports the option <code>method</code> that can be
used to modify the strategy. The option <code>method</code> may take the following
values.
<p>
<p>
<dl compact>
<dt><code>method := "regular"</code> <dd>
This may be specified for groups of small size, up to 10<sup>5</sup> say. It
implies that the function first constructs a regular representation <var>R</var>
of <var>G</var> and then a presentation of <var>R</var>. In general, this presentation will
be much more concise than the default one, but the price is the time needed
for the construction of <var>R</var>.
<p>
<dt><code>method := [ "regular", </code><var>bound</var><code> ]</code> <dd>
This is a refinement of the previous possibility. In this case, <var>bound</var>
should be an integer, and if so the method <code>"regular"</code> as described above
is applied to the largest stabilizer in the stabilizer chain of <var>G</var> whose
size does not exceed the given bound and then the multi-stage algorithm is
used to work through the chain from that subgroup to the top.
<p>
<dt><code>method := "fast"</code> <dd>
This chooses an alternative method which essentially is a kind of
multi-stage algorithm for a stabilizer chain of <var>G</var> but does not make any
attempt do reduce the number of relators as it is done in Cannon's
algorithm or to reduce their total length. Hence it is often much faster
than the default method, but the total length of the resulting presentation
may be huge.
<p>
<dt><code>method := "default"</code> <dd>
This simply means that the default method shall be used, which is the case
if the option <code>method</code> is not given a value.
</dl>
<p>
<pre>
gap> iso := IsomorphismFpGroupByGenerators( M12, gens : method := "regular" );;
#I the image group has 3 gens and 11 rels of total length 92
gap> iso := IsomorphismFpGroupByGenerators( M12, gens : method := "fast" );;
#I the image group has 3 gens and 137 rels of total length 3279
</pre>
<p>
Though the option <code>method := "regular"</code> is only checked in the case of a
permutation group it also affects the performance and the results of the
function <code>IsomorphismFpGroupByGenerators</code> for other groups, e. g. for matrix
groups. This happens because, for these groups, the function first calls the
function <code>NiceMonomorphism</code> to get a bijective action homomorphism from <var>G</var>
to a suitable permutation group, <var>P</var> say, and then, recursively, calls itself
for the group <var>P</var> so that now the option becomes relevant.
<p>
<pre>
gap> G := ImfMatrixGroup( 5, 1, 3 );
ImfMatrixGroup(5,1,3)
gap> gens := GeneratorsOfGroup( G );
[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ],
[ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ],
[ [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ],
[ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ] ]
gap> iso := IsomorphismFpGroupByGenerators( G, gens );;
#I the image group has 2 gens and 9 rels of total length 94
gap> iso := IsomorphismFpGroupByGenerators( G, gens : method := "regular" );;
#I the image group has 2 gens and 6 rels of total length 56
gap> SetInfoLevel( InfoFpGroup, 0 );
gap> iso;
<composed isomorphism:[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1,\
0 ], [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ], [ [ 0, 1, 0, 0, 0 ], [ 0, 0\
, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ] ]->[ F1\
, F2 ]>
gap> ConstituentsCompositionMapping(iso);
[ <action isomorphism>, [ (1,7,6)(2,9)(4,5,10), (2,3,4,5)(6,9,8,7) ] ->
[ F1, F2 ] ]
</pre>
<p>
Since <font face="Gill Sans,Helvetica,Arial">GAP</font> cannot decompose elements of a matrix group into generators,
the resulting isomorphism is stored as a composition of a (faithful)
permutation action on vectors and a homomorphism from the permutation image
to the finitely presented group. In such a situation the constituent
mappings can be obtained via <code>ConstituentsCompositionMapping</code> as
separate <font face="Gill Sans,Helvetica,Arial">GAP</font> objects.
<p>
<p>
<h2><a name="SECT011">45.11 New Presentations and Presentations for Subgroups</a></h2>
<p><p>
<a name = "I1"></a>
<code>IsomorphismFpGroup</code> is also used to compute a new finitely presented group
that is isomorphic to the subgroup of a given finitely presented group.
(This is typically the only method to compute with subgroups of a finitely
presented group.)
<p>
<pre>
gap> f:=FreeGroup(2);;
gap> g:=f/[f.1^2,f.2^3,(f.1*f.2)^5];
<fp group on the generators [ f1, f2 ]>
gap> u:=Subgroup(g,[g.1*g.2]);
Group([ f1*f2 ])
gap> hom:=IsomorphismFpGroup(u);
[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ] -> [ F1 ]
gap> new:=Range(hom);
<fp group on the generators [ F1 ]>
gap> List(GeneratorsOfGroup(new),i->PreImagesRepresentative(hom,i));
[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ]
</pre>
<p>
When working with such homomorphisms, some subgroup elements are expressed
as extremely long words in the group generators. Therefore the underlying
words of subgroup
generators stored in the isomorphism (as obtained by
<code>MappingGeneratorImages</code> and displayed when <code>View</code>ing the homomorphism) as
well as preimages under the homomorphism are stored in the form of straight
line program elements (see <a href="CHAP035.htm#SECT009">Straight Line Program Elements</a>). These will
behave like ordinary words and no extra treatment should be necessary.
<p>
<pre>
gap> r:=Range(hom).1^10;
F1^10
gap> p:=PreImagesRepresentative(hom,r);
<[ [ 1, 10 ] ]|f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1>
</pre>
If desired, it also is possible to convert these underlying words using
<code>EvalStraightLineProgElm</code>:
<pre>
gap> r:=EvalStraightLineProgElm(UnderlyingElement(p));
f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1
gap> p:=ElementOfFpGroup(FamilyObj(p),r);
f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1
</pre>
<p>
(If you are only interested in a finitely presented group isomorphic to <var>U</var>,
but not in the isomorphism, you may also use the functions
<code>PresentationViaCosetTable</code> and <code>FpGroupPresentation</code> (see <a href="CHAP046.htm#SECT001">Creating Presentations</a>).)
<p>
Homomorphisms can also be used to obtain an isomorphic finitely presented
group with a (hopefully) simpler presentation.
<p>
<a name = "SSEC011.1"></a>
<li><code>IsomorphismSimplifiedFpGroup( </code><var>G</var><code> ) A</code>
<p>
applies Tietze transformations to a copy of the presentation of the
given finitely presented group <var>G</var> in order to reduce it with respect to
the number of generators, the number of relators, and the relator
lengths.
<p>
The operation returns an isomorphism with source <var>G</var>, range a group
<var>H</var> isomorphic to <var>G</var>, so that the presentation of <var>H</var> has been
simplified using Tietze transformations.
<p>
<pre>
gap> f:=FreeGroup(3);;
gap> g:=f/[f.1^2,f.2^3,(f.1*f.2)^5,f.1/f.3];
<fp group on the generators [ f1, f2, f3 ]>
gap> hom:=IsomorphismSimplifiedFpGroup(g);
[ f1, f2, f3 ] -> [ f1, f2, f1 ]
gap> Range(hom);
<fp group on the generators [ f1, f2 ]>
gap> RelatorsOfFpGroup(Range(hom));
[ f1^2, f2^3, f1*f2*f1*f2*f1*f2*f1*f2*f1*f2 ]
gap> RelatorsOfFpGroup(g);
[ f1^2, f2^3, f1*f2*f1*f2*f1*f2*f1*f2*f1*f2, f1*f3^-1 ]
</pre>
<p>
(<code>IsomorphismSimplifiedFpGroup</code> uses Tietze transformations to simplify the
presentation, see <a href="CHAP046.htm#SSEC002.1">SimplifiedFpGroup</a>.)
<p>
<p>
<h2><a name="SECT012">45.12 Preimages under Homomorphisms from an FpGroup</a></h2>
<p><p>
For some subgroups of a finitely presented group the number of
subgroup generators increases with the index of the subgroup. However often
these generators are not needed at all for further calculations, but what is
needed is the action of the cosets of the subgroup. This gives the image of
the subgroup in a finite quotient and this finite quotient can be used to
calculate normalizers, closures, intersections and so
forth <a href="biblio.htm#HulpkeQuot"><cite>HulpkeQuot</cite></a>.
<p>
The same applies for subgroups that are obtained as preimages under
homomorphisms.
<p>
<a name = "SSEC012.1"></a>
<li><code>SubgroupOfWholeGroupByQuotientSubgroup( </code><var>fpfam</var><code>, </code><var>Q</var><code>, </code><var>U</var><code> ) F</code>
<p>
takes a fp group family <var>fpfam</var>, a finitely generated group <var>Q</var> such that
the fp generators of <var>fam</var> can be mapped by an epimorphism <var>phi</var> onto
<code>GeneratorsOfGroup(</code><var>Q</var><code>)</code> and a subgroup <var>U</var> of <var>Q</var>.
It returns the subgroup of <code></code><var>fam</var><code>!.wholeGroup</code> which is the full
preimage of <var>U</var> under <var>phi</var>.
<p>
<a name = "SSEC012.2"></a>
<li><code>IsSubgroupOfWholeGroupByQuotientRep( </code><var>G</var><code> ) R</code>
<p>
is the representation for subgroups of an fp group, given by a quotient
subgroup. The components <code></code><var>G</var><code>!.quot</code> and <code></code><var>G</var><code>!.sub</code> hold quotient,
respectively subgroup.
<p>
<a name = "SSEC012.3"></a>
<li><code>AsSubgroupOfWholeGroupByQuotient( </code><var>U</var><code> ) A</code>
<p>
returns the same subgroup in the representation
<code>AsSubgroupOfWholeGroupByQuotient</code>.
<p>
See also <code>SubgroupOfWholeGroupByCosetTable</code>
(<a href="CHAP045.htm#SSEC007.2">SubgroupOfWholeGroupByCosetTable</a>) and <code>CosetTableBySubgroup</code>
(<a href="CHAP045.htm#SSEC005.4">CosetTableBySubgroup</a>).
<p>
This technique is used by <font face="Gill Sans,Helvetica,Arial">GAP</font> for example to represent the derived
subgroup, which is obtained from the quotient <i>G</i>/<i>G</i>′.
<pre>
gap> f:=FreeGroup(2);;g:=f/[f.1^6,f.2^6,(f.1*f.2)^6];;
gap> d:=DerivedSubgroup(g);
Group(<fp, no generators known>)
gap> Index(g,d);
36
</pre>
<p>
<a name = "SSEC012.4"></a>
<li><code>DefiningQuotientHomomorphism( </code><var>U</var><code> ) F</code>
<p>
if <var>U</var> is a subgroup in quotient representation
(<code>IsSubgroupOfWholeGroupByQuotientRep</code>), this function returns the
defining homomorphism from the whole group to <code></code><var>U</var><code>!.quot</code>.
<p>
<p>
<h2><a name="SECT013">45.13 Quotient Methods</a></h2>
<p><p>
An important class of algorithms for finitely presented groups are the
<strong>quotient algorithms</strong> which compute quotient groups of a given finitely
presented group.
<p>
<code> MaximalAbelianQuotient(</code><var>fpgroup</var><code>) </code>
<p>
as defined for general groups, this attribute returns the largest abelian
quotient of <var>fpgroup</var>.
<pre>
gap> f:=FreeGroup(2);;fp:=f/[f.1^6,f.2^6,(f.1*f.2)^12];
<fp group on the generators [ f1, f2 ]>
gap> hom:=MaximalAbelianQuotient(fp);
[ f1, f2 ] -> [ f1, f3 ]
gap> Size(Image(hom));
36
</pre>
<p>
<a name = "SSEC013.1"></a>
<li><code>PQuotient( </code><var>F</var><code>, </code><var>p</var><code> [, </code><var>c</var><code>] [, </code><var>logord</var><code>] [, </code><var>ctype</var><code>] ) F</code>
<p>
computes a factor <var>p</var>-group of a finitely presented group <var>F</var> in form
of a quotient system. The quotient system can be converted into an
epimorphism from <var>F</var> onto the <var>p</var>-group computed by the function
<a href="CHAP045.htm#SSEC013.2">EpimorphismQuotientSystem</a>.
<p>
For a group <i>G</i> define the exponent-<i>p</i> central series of <i>G</i> inductively
by <font face="helvetica"><i>P</i></font><sub>1</sub>(<i>G</i>) = <i>G</i> and <font face="helvetica"><i>P</i></font><sub><i>i</i>+1</sub>(<i>G</i>) = [<font face="helvetica"><i>P</i></font><sub><i>i</i></sub>(<i>G</i>),<i>G</i>]<font face="helvetica"><i>P</i></font><sub><i>i</i>+1</sub>(<i>G</i>)<sup><i>p</i></sup>· The factor groups modulo the terms of the lower
exponent-<i>p</i> central series are <i>p</i>-groups. The group <i>G</i> has <i>p</i>-class
<i>c</i> if <font face="helvetica"><i>P</i></font><sub><i>c</i></sub>(<i>G</i>) ≠ <font face="helvetica"><i>P</i></font><sub><i>c</i>+1</sub>(<i>G</i>)=1·
<p>
The algorithm computes successive quotients modulo the terms of the
exponent-<i>p</i> central series of <var>F</var>. If the parameter <var>c</var> is present,
then the factor group modulo the (<i>c</i>+1)-th term of the exponent-<i>p</i>
central series of <var>F</var> is returned. If <var>c</var> is not present, then the
algorithm attempts to compute the largest factor <var>p</var>-group of <var>F</var>. In
case <var>F</var> does not have a largest factor <var>p</var>-group, the algorithm will not
terminate.
<p>
By default the algorithm computes only with factor groups of order at
most <i>p</i><sup>256</sup>· If the parameter <var>logord</var> is present, it will compute
with factor groups of order atmost <i>p</i><sup><i>logord</i> </sup>· If this parameter is
specified, then the parameter <var>c</var> must also be given. The present
implementation produces an error message if the order of a <i>p</i>-quotient
exceeds <i>p</i><sup>256</sup> or <i>p</i><sup><i>logord</i> </sup>, respectively. Note that the order of
intermediate <i>p</i>-groups may be larger than the final order of a
<i>p</i>-quotient.
<p>
The parameter <var>ctype</var> determines the type of collector that is used for
computations within the factor <var>p</var>-group. <var>ctype</var> must either be
<code>single</code> in which case a simple collector from the left is used or
<code>combinatorial</code> in which case a combinatorial collector from the left is
used.
<p>
<a name = "SSEC013.2"></a>
<li><code>EpimorphismQuotientSystem( </code><var>quotsys</var><code> ) O</code>
<p>
For a quotient system <var>quotsys</var> obtained from the function <a href="CHAP045.htm#SSEC013.1">PQuotient</a>,
this operation returns an epimorphism <i>F</i> →<i>P</i> where <i>F</i> is the
finitely presented group of which <var>quotsys</var> is a quotient system and
<i>P</i> is a <code>PcGroup</code> isomorphic to the quotient of <var>F</var> determined by
<var>quotsys</var>.
<p>
Different calls to this operation will create different groups <var>P</var>, each
with its own family.
<p>
<pre>
gap> PQuotient( FreeGroup(2), 5, 10, 1024, "combinatorial" );
<5-quotient system of 5-class 10 with 520 generators>
gap> phi := EpimorphismQuotientSystem( last );
[ f1, f2 ] -> [ a1, a2 ]
gap> Collected( Factors( Size( Image( phi ) ) ) );
[ [ 5, 520 ] ]
</pre>
<a name = "SSEC013.3"></a>
<li><code>EpimorphismPGroup( </code><var>fpgrp</var><code>, </code><var>p</var><code> ) O</code>
<li><code>EpimorphismPGroup( </code><var>fpgrp</var><code>, </code><var>p</var><code>, </code><var>cl</var><code> ) O</code>
<p>
computes an epimorphism from the finitely presented group <var>fpgrp</var> to the
largest <i>p</i>-group of <i>p</i>-class <var>cl</var> which is a quotient of <var>fpgrp</var>. If <var>cl</var>
is omitted, the largest finite <i>p</i>-group quotient (of <i>p</i>-class up to
1000) is determined.
<p>
<pre>
gap> hom:=EpimorphismPGroup(fp,2);
[ f1, f2 ] -> [ a1, a2 ]
gap> Size(Image(hom));
8
gap> hom:=EpimorphismPGroup(fp,3,7);
[ f1, f2 ] -> [ a1, a2 ]
gap> Size(Image(hom));
6561
</pre>
<p>
<a name = "SSEC013.4"></a>
<li><code>EpimorphismNilpotentQuotient( </code><var>fpgrp</var><code>[, </code><var>n</var><code>] ) F</code>
<p>
returns an epimorphism on the class <var>n</var> finite nilpotent quotient of the
finitely presented group <var>fpgrp</var>. If <var>n</var> is omitted, the largest
finite nilpotent quotient (of <i>p</i>-class up to 1000) is taken.
<p>
<pre>
gap> hom:=EpimorphismNilpotentQuotient(fp,7);
[ f1, f2 ] -> [ f1*f4, f2*f5 ]
gap> Size(Image(hom));
52488
</pre>
<p>
A related operation which is also applicable to finitely presented groups is
<code>GQuotients</code>, which computes all epimorphisms from a (finitely presented)
group <var>F</var> onto a given (finite) group <var>G</var>, see <a href="CHAP038.htm#SSEC009.2">GQuotients</a>.
<pre>
gap> GQuotients(fp,Group((1,2,3),(1,2)));
[ [ f1, f2 ] -> [ (2,3), (1,2) ], [ f1, f2 ] -> [ (2,3), (1,2,3) ],
[ f1, f2 ] -> [ (1,2,3), (1,2) ] ]
</pre>
<p>
<p>
<h2><a name="SECT014">45.14 Abelian Invariants for Subgroups</a></h2>
<p><p>
Using variations of coset enumeration it is possible to compute the abelian
invariants of a subgroup of a finitely presented group without computing a
complete presentation for the subgroup in the first place. Typically, the
operation <code>AbelianInvariants</code> when called for subgroups should automatically
take care of this, but in case you what to have further control about the
methods used, the following operations might be of use.
<p>
<a name = "SSEC014.1"></a>
<li><code>AbelianInvariantsSubgroupFpGroup( </code><var>G</var><code>, </code><var>H</var><code> ) F</code>
<p>
is a synonym for <code>AbelianInvariantsSubgroupFpGroupRrs(</code><var>G</var><code>,</code><var>H</var><code>)</code>.
<p>
<a name = "SSEC014.2"></a>
<li><code>AbelianInvariantsSubgroupFpGroupMtc( </code><var>G</var><code>, </code><var>H</var><code> ) F</code>
<p>
uses the Modified Todd-Coxeter method to compute the abelian
invariants of a subgroup <var>H</var> of a finitely presented group <var>G</var>.
<p>
<a name = "SSEC014.3"></a>
<li><code>AbelianInvariantsSubgroupFpGroupRrs( </code><var>G</var><code>, </code><var>H</var><code> ) F</code>
<li><code>AbelianInvariantsSubgroupFpGroupRrs( </code><var>G</var><code>, </code><var>table</var><code> ) F</code>
<p>
uses the Reduced Reidemeister-Schreier method to compute the abelian
invariants of a subgroup <var>H</var> of a finitely presented group <var>G</var>.
<p>
Alternatively to the subgroup <var>H</var>, its coset table <var>table</var> in <var>G</var> may be
given as second argument.
<p>
<a name = "SSEC014.4"></a>
<li><code>AbelianInvariantsNormalClosureFpGroup( </code><var>G</var><code>, </code><var>H</var><code> ) F</code>
<p>
is a synonym for <code>AbelianInvariantsNormalClosureFpGroupRrs(</code><var>G</var><code>,</code><var>H</var><code>)</code>.
<p>
<a name = "SSEC014.5"></a>
<li><code>AbelianInvariantsNormalClosureFpGroupRrs( </code><var>G</var><code>, </code><var>H</var><code> ) F</code>
<p>
uses the Reduced Reidemeister-Schreier method to compute the abelian
invariants of the normal closure of a subgroup <var>H</var> of a finitely
presented group <var>G</var>.
<p>
See <a href="CHAP046.htm#SECT003">Subgroup Presentations</a> for details on the different strategies.
<p>
The following example shows a calculation for the Coxeter group <i>B</i><sub>1</sub>.
This calculation and a similar one for <i>B</i><sub>0</sub> have been used to prove that
<i>B</i><sub>1</sub>′/ <i>B</i><sub>1</sub><sup>′′</sup> ≅ <i>Z</i><sub>2</sub><sup>9</sup> ×<i>Z</i><sup>3</sup> and <i>B</i><sub>0</sub>′/ <i>B</i><sub>0</sub><sup>′′</sup> ≅ <i>Z</i><sub>2</sub><sup>91</sup> ×<i>Z</i><sup>27</sup> as stated in Proposition 5
in <a href="biblio.htm#FJNT95"><cite>FJNT95</cite></a>.
<p>
<pre>
gap> # Define the Coxeter group E1.
gap> F := FreeGroup( "x1", "x2", "x3", "x4", "x5" );
<free group on the generators [ x1, x2, x3, x4, x5 ]>
gap> x1 := F.1;; x2 := F.2;; x3 := F.3;; x4 := F.4;; x5 := F.5;;
gap> rels := [ x1^2, x2^2, x3^2, x4^2, x5^2,
> ( x1 * x3 )^2, ( x2 * x4 )^2, ( x1 * x2 )^3, ( x2 * x3 )^3, ( x3 * x4 )^3,
> ( x4 * x1 )^3, ( x1 * x5 )^3, ( x2 * x5 )^2, ( x3 * x5 )^3, ( x4 * x5 )^2,
> ( x1 * x2 * x3 * x4 * x3 * x2 )^2 ];;
gap> E1 := F / rels;
<fp group on the generators [ x1, x2, x3, x4, x5 ]>
gap> x1 := E1.1;; x2 := E1.2;; x3 := E1.3;; x4 := E1.4;; x5 := E1.5;;
gap> # Get normal subgroup generators for B1.
gap> H := Subgroup( E1, [ x5 * x2^-1, x5 * x4^-1 ] );;
gap> # Compute the abelian invariants of B1/B1'.
gap> A := AbelianInvariantsNormalClosureFpGroup( E1, H );
[ 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> # Compute a presentation for B1.
gap> P := PresentationNormalClosure( E1, H );
<presentation with 18 gens and 46 rels of total length 132>
gap> SimplifyPresentation( P );
#I there are 8 generators and 30 relators of total length 148
gap> B1 := FpGroupPresentation( P );
<fp group on the generators [ _x1, _x2, _x3, _x4, _x6, _x7, _x8, _x11 ]>
gap> # Compute normal subgroup generators for B1'.
gap> gens := GeneratorsOfGroup( B1 );;
gap> numgens := Length( gens );;
gap> comms := [ ];;
gap> for i in [ 1 .. numgens - 1 ] do
> for j in [i+1 .. numgens ] do
> Add( comms, Comm( gens[i], gens[j] ) );
> od;
> od;
gap> # Compute the abelian invariants of B1'/B1".
gap> K := Subgroup( B1, comms );;
gap> A := AbelianInvariantsNormalClosureFpGroup( B1, K );
[ 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
</pre>
<p>
<p>
<h2><a name="SECT015">45.15 Testing Finiteness of Finitely Presented Groups</a></h2>
<p><p>
As a consequence of the algorithmic insolvabilities mentioned in the
introduction to this chapter, there cannot be a general method that will
test whether a given finitely presented group is actually finite.
<p>
Therefore testing a finitely presented group for <code>IsFinite</code> can be
problematic. What <font face="Gill Sans,Helvetica,Arial">GAP</font> actually does upon a call of <code>IsFinite</code> (or if it
is -- probably implicitly -- asked for a faithful permutation
representation) is to test whether it can find (via coset enumeration) a
cyclic subgroup of finite index. If it can, it rewrites the presentation to
this subgroup. Since the subgroup is cyclic, its size can be checked easily
from the resulting presentation, the size of the whole group is the product
of the index and the subgroup size. Since however no bound for the index of
such a subgroup (if any exist) is known, such a test might continue
unsuccesfully until memory is exhausted.
<p>
On the other hand, a couple of methods exist, that might prove that a group
is infinite. Again, none is guaranteed to work in every case:
<p>
The first method is to find (for example via the low index algorithm,
see <code>LowIndexSubgroupsFpGroup</code>) a subgroup <i>U</i> such that [<i>U</i>:<i>U</i>′] is
infinite. If <i>U</i> has finite index, this can be checked by the operation
<code>AbelianInvariants</code> (see section <a href="CHAP045.htm#SECT014">Abelian Invariants for Subgroups</a> for an
example).
<p>
Another method is based on <i>p</i>-group quotients:
<a name = "SSEC015.1"></a>
<li><code>NewmanInfinityCriterion( </code><var>G</var><code>, </code><var>p</var><code> ) F</code>
<p>
Let <var>G</var> be a finitely presented group and <var>p</var> a prime that divides the
order of <i>G</i> /<i>G</i> ′. This function applies an infinity
criterion due to M.F. Newman <a href="biblio.htm#New90"><cite>New90</cite></a> to <var>G</var>. (See chapter 16
of <a href="biblio.htm#Joh97"><cite>Joh97</cite></a> for a more explicit description.)
It returns <code>true</code>
if the criterion succeeds in proving that <var>G</var> is infinite and <code>fail</code>
otherwise.
<p>
Note that the criterion uses the number of generators and
relations in the presentation of <var>G</var>. Reduction of the persentation via
Tietze transformations (<code>IsomorphismSimplifiedFpGroup</code>) therefore might
produce an isomorphic group, for which the criterion will work better.
<p>
<pre>
gap> g:=FibonacciGroup(2,9);
<fp group on the generators [ f1, f2, f3, f4, f5, f6, f7, f8, f9 ]>
gap> hom:=EpimorphismNilpotentQuotient(g,2);;
gap> k:=Kernel(hom);;
gap> Index(g,k);
152
gap> AbelianInvariants(k);
[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]
gap> NewmanInfinityCriterion(Kernel(hom),5);
true
</pre>
<p>
This proves that the subgroup <var>k</var> (and thus the whole group <var>g</var>) is
infinite. (This is the original example from <a href="biblio.htm#New90"><cite>New90</cite></a>.)
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP044.htm">Previous</a>] [<a href ="CHAP046.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
>
187
