%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %W collection.tex GAP documentation Bjoern Assmann %W %% %H $Id: collection.tex,v 1.5 2007/05/24 16:48:37 bjoern Exp $ %% %Y Copyright (C) 1997, School of Math & Comp. Sci., St Andrews, Scotland %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Mal'cev collection} Let $G$ be an infinite polycyclic group. It is well-known that there exist a normal ${T}$-group $N$ and a ${T}$-group $C$ such that $H=CN$ is normal of finite index in $G$ and $H/N$ is free abelian of finite rank \cite{Seg83}. 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 $P$ going through the normal series $1 \le N \le H \le G$. This polycyclic sequence $P$ must be chosen as follows. Let $(n_1,\dots,n_l)$ be a Mal'cev basis of $N$ and let $(c_1N,\dots,c_k N)$ be a basis for the free abelian group $CN/N$. Then $(c_1,\dots,c_k,n_1,\dots,n_l)$ is a polycyclic sequence for $H=CN$. Further there exists $f_1,\dots, f_j \in G$ such that $(f_1 H, \dots, f_j H)$ is a polycyclic sequence for $G/H$. Now we set $$P = (f_1,\dots,f_j, c_1, \dots , c_k, n_1, \dots, n_l )$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The main functions} \> MalcevCollectorConstruction([ <G>, <inds>, <C>, <CC>, <N>, <NN>] ) returns a Mal'cev collector for the infinite polycyclically presented group $G$. The group $G$ must be given with respect to a polycyclic sequence $(g_1,\dots,g_r, c_{r+1}, \dots, c_{r+s}, n_{r+s+1}, \dots, n_{r+s+t})$ with the following properties: \beginlist \item{(a)} $(n_{r+s+1}, \dots, n_{r+s+t})$ is a Mal'cev basis for the $T$-group $N \leq G$, \item{(b)} $(c_{r+1}N, \dots, c_{r+s}N)$ is a basis for the free-abelian group $CN/N$ where $C \leq G$ is a $T$-group generated by $ c_{r+1}, \dots, c_{r+s} $, \item{(c)} $(g_1 CN, \dots, g_r CN)$ is a polycyclic sequence for the finite group $G/CN$. \endlist The list <inds> is equal to $[ [1,\dots,r],[r+1,\dots,r+s],[r+s+1,\dots,r+s+t]]$. The group $CC$ is isomorphic to $C$ via CC!.bijection and given by a polycyclic presentation with respect to a Mal'cev basis starting with $ c_{r+1}, \dots, c_{r+s}$. The group $NN$ is isomorphic to $N$ via NN!.bijection. and given by a polycyclic presentation with respect to the Mal'cev basis $( n_{r+s+1}, \dots, n_{r+s+t})$. \> GUARANA.Tr_n_O1( <n> ) \> GUARANA.Tr_n_O2( <n> ) for a positive integer <n> 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 <n> over the ring $O_1$, respectively $O_2$. The ring $O_1$, respectively $O_2$, is the maximal order of $\Q(\theta_i)$ where $\theta_1$, respectively $\theta_2$, is a zero of the polynomial $p_1(x) = x^2-3$, respectively $p_2(x)=x^3 -x^2 +4$. \> GUARANA.F_2c_Aut1( <c> ) \> GUARANA.F_3c_Aut2( <c> ) for a positive integer <c> 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 $F_{n,c}$ be the free nilpotent of class $c$ group on $n$ generators. An automorphism $\varphi$ of the free group $F_n$ naturally induces an automorphism $\bar{\varphi}$ of $F_{n,c}$. We use the automorphism $\varphi_1$ of $F_2$ which maps $f_1$ to $f_2^{-1}$ and $f_2$ to $f_1 f_2^3$ and the automorphism $\varphi_2$ of $F_3$ mapping $f_1$ to $f_2^{-1}$, $f_2$ to $f_3^{-1}$ and $f_3$ to $f_2^{-3}f_1^{-1}$ for our construction. The returned group F_2c_Aut1, respectively F_3c_Aut2, is isomorphic to the semidirect product $\langle \varphi_1 \rangle \ltimes F_{2,c}$, respectively $\langle \varphi_2 \rangle \ltimes F_{3,c}$. \> MalcevGElementByExponents( <malCol>, <exps> ) For a Mal'cev collector <malCol> of a group $G$ and an exponent vector <exps> with integer entries, this functions returns the group element of $G$, which has exponents <exps> with respect to the polycyclic sequence underlying <malCol>. \> Random( <malCol>, <range> ) For a Mal'cev collector <malCol> this function returns the output of MalcevGElementByExponents( <malCol>, <exps> ), where <exps> is an exponent vector whose entries are randomly chosen integers between -<range> and <range>. \> `<g> * <h>'{multiplication} returns the product of group elements which are defined with respect to a Mal'cev collector by the the function MalcevGElementByExponents. \> GUARANA.AverageRuntimeCollec( <malCol>, <ranges>, <no> ) for a Mal'cev collector <malCol>, a list of positive integers <ranges> and a positive integer <no> this function computes for each number <r> in <ranges> the average runtime of <no> multiplications of two random elements of <malCol> of range <r>, as generated by Random( <malCol>, <r> ). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{An example application} \beginexample 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 ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %%