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 [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 )\]
‣ MalcevCollectorConstruction( G, inds, C, CC, N, NN ) | ( function ) |
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:
(a) \((n_{r+s+1}, \dots, n_{r+s+t})\) is a Mal'cev basis for the \(T\)-group \(N \leq G\),
(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}\),
(c) \((g_1 CN, \dots, g_r CN)\) is a polycyclic sequence for the finite group \(G/CN\).
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 ) | ( function ) |
‣ GUARANA.Tr_n_O2( n ) | ( function ) |
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 ) | ( function ) |
‣ GUARANA.F_3c_Aut1( c ) | ( function ) |
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 ) | ( function ) |
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 ) | ( function ) |
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 ) | ( function ) |
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 ) | ( function ) |
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 ).
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, -7, 0, -37, -16, -352, -212 ] gap> Random( malCol, 10 ); [ 0, 0, 1, 9, 5, 5, 2, -2, 7, -10, 7, -6 ]
generated by GAPDoc2HTML