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