%% for a long time these were red and blue by default, %% now black, but keep variables to overwrite \definecolor{FuncColor}{rgb}{0.0,0.0,0.0} %% strange name because of pdflatex bug: \definecolor{Chapter }{rgb}{0.0,0.0,0.0} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
% write page numbers to a .pnr log file for online help \newwrite\pagenrlog \immediate\openout\pagenrlog =\jobname.pnr \immediate\write\pagenrlog{PAGENRS := [} \newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} %% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
%% nicer description environments, allows long labels \usepackage{enumitem} \setdescription{style=nextline}
\newpage\setcounter{page}{2}
{\small \section*{Copyright} \logpage{[ 0, 0, 1 ]} \index{License} {\copyright} 2003\texttt{\symbol{45}}2018 by Bettina Eick, Max Horn and Werner
Nickel
The \textsf{Polycyclic} package is free software; you can redistribute it and/or modify it under the
terms of the \href{http://www.fsf.org/licenses/gpl.html} {GNU General Public License} as published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version. \mbox{}}\\[1cm]
{\small \section*{Acknowledgements} \logpage{[ 0, 0, 2 ]}
We appreciate very much all past and future comments, suggestions and
contributions to this package and its documentation provided by \textsf{GAP} users and developers. \mbox{}}\\[1cm] \newpage
\def\contentsname{Contents\logpage{[ 0, 0, 3 ]}}
\tableofcontents \newpage
\chapter{\textcolor{Chapter }{Preface}}\label{Preface} \logpage{[ 1, 0, 0 ]} \hyperdef{L}{X874E1D45845007FE}{}
{
A group $G$ is called \emph{polycyclic} if there exists a subnormal series in $G$ with cyclic factors. Every polycyclic group is soluble and every supersoluble
group is polycyclic. The class of polycyclic groups is closed with respect to
forming subgroups, factor groups and extensions. Polycyclic groups can also be
characterised as those soluble groups in which each subgroup is finitely
generated.
K. A. Hirsch has initiated the investigation of polycyclic groups in 1938, see \cite{Hir38a}, \cite{Hir38b}, \cite{Hir46}, \cite{Hir52}, \cite{Hir54}, and their central position in infinite group theory has been recognised
since.
A well\texttt{\symbol{45}}known result of Hirsch asserts that each polycyclic
group is finitely presented. In fact, a polycyclic group has a presentation
which exhibits its polycyclic structure: a \emph{pc\texttt{\symbol{45}}presentation} as defined in the Chapter \hyperref[Introduction to polycyclic presentations]{`Introduction to polycyclic presentations'}. Pc\texttt{\symbol{45}}presentations allow efficient computations with the
groups they define. In particular, the word problem is efficiently solvable in
a group given by a pc\texttt{\symbol{45}}presentation. Further, subgroups and
factor groups of groups given by a pc\texttt{\symbol{45}}presentation can be
handled effectively.
The \textsf{GAP} 4 package \textsf{Polycyclic} is designed for computations with polycyclic groups which are given by a
pc\texttt{\symbol{45}}presentation. The package contains methods to solve the
word problem in such groups and to handle subgroups and factor groups of
polycyclic groups. Based on these basic algorithms we present a collection of
methods to construct polycyclic groups and to investigate their structure.
In \cite{BCRS91} and \cite{Seg90} the theory of problems which are decidable in
polycyclic\texttt{\symbol{45}}by\texttt{\symbol{45}}finite groups has been
started. As a result of these investigation we know that a large number of
group theoretic problems are decidable by algorithms in polycyclic groups.
However, practical algorithms which are suitable for computer implementations
have not been obtained by this study. We have developed a new set of practical
methods for groups given by pc\texttt{\symbol{45}}presentations, see for
example \cite{Eic00}, and this package is a collection of implementations for these and other
methods.
We refer to \cite{Rob82}, page 147ff, and \cite{Seg83} for background on polycyclic groups. Further, in \cite{Sims94} a variation of the basic methods for groups with
pc\texttt{\symbol{45}}presentation is introduced. Finally, we note that the
main GAP library contains many practical algorithms to compute with finite
polycyclic groups. This is described in the Section on polycyclic groups in
the reference manual. }
\chapter{\textcolor{Chapter }{Introduction to polycyclic presentations}}\label{Introduction to polycyclic presentations} \logpage{[ 2, 0, 0 ]} \hyperdef{L}{X792561B378D95B23}{}
{
Let $G$ be a polycyclic group and let $G = C_1 \rhd C_2 \ldots C_n\rhd C_{n+1} = 1$ be a \emph{polycyclic series}, that is, a subnormal series of $G$ with non\texttt{\symbol{45}}trivial cyclic factors. For $1 \leq i \leq n$ we choose $g_i \in C_i$ such that $C_i = \langle g_i, C_{i+1} \rangle$. Then the sequence $(g_1, \ldots, g_n)$ is called a \emph{polycyclic generating sequence of $G$}. Let $I$ be the set of those $i \in\{1, \ldots, n\}$ with $r_i := [C_i : C_{i+1}]$ finite. Each element of $G$ can be written \mbox{\texttt{\mdseries\slshape uniquely}} as $g_1^{e_1}\cdots g_n^{e_n}$ with $e_i\in {\ensuremath{\mathbb Z}}$ for $1\leq i\leq n$ and $0\leq e_i < r_i$ for $i\in I$.
Each polycyclic generating sequence of $G$ gives rise to a \emph{power\texttt{\symbol{45}}conjugate (pc\texttt{\symbol{45}}) presentation} for $G$ with the conjugate relations \[g_j^{g_i} = g_{i+1}^{e(i,j,i+1)} \cdots g_n^{e(i,j,n)} \hbox{ for } 1 \leq i <
j \leq n,\]
\[g_j^{g_i^{-1}} = g_{i+1}^{f(i,j,i+1)} \cdots g_n^{f(i,j,n)} \hbox{ for } 1 \leq i < j \leq n,\]
and the power relations \[g_i^{r_i} = g_{i+1}^{l(i,i+1)} \cdots g_n^{l(i,n)} \hbox{ for } i \in I.\]
Vice versa, we say that a group $G$ is defined by a pc\texttt{\symbol{45}}presentation if $G$ is given by a presentation of the form above on generators $g_1,\ldots,g_n$. These generators are the \emph{defining generators} of $G$. Here, $I$ is the set of $1\leq i\leq n$ such that $g_i$ has a power relation. The positive integer $r_i$ for $i\in I$ is called the \emph{relative order} of $g_i$. If $G$ is given by a pc\texttt{\symbol{45}}presentation, then $G$ is polycyclic. The subgroups $C_i = \langle g_i, \ldots, g_n \rangle$ form a subnormal series $G = C_1 \geq\ldots\geq C_{n+1} = 1$ with cyclic factors and we have that $g_i^{r_i}\in C_{i+1}$. However, some of the factors of this series may be smaller than $r_i$ for $i\in I$ or finite if $i\not\in I$.
If $G$ is defined by a pc\texttt{\symbol{45}}presentation, then each element of $G$ can be described by a word of the form $g_1^{e_1}\cdots g_n^{e_n}$ in the defining generators with $e_i\in {\ensuremath{\mathbb Z}}$ for $1\leq i\leq n$ and $0\leq e_i < r_i$ for $i\in I$. Such a word is said to be in \emph{collected form}. In general, an element of the group can be represented by more than one
collected word. If the pc\texttt{\symbol{45}}presentation has the property
that each element of $G$ has precisely one word in collected form, then the presentation is called \emph{confluent} or \emph{consistent}. If that is the case, the generators with a power relation correspond
precisely to the finite factors in the polycyclic series and $r_i$ is the order of $C_i/C_{i+1}$.
The \textsf{GAP} package \textsf{Polycyclic} is designed for computations with polycyclic groups which are given by
consistent pc\texttt{\symbol{45}}presentations. In particular, all the
functions described below assume that we compute with a group defined by a
consistent pc\texttt{\symbol{45}}presentation. See Chapter \hyperref[Collectors]{`Collectors'} for a routine that checks the consistency of a
pc\texttt{\symbol{45}}presentation.
A pc\texttt{\symbol{45}}presentation can be interpreted as a \emph{rewriting system} in the following way. One needs to add a new generator $G_i$ for each generator $g_i$ together with the relations $g_iG_i = 1$ and $G_ig_i = 1$. Any occurrence in a relation of an inverse generator $g_i^{-1}$ is replaced by $G_i$. In this way one obtains a monoid presentation for the group $G$. With respect to a particular ordering on the set of monoid words in the
generators $g_1,\ldots g_n,G_1,\ldots G_n$, the \emph{wreath product ordering}, this monoid presentation is a rewriting system. If the
pc\texttt{\symbol{45}}presentation is consistent, the rewriting system is
confluent.
In this package we do not address this aspect of
pc\texttt{\symbol{45}}presentations because it is of little relevance for the
algorithms implemented here. For the definition of rewriting systems and
confluence in this context as well as further details on the connections
between pc\texttt{\symbol{45}}presentations and rewriting systems we recommend
the book\cite{Sims94}. }
\chapter{\textcolor{Chapter }{Collectors}}\label{Collectors} \logpage{[ 3, 0, 0 ]} \hyperdef{L}{X792305CC81E8606A}{}
{
Let $G$ be a group defined by a pc\texttt{\symbol{45}}presentation as described in the
Chapter \hyperref[Introduction to polycyclic presentations]{`Introduction to polycyclic presentations'}.
The process for computing the collected form for an arbitrary word in the
generators of $G$ is called \emph{collection}. The basic idea in collection is the following. Given a word in the defining
generators, one scans the word for occurrences of adjacent generators (or
their inverses) in the wrong order or occurrences of subwords $g_i^{e_i}$ with $i\in I$ and $e_i$ not in the range $0\ldots r_{i}-1$. In the first case, the appropriate conjugacy relation is used to move the
generator with the smaller index to the left. In the second case, one uses the
appropriate power relation to move the exponent of $g_i$ into the required range. These steps are repeated until a collected word is
obtained.
There exist a number of different strategies for collecting a given word to
collected form. The strategies implemented in this package are \emph{collection from the left} as described by \cite{LGS90} and \cite{Sims94} and \emph{combinatorial collection from the left} by \cite{MVL90}. In addition, the package provides access to Hall polynomials computed by
Deep Thought for the multiplication in a nilpotent group, see \cite{WWM97} and \cite{LGS98}.
The first step in defining a pc\texttt{\symbol{45}}presented group is setting
up a data structure that knows the pc\texttt{\symbol{45}}presentation and has
routines that perform the collection algorithm with words in the generators of
the presentation. Such a data structure is called \emph{a collector}.
To describe the right hand sides of the relations in a
pc\texttt{\symbol{45}}presentation we use \emph{generator exponent lists}; the word $g_{i_1}^{e_1}g_{i_2}^{e_2}\ldots g_{i_k}^{e_k}$ is represented by the generator exponent list $[i_1,e_1,i_2,e_2,\ldots,i_k,e_k]$.
\section{\textcolor{Chapter }{Constructing a Collector}}\label{Constructing a Collector} \logpage{[ 3, 1, 0 ]} \hyperdef{L}{X800FD91386C08CD8}{}
{
A collector for a group given by a pc\texttt{\symbol{45}}presentation starts
by setting up an empty data structure for the collector. Then the relative
orders, the power relations and the conjugate relations are added into the
data structure. The construction is finalised by calling a routine that
completes the data structure for the collector. The following functions
provide the necessary tools for setting up a collector.
returns an empty data structure for a collector with \mbox{\texttt{\mdseries\slshape n}} generators. No generator has a relative order, no right hand sides of power
and conjugate relations are defined. Two generators for which no right hand
side of a conjugate relation is defined commute. Therefore, the collector
returned by this function can be used to define a free abelian group of rank \mbox{\texttt{\mdseries\slshape n}}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@ftl := FromTheLeftCollector( 4 );|
<<from the left collector with 4 generators>>
!gapprompt@gap>| !gapinput@PcpGroupByCollector( ftl );|
Pcp-group with orders [ 0, 0, 0, 0 ]
!gapprompt@gap>| !gapinput@IsAbelian(last);|
true \end{Verbatim}
If the relative order of a generators has been defined (see \texttt{SetRelativeOrder} (\ref{SetRelativeOrder})), but the right hand side of the corresponding power relation has not, then
the order and the relative order of the generator are the same. }
set the relative order in collector \mbox{\texttt{\mdseries\slshape coll}} for generator \mbox{\texttt{\mdseries\slshape i}} to \mbox{\texttt{\mdseries\slshape ro}}. The parameter \mbox{\texttt{\mdseries\slshape coll}} is a collector as returned by the function \texttt{FromTheLeftCollector} (\ref{FromTheLeftCollector}), \mbox{\texttt{\mdseries\slshape i}} is a generator number and \mbox{\texttt{\mdseries\slshape ro}} is a non\texttt{\symbol{45}}negative integer. The generator number\mbox{\texttt{\mdseries\slshape i}} is an integer in the range $1,\ldots,n$ where $n$ is the number of generators of the collector.
If \mbox{\texttt{\mdseries\slshape ro}} is $0,$ then the generator with number\mbox{\texttt{\mdseries\slshape i}} has infinite order and no power relation can be specified. As a side effect in
this case, a previously defined power relation is deleted.
If \mbox{\texttt{\mdseries\slshape ro}} is the relative order of a generator with number\mbox{\texttt{\mdseries\slshape i}} and no power relation is set for that generator, then \mbox{\texttt{\mdseries\slshape ro}} is the order of that generator.
The NC version of the function bypasses checks on the range of \mbox{\texttt{\mdseries\slshape i}}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@ftl := FromTheLeftCollector( 4 );|
<<from the left collector with 4 generators>>
!gapprompt@gap>| !gapinput@for i in [1..4] do SetRelativeOrder( ftl, i, 3 ); od;|
!gapprompt@gap>| !gapinput@G := PcpGroupByCollector( ftl );|
Pcp-group with orders [ 3, 3, 3, 3 ]
!gapprompt@gap>| !gapinput@IsElementaryAbelian( G );|
true \end{Verbatim}
}
set the right hand side of the power relation for generator \mbox{\texttt{\mdseries\slshapei}} in collector \mbox{\texttt{\mdseries\slshape coll}} to (a copy of) \mbox{\texttt{\mdseries\slshape rhs}}. An attempt to set the right hand side for a generator without a relative
order results in an error.
Right hand sides are by default assumed to be trivial.
The parameter \mbox{\texttt{\mdseries\slshape coll}} is a collector, \mbox{\texttt{\mdseries\slshape i}} is a generator number and \mbox{\texttt{\mdseries\slshape rhs}} is a generators exponent list or an element from a free group.
The no\texttt{\symbol{45}}check (NC) version of the function bypasses checks
on the range of \mbox{\texttt{\mdseries\slshape i}} and stores \mbox{\texttt{\mdseries\slshape rhs}} (instead of a copy) in the collector. }
set the right hand side of the conjugate relation for the generators \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}} with \mbox{\texttt{\mdseries\slshape j}} larger than \mbox{\texttt{\mdseries\slshape i}}. The parameter \mbox{\texttt{\mdseries\slshape coll}} is a collector, \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}} are generator numbers and \mbox{\texttt{\mdseries\slshape rhs}} is a generator exponent list or an element from a free group. Conjugate
relations are by default assumed to be trivial.
The generator number\mbox{\texttt{\mdseries\slshape i}} can be negative in order to define conjugation by the inverse of a generator.
The no\texttt{\symbol{45}}check (NC) version of the function bypasses checks
on the range of \mbox{\texttt{\mdseries\slshape i}} and \mbox{\texttt{\mdseries\slshapej}} and stores \mbox{\texttt{\mdseries\slshape rhs}} (instead of a copy) in the collector. }
set the right hand side of the conjugate relation for the generators \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}} with \mbox{\texttt{\mdseries\slshape j}} larger than \mbox{\texttt{\mdseries\slshape i}} by specifying the commutator of \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}}. The parameter \mbox{\texttt{\mdseries\slshape coll}} is a collector, \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}} are generator numbers and \mbox{\texttt{\mdseries\slshape rhs}} is a generator exponent list or an element from a free group.
The generator number\mbox{\texttt{\mdseries\slshape i}} can be negative in order to define the right hand side of a commutator
relation with the second generator being the inverse of a generator. }
completes the data structures of a collector. This is usually the last step in
setting up a collector. Among the steps performed is the completion of the
conjugate relations. For each non\texttt{\symbol{45}}trivial conjugate
relation of a generator, the corresponding conjugate relation of the inverse
generator is calculated.
Note that \texttt{UpdatePolycyclicCollector} is automatically called by the function \texttt{PcpGroupByCollector} (see \texttt{PcpGroupByCollector} (\ref{PcpGroupByCollector})). }
tests if the collector \mbox{\texttt{\mdseries\slshape coll}} is confluent. The function returns true or false accordingly.
Compare Chapter \ref{Introduction to polycyclic presentations} for a definition of confluence.
Note that confluence is automatically checked by the function \texttt{PcpGroupByCollector} (see \texttt{PcpGroupByCollector} (\ref{PcpGroupByCollector})).
The following example defines a collector for a semidirect product of the
cyclic group of order $3$ with the free abelian group of rank $2$. The action of the cyclic group on the free abelian group is given by the
matrix \[\pmatrix{ 0 & 1 \cr -1 & -1}.\]
This leads to the following polycyclic presentation: \[\langle g_1,g_2,g_3 | g_1^3, g_2^{g_1}=g_3, g_3^{g_1}=g_2^{-1}g_3^{-1},
g_3^{g_2}=g_3\rangle.\]
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@ftl := FromTheLeftCollector( 3 );|
<<from the left collector with 3 generators>>
!gapprompt@gap>| !gapinput@SetRelativeOrder( ftl, 1, 3 );|
!gapprompt@gap>| !gapinput@SetConjugate( ftl, 2, 1, [3,1] );|
!gapprompt@gap>| !gapinput@SetConjugate( ftl, 3, 1, [2,-1,3,-1] );|
!gapprompt@gap>| !gapinput@UpdatePolycyclicCollector( ftl );|
!gapprompt@gap>| !gapinput@IsConfluent( ftl );|
true \end{Verbatim}
The action of the inverse of $g_1$ on $\langle g_2,g_2\rangle$ is given by the matrix \[\pmatrix{ -1 & -1 \cr 1 & 0}.\]
The corresponding conjugate relations are automatically computed by \texttt{UpdatePolycyclicCollector}. It is also possible to specify the conjugation by inverse generators. Note
that you need to run \texttt{UpdatePolycyclicCollector} after one of the set functions has been used. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@SetConjugate( ftl, 2, -1, [2,-1,3,-1] );|
!gapprompt@gap>| !gapinput@SetConjugate( ftl, 3, -1, [2,1] );|
!gapprompt@gap>| !gapinput@IsConfluent( ftl );|
Error, Collector is out of date called from
CollectWordOrFail( coll, ev1, [ j, 1, i, 1 ] ); called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
!gapbrkprompt@brk>| !gapinput@|
!gapprompt@gap>| !gapinput@UpdatePolycyclicCollector( ftl );|
!gapprompt@gap>| !gapinput@IsConfluent( ftl );|
true \end{Verbatim}
}
}
\section{\textcolor{Chapter }{Accessing Parts of a Collector}}\label{Accessing Parts of a Collector} \logpage{[ 3, 2, 0 ]} \hyperdef{L}{X818484817C3BAAE6}{}
{
returns a copy of the generator exponent list stored for the right hand side
of the power relation of the generator \mbox{\texttt{\mdseries\slshape i}} in the collector \mbox{\texttt{\mdseries\slshape coll}}.
The no\texttt{\symbol{45}}check (NC) version of the function bypasses checks
on the range of \mbox{\texttt{\mdseries\slshape i}} and does not create a copy before returning the right hand side of the power
relation. }
returns a copy of the right hand side of the conjugate relation stored for the
generators \mbox{\texttt{\mdseries\slshape j}} and \mbox{\texttt{\mdseries\slshape i}} in the collector \mbox{\texttt{\mdseries\slshape coll}} as generator exponent list. The generator \mbox{\texttt{\mdseries\slshape j}} must be larger than \mbox{\texttt{\mdseries\slshape i}}.
The no\texttt{\symbol{45}}check (NC) version of the function bypasses checks
on the range of \mbox{\texttt{\mdseries\slshape i}} and \mbox{\texttt{\mdseries\slshapej}} and does not create a copy before returning the right hand side of the power
relation. }
returns a generator exponent list for the exponent vector \mbox{\texttt{\mdseries\slshapeexpvec}}. This is the inverse operation to \texttt{ExponentsByObj}. See \texttt{ExponentsByObj} (\ref{ExponentsByObj}) for an example. }
returns an exponent vector for the generator exponent list \mbox{\texttt{\mdseries\slshape genexp}}. This is the inverse operation to \texttt{ObjByExponents}. The function assumes that the generators in \mbox{\texttt{\mdseries\slshape genexp}} are given in the right order and that the exponents are in the right range. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@G := UnitriangularPcpGroup( 4, 0 );|
Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ]
!gapprompt@gap>| !gapinput@coll := Collector ( G );|
<<from the left collector with 6 generators>>
!gapprompt@gap>| !gapinput@ObjByExponents( coll, [6,-5,4,3,-2,1] );|
[ 1, 6, 2, -5, 3, 4, 4, 3, 5, -2, 6, 1 ]
!gapprompt@gap>| !gapinput@ExponentsByObj( coll, last );|
[ 6, -5, 4, 3, -2, 1 ] \end{Verbatim}
}
}
\section{\textcolor{Chapter }{Special Features}}\label{Special Features} \logpage{[ 3, 3, 0 ]} \hyperdef{L}{X79AEB3477800DC16}{}
{
In this section we descibe collectors for nilpotent groups which make use of
the special structure of the given pc\texttt{\symbol{45}}presentation.
checks if there is a function $w$ from the generators of the collector \mbox{\texttt{\mdseries\slshape coll}} into the positive integers such that $w(g) \geq w(x)+w(y)$ for all generators $x$, $y$ and all generators $g$ in (the normal of) $[x,y]$. If such a function does not exist, false is returned. If such a function
exists, it is computed and stored in the collector. In addition, the default
collection strategy for this collector is set to combinatorial collection. }
is applicable to a collector which passes \texttt{IsWeightedCollector} and computes the Hall multiplication polynomials for the presentation stored
in \mbox{\texttt{\mdseries\slshape coll}}. The default strategy for this collector is set to evaluating those
polynomial when multiplying two elements. }
stores a collector \mbox{\texttt{\mdseries\slshape coll}} in the file \mbox{\texttt{\mdseries\slshape file}} such that the file can be read back using the function 'Read' into \textsf{GAP} and would then be stored in the variable \mbox{\texttt{\mdseries\slshape name}}. }
appends a collector \mbox{\texttt{\mdseries\slshape coll}} in the file \mbox{\texttt{\mdseries\slshape file}} such that the file can be read back into \textsf{GAP} and would then be stored in the variable \mbox{\texttt{\mdseries\slshape name}}. }
this property can be set to \texttt{true} for a collector to force a simple
from\texttt{\symbol{45}}the\texttt{\symbol{45}}left collection strategy
implemented in the \textsf{GAP} language to be used. Its main purpose is to help debug the collection
routines. }
this global variable can be set to \texttt{true} to force all collectors to use a simple
from\texttt{\symbol{45}}the\texttt{\symbol{45}}left collection strategy
implemented in the \textsf{GAP} language to be used. Its main purpose is to help debug the collection
routines. }
this global variable can be set to \texttt{true} to force the comparison of results from the combinatorial collector with the
result of an identical collection performed by a simple
from\texttt{\symbol{45}}the\texttt{\symbol{45}}left collector. Its main
purpose is to help debug the collection routines. }
\section{\textcolor{Chapter }{Pcp\texttt{\symbol{45}}elements \texttt{\symbol{45}}\texttt{\symbol{45}}
elements of a pc\texttt{\symbol{45}}presented group}}\label{Pcp-elements -- elements of a pc-presented group} \logpage{[ 4, 1, 0 ]} \hyperdef{L}{X7882F0F57ABEB680}{}
{
A \emph{pcp\texttt{\symbol{45}}element} is an element of a group defined by a consistent
pc\texttt{\symbol{45}}presentation given by a collector. Suppose that $g_1, \ldots, g_n$ are the defining generators of the collector. Recall that each element $g$ in this group can be written uniquely as a collected word $g_1^{e_1} \cdots g_n^{e_n}$ with $e_i \in {\ensuremath{\mathbb Z}}$ and $0 \leq e_i < r_i$ for $i \in I$. The integer vector $[e_1, \ldots, e_n]$ is called the \emph{exponent vector} of $g$. The following functions can be used to define
pcp\texttt{\symbol{45}}elements via their exponent vector or via an arbitrary
generator exponent word as introduced in Chapter \ref{Collectors}.
returns the pcp\texttt{\symbol{45}}element with exponent vector \mbox{\texttt{\mdseries\slshape exp}}. The exponent vector is considered relative to the defining generators of the
pc\texttt{\symbol{45}}presentation. }
returns the pcp\texttt{\symbol{45}}element with generators exponent list \mbox{\texttt{\mdseries\slshape word}}. This list \mbox{\texttt{\mdseries\slshape word}} consists of a sequence of generator numbers and their corresponding exponents
and is of the form $[i_1, e_{i_1}, i_2, e_{i_2}, \ldots, i_r, e_{i_r}]$. The generators exponent list is considered relative to the defining
generators of the pc\texttt{\symbol{45}}presentation.
These functions return pcp\texttt{\symbol{45}}elements in the category \texttt{IsPcpElement}. Presently, the only representation implemented for this category is \texttt{IsPcpElementRep}. (This allows us to be a little sloppy right now. The basic set of operations
for \texttt{IsPcpElement} has not been defined yet. This is going to happen in one of the next version,
certainly as soon as the need for different representations arises.) }
returns true if the object \mbox{\texttt{\mdseries\slshape obj}} is a group and also a pcp\texttt{\symbol{45}}element collection. }
}
\section{\textcolor{Chapter }{Methods for pcp\texttt{\symbol{45}}elements}}\label{Methods for pcp-elements} \logpage{[ 4, 2, 0 ]} \hyperdef{L}{X790471D07A953E12}{}
{
Now we can describe attributes and functions for
pcp\texttt{\symbol{45}}elements. The four basic attributes of a
pcp\texttt{\symbol{45}}element, \texttt{Collector}, \texttt{Exponents}, \texttt{GenExpList} and \texttt{NameTag} are computed at the creation of the pcp\texttt{\symbol{45}}element. All other
attributes are determined at runtime.
Let \mbox{\texttt{\mdseries\slshape g}} be a pcp\texttt{\symbol{45}}element and $g_1, \ldots, g_n$ a polycyclic generating sequence of the underlying
pc\texttt{\symbol{45}}presented group. Let $C_1, \ldots, C_n$ be the polycyclic series defined by $g_1, \ldots, g_n$.
The \emph{depth} of a non\texttt{\symbol{45}}trivial element $g$ of a pcp\texttt{\symbol{45}}group (with respect to the defining generators) is
the integer $i$ such that $g \in C_i \setminus C_{i+1}$. The depth of the trivial element is defined to be $n+1$. If $g\not=1$ has depth $i$ and $g_i^{e_i} \cdots g_n^{e_n}$ is the collected word for $g$, then $e_i$ is the \emph{leading exponent} of $g$.
If $g$ has depth $i$, then we call $r_i = [C_i:C_{i+1}]$ the \emph{factor order} of $g$. If $r < \infty$, then the smallest positive integer $l$ with $g^l \in C_{i+1}$ is the called \emph{relative order} of $g$. If $r=\infty$, then the relative order of $g$ is defined to be $0$. The index $e$ of $\langle g,C_{i+1}\rangle$ in $C_i$ is called \emph{relative index} of $g$. We have that $r = el$.
We call a pcp\texttt{\symbol{45}}element \emph{normed}, if its leading exponent is equal to its relative index. For each
pcp\texttt{\symbol{45}}element $g$ there exists an integer $e$ such that $g^e$ is normed.
returns the exponent vector of the pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}} with respect to the defining generating set of the underlying collector. }
returns the generators exponent list of the pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}} with respect to the defining generating set of the underlying collector. }
the name used for printing the pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}}. Printing is done by using the name tag and appending the generator number of \mbox{\texttt{\mdseries\slshape g}}. }
returns the leading exponent of pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}} relative to the defining generators. If \mbox{\texttt{\mdseries\slshape g}} is the identity element, the functions returns 'fail' }
returns a positive integer $e$ such that the pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}} raised to the power of $e$ is normed. }
returns the normed element corresponding to the pcp\texttt{\symbol{45}}element \mbox{\texttt{\mdseries\slshape g}}. }
}
\section{\textcolor{Chapter }{Pcp\texttt{\symbol{45}}groups \texttt{\symbol{45}} groups of
pcp\texttt{\symbol{45}}elements}}\label{pcpgroup} \logpage{[ 4, 3, 0 ]} \hyperdef{L}{X7A4EF7C68151905A}{}
{
A \emph{pcp\texttt{\symbol{45}}group} is a group consisting of pcp\texttt{\symbol{45}}elements such that all
pcp\texttt{\symbol{45}}elements in the group share the same collector. Thus
the group $G$ defined by a polycyclic presentation and all its subgroups are
pcp\texttt{\symbol{45}}groups.
returns a pcp\texttt{\symbol{45}}group build from the collector \mbox{\texttt{\mdseries\slshape coll}}.
The function calls \texttt{UpdatePolycyclicCollector} (\ref{UpdatePolycyclicCollector}) and checks the confluence (see \texttt{IsConfluent} (\ref{IsConfluent})) of the collector.
The non\texttt{\symbol{45}}check version bypasses these checks. }
returns the group generated by the pcp\texttt{\symbol{45}}elements \mbox{\texttt{\mdseries\slshape gens}} with identity \mbox{\texttt{\mdseries\slshape id}}. }
returns a subgroup of the pcp\texttt{\symbol{45}}group \mbox{\texttt{\mdseries\slshapeG}} generated by the list \mbox{\texttt{\mdseries\slshape gens}} of pcp\texttt{\symbol{45}}elements from \mbox{\texttt{\mdseries\slshape G}}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@ ftl := FromTheLeftCollector( 2 );;|
!gapprompt@gap>| !gapinput@ SetRelativeOrder( ftl, 1, 2 );|
!gapprompt@gap>| !gapinput@ SetConjugate( ftl, 2, 1, [2,-1] );|
!gapprompt@gap>| !gapinput@ UpdatePolycyclicCollector( ftl );|
!gapprompt@gap>| !gapinput@ G:= PcpGroupByCollectorNC( ftl );|
Pcp-group with orders [ 2, 0 ]
!gapprompt@gap>| !gapinput@Subgroup( G, GeneratorsOfGroup(G){[2]} );|
Pcp-group with orders [ 0 ] \end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Basic methods and functions for pcp\texttt{\symbol{45}}groups}}\label{Basic methods and functions for pcp-groups} \logpage{[ 5, 0, 0 ]} \hyperdef{L}{X7B9B85AE7C9B13EE}{}
{
Pcp\texttt{\symbol{45}}groups are groups in the \textsf{GAP} sense and hence all generic \textsf{GAP} methods for groups can be applied for pcp\texttt{\symbol{45}}groups. However,
for a number of group theoretic questions \textsf{GAP} does not provide generic methods that can be applied to
pcp\texttt{\symbol{45}}groups. For some of these questions there are functions
provided in \textsf{Polycyclic}. \section{\textcolor{Chapter }{Elementary methods for pcp\texttt{\symbol{45}}groups}}\label{methods} \logpage{[ 5, 1, 0 ]} \hyperdef{L}{X821360107E355B88}{}
{
In this chapter we describe some important basic functions which are available
for pcp\texttt{\symbol{45}}groups. A number of higher level functions are
outlined in later sections and chapters.
Let $U, V$ and $N$ be subgroups of a pcp\texttt{\symbol{45}}group.
returns the index of \mbox{\texttt{\mdseries\slshape V}} in \mbox{\texttt{\mdseries\slshape U}} if \mbox{\texttt{\mdseries\slshape V}} is a subgroup of \mbox{\texttt{\mdseries\slshape U}}. The function does not check if \mbox{\texttt{\mdseries\slshape V}} is a subgroup of \mbox{\texttt{\mdseries\slshape U}} and if it is not, the result is not meaningful. }
returns a list containing all elements of \mbox{\texttt{\mdseries\slshape U}} if \mbox{\texttt{\mdseries\slshape U}} is finite and it returns the list [fail] otherwise. }
returns the group generated by all commutators $[u,v]$ with $u$ in \mbox{\texttt{\mdseries\slshape U}} and $v$ in \mbox{\texttt{\mdseries\slshape V}}. }
checks whether \mbox{\texttt{\mdseries\slshape U}} is free abelian. }
}
\section{\textcolor{Chapter }{Subgroups of pcp\texttt{\symbol{45}}groups}}\label{Subgroups of pcp-groups} \logpage{[ 5, 3, 0 ]} \hyperdef{L}{X85A7E26C7E14AFBA}{}
{
A subgroup of a pcp\texttt{\symbol{45}}group $G$ can be defined by a set of generators as described in Section \ref{pcpgroup}. However, many computations with a subgroup $U$ need an \emph{induced generating sequence} or \emph{igs} of $U$. An igs is a sequence of generators of $U$ whose list of exponent vectors form a matrix in upper triangular form. Note
that there may exist many igs of $U$. The first one calculated for $U$ is stored as an attribute.
An induced generating sequence of a subgroup of a pcp\texttt{\symbol{45}}group $G$ is a list of elements of $G$. An igs is called \emph{normed}, if each element in the list is normed. Moreover, it is \emph{canonical}, if the exponent vector matrix is in Hermite Normal Form. The following
functions can be used to compute induced generating sequence for a given
subgroup \mbox{\texttt{\mdseries\slshape U}} of \mbox{\texttt{\mdseries\slshape G}}.
returns an induced generating sequence of the subgroup \mbox{\texttt{\mdseries\slshape U}} of a pcp\texttt{\symbol{45}}group. In the second form the subgroup is given
via a generating set \mbox{\texttt{\mdseries\slshape gens}}. The third form computes an igs for the subgroup generated by \mbox{\texttt{\mdseries\slshape gens}} carrying \mbox{\texttt{\mdseries\slshape gens2}} through as shadows. This means that each operation that is applied to the
first list is also applied to the second list. }
\subsection{\textcolor{Chapter }{Ngs (for a subgroup)}} \logpage{[ 5, 3, 2 ]}\nobreak \hyperdef{L}{X7F4D95C47F9652BA}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Ngs({\mdseries\slshape U})\index{Ngs@\texttt{Ngs}!for a subgroup} \label{Ngs:for a subgroup}
}\hfill{\scriptsize (attribute)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Ngs({\mdseries\slshape igs})\index{Ngs@\texttt{Ngs}} \label{Ngs}
}\hfill{\scriptsize (function)}}\\
returns a normed induced generating sequence of the subgroup \mbox{\texttt{\mdseries\slshape U}} of a pcp\texttt{\symbol{45}}group. The second form takes an igs as input and
norms it. }
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
