<html><head><title>[Example] 3 Mal'cev collection</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>3 Mal'cev collection</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP003.htm#SECT001">The main functions</a> <li> <A HREF="CHAP003.htm#SECT002">An example application</a> </ol><p> <p> Let <var>G</var> be an infinite polycyclic group. It is well-known that there exist a normal <var>T</var>-group <var>N</var> and a <var>T</var>-group <var>C</var> such that <var>H=CN</var> is normal of finite index in <var>G</var> and <var>H/N</var> is free abelian of finite rank <a href="biblio.htm#Seg83"><cite>Seg83</cite></a>. <p> In this chapter we present an effective collection method for an infinite polycyclic group which is given by a polycyclic presentation with respect to a polycyclic sequence <var>P</var> going through the normal series <var>1 leN leH leG</var>. <p> This polycyclic sequence <var>P</var> must be chosen as follows. Let <var>(n<sub>1</sub>,...,n<sub>l</sub>)</var> be a Mal'cev basis of <var>N</var> and let <var>(c<sub>1</sub>N,...,c<sub>k</sub> N)</var> be a basis for the free abelian group <var>CN/N</var>. Then <var>(c<sub>1</sub>,...,c<sub>k</sub>,n<sub>1</sub>,...,n<sub>l</sub>)</var> is a polycyclic sequence for <var>H=CN</var>. Further there exists <var>f<sub>1</sub>,..., f<sub>j</sub> inG</var> such that <var>(f<sub>1</sub> H, ..., f<sub>j</sub> H)</var> is a polycyclic sequence for <var>G/H</var>. Now we set <p><var>P = (f<sub>1</sub>,...,f<sub>j</sub>, c<sub>1</sub>, ..., c<sub>k</sub>, n<sub>1</sub>, ..., n<sub>l</sub> )<p></var> <p> <p> <h2><a name="SECT001">3.1 The main functions</a></h2> <p><p> <li><code>MalcevCollectorConstruction([ </code><var>G</var><code>, </code><var>inds</var><code>, </code><var>C</var><code>, </code><var>CC</var><code>, </code><var>N</var><code>, </code><var>NN</var><code>] )</code> <p> returns a Mal'cev collector for the infinite polycyclically presented group <var>G</var>. The group <var>G</var> must be given with respect to a polycyclic sequence <var>(g<sub>1</sub>,...,g<sub>r</sub>, c<sub>r+1</sub>, ..., c<sub>r+s</sub>, n<sub>r+s+1</sub>, ..., n<sub>r+s+t</sub>)</var> with the following properties: <dl compact> <dt>(a)<dd> <var>(n<sub>r+s+1</sub>, ..., n<sub>r+s+t</sub>)</var> is a Mal'cev basis for the <var>T</var>-group <var>N leqG</var>, <dt>(b)<dd><var>(c<sub>r+1</sub>N, ..., c<sub>r+s</sub>N)</var> is a basis for the free-abelian group <var>CN/N</var> where <var>C leqG</var> is a <var>T</var>-group generated by <var> c<sub>r+1</sub>, ..., c<sub>r+s</sub> </var>, <dt>(c)<dd> <var>(g<sub>1</sub> CN, ..., g<sub>r</sub> CN)</var> is a polycyclic sequence for the finite group <var>G/CN</var>. </dl> The list <var>inds</var> is equal to <var>[ [1,...,r],[r+1,...,r+s],[r+s+1,...,r+s+t]]</var>. The group <var>CC</var> is isomorphic to <var>C</var> via CC!.bijection and given by a polycyclic presentation with respect to a Mal'cev basis starting with <var> c<sub>r+1</sub>, ..., c<sub>r+s</sub></var>. The group <var>NN</var> is isomorphic to <var>N</var> via NN!.bijection. and given by a polycyclic presentation with respect to the Mal'cev basis <var>( n<sub>r+s+1</sub>, ..., n<sub>r+s+t</sub>)</var>. <p> <li><code>GUARANA.Tr_n_O1( </code><var>n</var><code> )</code> <li><code>GUARANA.Tr_n_O2( </code><var>n</var><code> )</code> <p> for a positive integer <var>n</var> these functions construct polycyclically presented groups that can be used to test the Mal'cev collector. They return a list which can be used as input for the function MalcevCollectorConstruction. The constructed groups are isomorphic to triangular matrix groups of dimension <var>n</var> over the ring <var>O<sub>1</sub></var>, respectively <var>O<sub>2</sub></var>. The ring <var>O<sub>1</sub></var>, respectively <var>O<sub>2</sub></var>, is the maximal order of <var><font face="helvetica,arial">Q</font>(theta<sub>i</sub>)</var> where <var>theta<sub>1</sub></var>, respectively <var>theta<sub>2</sub></var>, is a zero of the polynomial <var>p<sub>1</sub>(x) = x<sup>2</sup>-3</var>, respectively <var>p<sub>2</sub>(x)=x<sup>3</sup> -x<sup>2</sup> +4</var>. <p> <li><code>GUARANA.F_2c_Aut1( </code><var>c</var><code> )</code> <li><code>GUARANA.F_3c_Aut2( </code><var>c</var><code> )</code> <p> for a positive integer <var>c</var> these functions construct polycyclically presented groups that can be used to test the Mal'cev collector. They return a list which can be used as input for the function MalcevCollectorConstruction. These groups are constructed as follows: Let <var>F<sub>n,c</sub></var> be the free nilpotent of class <var>c</var> group on <var>n</var> generators. An automorphism <var>varphi</var> of the free group <var>F<sub>n</sub></var> naturally induces an automorphism <var>barvarphi</var> of <var>F<sub>n,c</sub></var>. We use the automorphism <var>varphi<sub>1</sub></var> of <var>F<sub>2</sub></var> which maps <var>f<sub>1</sub></var> to <var>f<sub>2</sub><sup>-1</sup></var> and <var>f<sub>2</sub></var> to <var>f<sub>1</sub> f<sub>2</sub><sup>3</sup></var> and the automorphism <var>varphi<sub>2</sub></var> of <var>F<sub>3</sub></var> mapping <var>f<sub>1</sub></var> to <var>f<sub>2</sub><sup>-1</sup></var>, <var>f<sub>2</sub></var> to <var>f<sub>3</sub><sup>-1</sup></var> and <var>f<sub>3</sub></var> to <var>f<sub>2</sub><sup>-3</sup>f<sub>1</sub><sup>-1</sup></var> for our construction. The returned group F_2c_Aut1, respectively F_3c_Aut2, is isomorphic to the semidirect product <var>langlevarphi<sub>1</sub> rangleltimesF<sub>2,c</sub></var>, respectively <var>langlevarphi<sub>2</sub> rangleltimesF<sub>3,c</sub></var>. <p> <li><code>MalcevGElementByExponents( </code><var>malCol</var><code>, </code><var>exps</var><code> )</code> <p> For a Mal'cev collector <var>malCol</var> of a group <var>G</var> and an exponent vector <var>exps</var> with integer entries, this functions returns the group element of <var>G</var>, which has exponents <var>exps</var> with respect to the polycyclic sequence underlying <var>malCol</var>. <p> <li><code>Random( </code><var>malCol</var><code>, </code><var>range</var><code> )</code> <p> For a Mal'cev collector <var>malCol</var> this function returns the output of MalcevGElementByExponents( <var>malCol</var>, <var>exps</var> ), where <var>exps</var> is an exponent vector whose entries are randomly chosen integers between -<var>range</var> and <var>range</var>. <p> <li><code></code><var>g</var><code> * </code><var>h</var><code></code> <p> returns the product of group elements which are defined with respect to a Mal'cev collector by the the function MalcevGElementByExponents. <p> <li><code>GUARANA.AverageRuntimeCollec( </code><var>malCol</var><code>, </code><var>ranges</var><code>, </code><var>no</var><code> )</code> <p> for a Mal'cev collector <var>malCol</var>, a list of positive integers <var>ranges</var> and a positive integer <var>no</var> this function computes for each number <var>r</var> in <var>ranges</var> the average runtime of <var>no</var> multiplications of two random elements of <var>malCol</var> of range <var>r</var>, as generated by Random( <var>malCol</var>, <var>r</var> ). <p> <p> <h2><a name="SECT002">3.2 An example application</a></h2> <p><p> <pre> gap> ll := GUARANA.Tr_n_O1( 3 ); [ Pcp-group with orders [ 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ [ 1 .. 3 ], [ 4 .. 6 ], [ 7 .. 12 ] ], Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ], Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ], Pcp-group with orders [ 0, 0, 0 ], Pcp-group with orders [ 0, 0, 0 ] ] gap> malCol := MalcevCollectorConstruction( ll ); <<Malcev collector>> F : [ 2, 2, 2 ] C : <<Malcev object of dimension 3>> N : <<Malcev object of dimension 6>> gap> exps_g := [ 1, 1, 1, -3, -2, 1, -2, -1, 0, 3, -1,3 ]; [ 1, 1, 1, -3, -2, 1, -2, -1, 0, 3, -1, 3 ] gap> exps_h := [ 1, 0, 1, -1, 0, 2, 0, 4, -1, 5, 9,-5 ]; [ 1, 0, 1, -1, 0, 2, 0, 4, -1, 5, 9, -5 ] gap> g := MalcevGElementByExponents( malCol, exps_g ); [ 1, 1, 1, -3, -2, 1, -2, -1, 0, 3, -1, 3 ] gap> h := MalcevGElementByExponents( malCol, exps_h ); [ 1, 0, 1, -1, 0, 2, 0, 4, -1, 5, 9, -5 ] gap> k := g*h; [ 0, 1, 0, -4, -2, 3, 1, 4, 35, -16, -404, 232 ] gap> Random( malCol, 10 ); [ 0, 0, 1, 9, 5, 5, 2, -2, 7, -10, 7, -6 ] </pre> <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>Example manual<br>June 2007 </address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1363
