[Up] [Previous] [Next] [Index]

3 Mal'cev collection

Sections

  1. The main functions
  2. An example application

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 leN leH leG.

This polycyclic sequence P must be chosen as follows. Let (n1,...,nl) be a Mal'cev basis of N and let (c1N,...,ck N) be a basis for the free abelian group CN/N. Then (c1,...,ck,n1,...,nl) is a polycyclic sequence for H=CN. Further there exists f1,..., fj inG such that (f1 H, ..., fj H) is a polycyclic sequence for G/H. Now we set

P = (f1,...,fj, c1, ..., ck, n1, ..., nl )

3.1 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 (g1,...,gr, cr+1, ..., cr+s, nr+s+1, ..., nr+s+t) with the following properties:

    (a)
    (nr+s+1, ..., nr+s+t) is a Mal'cev basis for the T-group N leqG,
    (b)
    (cr+1N, ..., cr+sN) is a basis for the free-abelian group CN/N where C leqG is a T-group generated by cr+1, ..., cr+s ,
    (c)
    (g1 CN, ..., gr CN) is a polycyclic sequence for the finite group G/CN.
    The list inds is equal to [ [1,...,r],[r+1,...,r+s],[r+s+1,...,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 cr+1, ..., cr+s. The group NN is isomorphic to N via NN!.bijection. and given by a polycyclic presentation with respect to the Mal'cev basis ( nr+s+1, ..., nr+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 O1, respectively O2. The ring O1, respectively O2, is the maximal order of Q(thetai) where theta1, respectively theta2, is a zero of the polynomial p1(x) = x2-3, respectively p2(x)=x3 -x2 +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 Fn,c be the free nilpotent of class c group on n generators. An automorphism varphi of the free group Fn naturally induces an automorphism barvarphi of Fn,c. We use the automorphism varphi1 of F2 which maps f1 to f2-1 and f2 to f1 f23 and the automorphism varphi2 of F3 mapping f1 to f2-1, f2 to f3-1 and f3 to f2-3f1-1 for our construction. The returned group F_2c_Aut1, respectively F_3c_Aut2, is isomorphic to the semidirect product langlevarphi1 rangleltimesF2,c, respectively langlevarphi2 rangleltimesF3,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

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

    3.2 An example application

    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 ]
    

    [Up] [Previous] [Next] [Index]

    Example manual
    June 2007