<html><head><title>[FGA] 2 Functionality of the FGA package</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>2 Functionality of the FGA package</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP002.htm#SECT001">New operations for free groups</a>
<li> <A HREF="CHAP002.htm#SECT002">Method installations</a>
<li> <A HREF="CHAP002.htm#SECT003">Constructive membership test</a>
<li> <A HREF="CHAP002.htm#SECT004">Automorphism groups of free groups</a>
</ol><p>
<p>
<a name = "I0"></a>
This chapter describes methods available from the <font face="Gill Sans,Helvetica,Arial">FGA</font> package.
<p>
In the following, let <var>f</var> be a free group created by <code>FreeGroup(</code><var>n</var><code>)</code>,
and let <var>u</var>, <var>u1</var> and <var>u2</var> be finitely generated subgroups of <var>f</var>
created by <code>Group</code> or <code>Subgroup</code>, or computed from some other subgroup
of <var>f</var>. Let <var>elm</var> be an element of <var>f</var>.
<p>
For example:
<p>
<pre>
gap> f := FreeGroup( 2 );
<free group on the generators [ f1, f2 ]>
gap> u := Group( f.1^2, f.2^2, f.1*f.2 );
Group([ f1^2, f2^2 ])
gap> u1 := Subgroup( u, [f.1^2, f.1^4*f.2^6] );
Group([ f1^2, f1^4*f2^6 ])
gap> elm := f.1;
f1
gap> u2 := Normalizer( u, elm );
Group([ f1^2 ])
</pre>
<p>
<p>
<h2><a name="SECT001">2.1 New operations for free groups</a></h2>
<p><p>
These new operations are available for finitely generated subgroups of
free groups:
<p>
<a name = "SSEC001.1"></a>
<li><code>FreeGeneratorsOfGroup( </code><var>u</var><code> ) A</code>
<p>
returns a list of free generators of the finitely generated subgroup
<var>u</var> of a free group.
<p>
The elements in this list form an N-reduced set. In addition to
being a free (and thus minimal) generating set for <var>u</var>, this means
that whenever <var>v1</var>, <var>v2</var> and <var>v3</var> are elements or inverses of elements
of this list, then
<p>
<ul>
<li>
<var><var>v1</var><var>v2</var>neq1</var> implies <var>|<var>v1</var><var>v2</var>|geqmax(|<var>v1</var>|, |<var>v2</var>|)</var>, and
<li>
<var><var>v1</var><var>v2</var>neq1</var> and <var><var>v2</var><var>v3</var>neq1</var> implies
<var>|<var>v1</var><var>v2</var><var>v3</var>| > |<var>v1</var>| - |<var>v2</var>| + |<var>v3</var>|</var>
</ul>
<p>
hold, where <var>|.|</var> denotes the word length.
<p>
<a name = "SSEC001.2"></a>
<li><code>RankOfFreeGroup( </code><var>u</var><code> ) A</code>
<a name = "SSEC001.2"></a>
<li><code>Rank( </code><var>u</var><code> ) O</code>
<p>
returns the rank of the finitely generated subgroup <var>u</var> of a free
group.
<p>
<a name = "SSEC001.3"></a>
<li><code>CyclicallyReducedWord( </code><var>elm</var><code> ) O</code>
<p>
returns the cyclically reduced form of <var>elm</var>.
<p>
<p>
<h2><a name="SECT002">2.2 Method installations</a></h2>
<p><p>
This section lists operations that are already known to <font face="Gill Sans,Helvetica,Arial">GAP</font>.
<font face="Gill Sans,Helvetica,Arial">FGA</font> installs new methods for them so that they can also be used
with free groups.
In cases where <font face="Gill Sans,Helvetica,Arial">FGA</font> installs methods that are usually only used
internally, user functions are shown instead.
<p>
<a name = "SSEC002.1"></a>
<li><code>Normalizer( </code><var>u1</var><code>, </code><var>u2</var><code> ) O</code>
<li><code>Normalizer( </code><var>u</var><code>, </code><var>elm</var><code> ) O</code>
<p>
The first variant returns the normalizer of the finitely generated
subgroup <var>u2</var> in <var>u1</var>.
<p>
The second variant returns the normalizer of <var>langle<var>elm</var> rangle</var>
in the finitely generated subgroup <var>u</var> (see <a href="../../../doc/htm/ref/CHAP037.htm#SSEC010.1">Normalizer</a> in the
Reference Manual).
<p>
<a name = "SSEC002.2"></a>
<li><code>RepresentativeAction( </code><var>u</var><code>, </code><var>d</var><code>, </code><var>e</var><code> ) O</code>
<a name = "SSEC002.2"></a>
<li><code>IsConjugate( </code><var>u</var><code>, </code><var>d</var><code>, </code><var>e</var><code> ) O</code>
<p>
<code>RepresentativeAction</code> returns an element <var> <var>r</var> in<var>u</var> </var>,
where <var>u</var> is a finitely generated subgroup of a free group, such
that <var><var>d</var><sup><var>r</var></sup>=<var>e</var></var>, or fail, if no such <var>r</var> exists. <var>d</var> and <var>e</var> may
be elements or subgroups of <var>u</var>.
<p>
<code>IsConjugate</code> returns a boolean indicating whether such an element <var>r</var>
exists.
<p>
<a name = "SSEC002.3"></a>
<li><code>Centralizer( </code><var>u</var><code>, </code><var>u2</var><code> ) O</code>
<li><code>Centralizer( </code><var>u</var><code>, </code><var>elm</var><code> ) O</code>
<p>
returns the centralizer of <var>u2</var> or <var>elm</var> in the finitely generated
subgroup <var>u</var> of a free group.
<p>
<a name = "SSEC002.4"></a>
<li><code>Index( </code><var>u1</var><code>, </code><var>u2</var><code> ) O</code>
<a name = "SSEC002.4"></a>
<li><code>IndexNC( </code><var>u1</var><code>, </code><var>u2</var><code> ) O</code>
<p>
return the index of <var>u2</var> in <var>u1</var>, where <var>u1</var> and <var>u2</var> are finitely
generated subgroups of a free group. The first variant returns
fail if <var>u2</var> is not a subgroup of <var>u1</var>, the second may return
anything in this case.
<p>
<a name = "SSEC002.5"></a>
<li><code>Intersection( </code><var>u1</var><code>, </code><var>u2</var><code> ...) F</code>
<p>
returns the intersection of <var>u1</var> and <var>u2</var>, where <var>u1</var> and <var>u2</var> are
finitely generated subgroups of a free group.
<p>
<a name = "SSEC002.6"></a>
<li><code></code><var>elm</var><code> in </code><var>u</var><code> O</code>
<p>
tests whether <var>elm</var> is contained in the finitely generated subgroup
<var>u</var> of a free group.
<p>
<a name = "SSEC002.7"></a>
<li><code>IsSubgroup( </code><var>u1</var><code>, </code><var>u2</var><code> ) F</code>
<p>
tests whether <var>u2</var> is a subgroup of <var>u1</var>, where <var>u1</var> and <var>u2</var> are finitely
generated subgroups of a free group.
<p>
<a name = "SSEC002.8"></a>
<li><code></code><var>u1</var><code> = </code><var>u2</var><code> O</code>
<p>
test whether the two finitely generated subgroups <var>u1</var> and <var>u2</var> of a
free group are equal.
<p>
<a name = "SSEC002.9"></a>
<li><code>MinimalGeneratingSet( </code><var>u</var><code> ) A</code>
<a name = "SSEC002.9"></a>
<li><code>SmallGeneratingSet( </code><var>u</var><code> ) A</code>
<a name = "SSEC002.9"></a>
<li><code>GeneratorsOfGroup( </code><var>u</var><code> ) A</code>
<p>
return generating sets for the finitely generated subgroup <var>u</var> of a
free group. <code>MinimalGeneratingSet</code> and <code>SmallGeneratingSet</code> return
the same free generators as <code>FreeGeneratorsOfGroup</code>, which are in
fact a minimal generating set. <code>GeneratorsOfGroup</code> also returns these
generators, if no other generators were stored at creation time.
<p>
<p>
<h2><a name="SECT003">2.3 Constructive membership test</a></h2>
<p><p>
It is not only possible to test whether an element is in a finitely
generated subgroup of free group, this can also be done
constructively. The idiomatic way to do so is by using a
homomorphism.
<p>
Here is an example that computes how to write <code>f.1^2</code> in the
generators <code>a=f1^2*f2^2</code> and <code>b=f.1^2*f.2</code>, checks the result, and
then tries to write <code>f.1</code> in the same generators:
<p>
<pre>
gap> f := FreeGroup( 2 );
<free group on the generators [ f1, f2 ]>
gap> ua := f.1^2*f.2^2;; ub := f.1^2*f.2;;
gap> u := Group( ua, ub );;
gap> g := FreeGroup( "a", "b" );;
gap> hom := GroupHomomorphismByImages( g, u,
GeneratorsOfGroup(g),
GeneratorsOfGroup(u) );
[ a, b ] -> [ f1^2*f2^2, f1^2*f2 ]
gap> # how can f.1^2 be expressed?
gap> PreImagesRepresentative( hom, f.1^2 );
b*a^-1*b
gap> last ^ hom; # check this
f1^2
gap> ub * ua^-1 * ub; # another check
f1^2
gap> PreImagesRepresentative( hom, f.1 ); # try f.1
fail
gap> f.1 in u;
false
</pre>
<p>
There are also lower level operations to get the same results.
In fact, they are faster when used repeatedly with the same group.
<p>
<a name = "SSEC003.1"></a>
<li><code>AsWordLetterRepInGenerators( </code><var>elm</var><code>, </code><var>u</var><code> ) O</code>
<a name = "SSEC003.1"></a>
<li><code>AsWordLetterRepInFreeGenerators( </code><var>elm</var><code>, </code><var>u</var><code> ) O</code>
<p>
return a letter representation
(see Section <a href="../../../doc/htm/ref/CHAP035.htm#SECT006">Representations for Associative Words</a> in the <font face="Gill Sans,Helvetica,Arial">GAP</font>
Reference Manual)
of the given <var>elm</var> relative to the generators the group was created
with or the free generators as returned by <code>FreeGeneratorsOfGroup</code>.
<p>
Continuing the above example:
<p>
<pre>
gap> AsWordLetterRepInGenerators( f.1^2, u );
[ 2, -1, 2 ]
gap> AsWordLetterRepInFreeGenerators( f.1^2, u );
[ 2 ]
</pre>
<p>
This means: to get <code>f.1^2</code>, multiply the second of the given generators
with the inverse of the first and again with the second; or just take
the second free generator.
<p>
<p>
<h2><a name="SECT004">2.4 Automorphism groups of free groups</a></h2>
<p><p>
The <font face="Gill Sans,Helvetica,Arial">FGA</font> package knows presentations of the automorphism groups of free
groups. It also allows to express an automorphism as word in the
generators of these presentations.
This sections repeats the <font face="Gill Sans,Helvetica,Arial">GAP</font> standard methods to do so and shows
functions to obtain the generating automorphisms.
<p>
<a name = "SSEC004.1"></a>
<li><code>AutomorphismGroup( </code><var>u</var><code> ) A</code>
<p>
returns the automorphism group of the finitely generated subgroup <var>u</var>
of a free group.
<p>
Only a few methods will work with this group. But there is a way to
obtain an isomorphic finitely presented group:
<p>
<a name = "SSEC004.2"></a>
<li><code>IsomorphismFpGroup( </code><var>group</var><code> ) A</code>
<p>
returns an isomorphism of <var>group</var> to a finitely presented group.
For automorphism groups of free groups, the <font face="Gill Sans,Helvetica,Arial">FGA</font> package implements
the presentations of <a href="biblio.htm#Neumann33"><cite>Neumann33</cite></a>.
The finitely presented group itself can then be obtained with the
command <code>Range</code>.
<p>
Here is an example:
<p>
<pre>
gap> f := FreeGroup( 2 );;
gap> a := AutomorphismGroup( f );;
gap> iso := IsomorphismFpGroup( a );;
gap> Range( iso );
<fp group on the generators [ O, P, U ]>
</pre>
<p>
To express an automorphism as word in the generators of the
presentation, just apply the isomorphism obtained from
<code>IsomorphismFpGroup</code>.
<p>
<pre>
gap> aut := GroupHomomorphismByImages( f, f,
GeneratorsOfGroup( f ), [ f.1^f.2, f.1*f.2 ] );
[ f1, f2 ] -> [ f2^-1*f1*f2, f1*f2 ]
gap> ImageElm( iso, aut );
O^2*U*O*P^-1*U
</pre>
<p>
It is also possible to use <code>aut^iso</code>.
Please note that using <code>Image</code> does not work.
<p>
The <font face="Gill Sans,Helvetica,Arial">FGA</font> package provides a simpler way to create endomorphisms:
<p>
<a name = "SSEC004.3"></a>
<li><code>FreeGroupEndomorphismByImages( </code><var>g</var><code>, </code><var>imgs</var><code> ) F</code>
<p>
returns the endomorphism that maps the free generators of the finitely
generated subgroup <var>g</var> of a free group to the elements listed in <var>imgs</var>.
You may then apply <code>IsBijective</code> to check whether it is an
automorphism.
<p>
The follwowing functions return automorphisms that correspond to the
generators in the presentation:
<p>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorO( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorP( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorU( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorS( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorT( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorQ( </code><var>group</var><code> ) F</code>
<a name = "SSEC004.4"></a>
<li><code>FreeGroupAutomorphismsGeneratorR( </code><var>group</var><code> ) F</code>
<p>
return the automorphism which maps the free generators
[<var> x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub> </var>] of <var>group</var> to
<dl compact>
<dt>O:<dd>[<var> x<sub>1</sub><sup>-1</sup>, x<sub>2</sub>, ..., x<sub>n</sub> </var>] (<var>nge1</var>)
<dt>P:<dd>[<var> x<sub>2</sub>, x<sub>1</sub>, x<sub>3</sub>, ..., x<sub>n</sub> </var>] (<var>nge2</var>)
<dt>U:<dd>[<var> x<sub>1</sub>x<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, ..., x<sub>n</sub> </var>] (<var>nge2</var>)
<dt>S:<dd>[<var> x<sub>2</sub><sup>-1</sup>, x<sub>3</sub><sup>-1</sup>, ..., x<sub>n</sub><sup>-1</sup>, x<sub>1</sub><sup>-1</sup> </var>] (<var>nge1</var>)
<dt>T:<dd>[<var> x<sub>2</sub>, x<sub>1</sub><sup>-1</sup>, x<sub>3</sub>, ..., x<sub>n</sub> </var>] (<var>nge2</var>)
<dt>Q:<dd>[<var> x<sub>2</sub>, x<sub>3</sub>, ..., x<sub>n</sub>, x<sub>1</sub> </var>] (<var>nge2</var>)
<dt>R:<dd>[<var> x<sub>2</sub><sup>-1</sup>, x<sub>1</sub>, x<sub>3</sub>, x<sub>4</sub>, ...,
x<sub>n-2</sub>, x<sub>n</sub>x<sub>n-1</sub><sup>-1</sup>, x<sub>n-1</sub><sup>-1</sup> </var>] (<var>nge4</var>)
</dl>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>FGA manual<br>May 2005
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1041
