%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  intro.tex             POLENTA documentation            Bjoern Assmann
%W                                                     
%W                                                     
%W                                                       
%%
%H  @(#)$Id: intro.tex,v 1.3 2007/05/24 16:33:55 bjoern Exp $
%%
%Y 2003
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Introduction}

\atindex{Guarana}{@Guarana}

In this package we demonstrate the algorithmic usefulness of the
so-called Mal'cev correspondence for computations with infinite polycyclic
groups; it is a correspondence
that associates to every $\Q$-powered nilpotent group $H$ a
unique rational nilpotent Lie algebra $L_H$ and vice-versa.
The Mal'cev correspondence was discovered 
by Anatoly Mal'cev in 1951 \cite{Mal51}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Setup for computing the correspondence}

Let $G$ be a finitely generated torsion-free nilpotent group, 
i.e.\ a $T$-group.
Then $G$ can be embedded in a $\Q$-powered hull $\hat{G}$.
The group $\hat{G}$ is
a $\Q$-powered nilpotent group and  
is unique up to isomorphism. 
We denote the Lie algebra
which corresponds to $\hat{G}$ under the Mal'cev correspondence by
$L(G)= L_{\hat{G}}$.

We provide an algorithm for setting up the 
Mal'cev correspondence
between $\hat{G}$ and the Lie algebra $L(G)$. 
That is, if $G$
is given by a polycyclic presentation with respect to a Mal'cev basis,
then we can compute a structure constants table of $L(G)$.
Furthermore for a given $g\in G$ we can compute the corresponding 
element in $L(G)$ and vice versa. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Collection}

Every element of a
polycyclically presented
group has a unique normal form. An algorithm for computing this normal
form is called a collection algorithm. Such an algorithm
lies at the heart of most methods
dealing with polycyclically presented groups. The current state of
the art is collection from the left 
\cite{Geb02,LGS90,VLe90}.

This package contains
a new collection algorithm for polycyclically presented groups,
which we call Mal'cev collection \cite{ALi07}.
Mal'cev collection is
in some cases dramatically faster than
collection from the left, while using less memory.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E