<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>