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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%