%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  basics.tex             GAP documentation                 Bettina Eick
%W                                                          Werner Nickel
%%
%H  $Id: basics.tex,v 1.9 2008/11/10 08:04:16 gap Exp $
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Basic methods and functions for pcp-groups}

Pcp-groups are groups in the {\GAP} sense and hence all generic {\GAP}
methods for groups can be applied for pcp-groups.  However, for a
number of group theoretic questions {\GAP} does not provide generic
methods that can be applied to pcp-groups. For some of these questions
there are functions provided in {\sf polycyclic}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Elementary methods for pcp-groups}
\label{methods}

In this chapter we describe some important basic functions which are 
available for pcp-groups. A number of higherlevel functions are outlined 
in later sections and chapters.

Let $U, V$ and $N$ are subgroups of a pcp-group.

\>`U = V'{equality}!{subgroups}

decides if <U> and <V> are equal as sets.

\>Size( <U> )

returns the size of <U>.

\>Random( <U> )

returns a random element of <U>. 

\>Index( <U>, <V> )

returns the index of  <V> in <U>  if <V>  is  a subgroup of  <U>.  The
function does not check if <V> is a subgroup of <U> and  if it is not,
the result is not meaningful.

\>`$g$ in $U$'{membership}

checks if <g> is an element of <U>.

\>Elements( <U> )

returns a list  containing all elements of  <U> if <U> is finite and it
returns the list [fail] otherwise.

\>ClosureGroup( <U>, <V> )

returns the group generated by <U> and <V>.

\>NormalClosure( <U>, <V> )

returns  the normal closure of <V>  under action of <U>. 

\>HirschLength( <U> )

returns the Hirsch length of <U>.

\>CommutatorSubgroup( <U>, <V> )

returns the group generated by all commutators $[u,v]$ with $u$ in <U>
and $v$ in <V>.

\>PRump( <U>, <p> )

returns the subgroup $U'U^p$ of <U> where <p> is a prime number.

\> SmallGeneratingSet( <U> )

returns a small generating set for <U>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Elementary properties of pcp-groups}

\>IsSubgroup( <U>, <V> )

tests if <V> is a subgroup of <U>.

\>IsNormal( <U>, <V> )

tests if <V> is normal in <U>.

\>IsNilpotentGroup( <U> )

checks whether <U> is nilpotent.

\>IsAbelian( <U> )

checks whether <U> is abelian.

\>IsElementaryAbelian( <U> )

checks whether <U> is elementary abelian.

\>IsFreeAbelian( <U> )

checks whether <U> is free abelian.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subgroups of pcp-groups}

A subgroup of a pcp-group $G$ can be defined by a set of generators as 
described in Section "pcpgroup". However, many computations  with a 
subgroup $U$ need  an *induced generating sequence* or *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-group $G$ is a
list of elements of $G$.  An igs is called *normed*, if each element
in the list is normed.  Moreover, it is *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
<U> of <G>.

\>Igs( <U> )
\>Igs( <gens> )
\>IgsParallel( <gens>, <gens2> )

returns an induced generating sequence of the subgroup <U> of a
pcp-group. In the second form the subgroup is given via a generating
set <gens>. The third form computes an igs for the subgroup generated
by <gens> carrying <gens2> through as shadows.  This means that each
operation that is applied to the first list is also applied to the
second list.



\>Ngs( <U> )
\>Ngs( <igs> )

returns a normed induced generating sequence of the subgroup <U> of a
pcp-group. The second form takes an igs as input and norms it.

\>Cgs( <U> )
\>Cgs( <igs> )
\>CgsParallel( <gens>, <gens2> )

returns a canonical generating sequence of the subgroup <U> of a
pcp-group. In the second form the function takes an igs as input and
returns a canonical generating sequence. The third version takes a
generating set and computes a canonical generating sequence carrying
<gens2> through as shadows.  This means that each operation that is
applied to the first list is also applied to the second list.

For a large number of methods for pcp-groups <U> we will first of all 
determine an <igs> for <U>. Hence it might speed up computations, if 
a known <igs> for a group <U> is set {\it a priori}. The following 
functions can be used for this purpose.

\>SubgroupByIgs( <G>, <igs> )
\>SubgroupByIgs( <G>, <igs>, <gens> )

returns the subgroup of the pcp-group <G> generated by the elements of
the induced  generating sequence <igs>.   Note that  <igs> must  be an
induced generating sequence of  the subgroup generated by the elements
of the <igs>. In the second form <igs> is a igs for a subgroup and 
<gens> are some generators. The function returns the subgroup generated
by <igs> and <gens>. 

\> AddToIgs( <igs>, <gens> )
\> AddToIgsParallel( <igs>, <gens>, <igs2>, <gens2> )
\> AddIgsToIgs( <igs>, <igs2> )

sifts the elements in the list $gens$ into $igs$.  The second version
has the same functionality and carries shadows.  This means that each
operation that is applied to the first list and the element <gens> is
also applied to the second list and the lement <gens2>.  The third
version is available for efficiency reasons and assumes that the
second list <igs2> is not only a generating set, but an igs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Polycyclic presentation sequences for subfactors}
\label{pcps}

A subfactor of a pcp-group $G$ is again a polycyclic group for which a
polycyclic presentation can computed.  However, to compute a polycyclic
presentation for  a given subfactor  can  be time-consuming.  Hence we
introduce *polycyclic presentation sequences* or *Pcp* to compute more
efficiently with subfactors. (Note that a subgroup is also a subfactor 
and  thus can be handled by a pcp)

A pcp for a pcp-group $U$ or a subfactor $U /  N$ can be created with
one of the following functions.

\>Pcp( <U> )
\>Pcp( <U>, <N> )
\>Pcp( <U>, <"snf"> )
\>Pcp( <U>, <N>, <"snf"> )

returns a polycyclic presentation sequence for the subgroup <U> or the
quotient group  <U> modulo <N>.  If the  parameter <`"snf"'> is present,
the function can only be applied to an abelian  subgroup <U>  or abelian
subfactor   <U>/<N>.   The pcp  returned  will correspond     to a
decomposition of  the abelian  group  into a direct  product of cyclic
groups.

\bigskip
A  pcp   is  a component  object which    behaves similar  to   a list
representing an igs of the  subfactor in question. The basic functions
to   obtain  the  stored  values of  this     component object  are as
follows.  Let $pcp$  be a pcp  for  a subfactor $U/N$  of the defining
pcp-group $G$.

\>GeneratorsOfPcp( <pcp> )

this returns a list   of elements of $U$   corresponding to an  igs of
$U/N$.

\>`pcp[i]'{pcp}!{as list}

returns the <i>-th element of <pcp>.

\>Length( <pcp> )

returns the number of generators in <pcp>.

\>RelativeOrdersOfPcp( <pcp> )

the relative orders of the igs in <U/N>.

\>DenominatorOfPcp( <pcp> )

returns an igs of <N>. 

\>NumeratorOfPcp( <pcp> )

returns an igs of <U>.

\>GroupOfPcp( <pcp> )

returns <U>.

% \item $DefiningGroupOfPcp( <pcp> )$ returns $G$.

\>OneOfPcp( <pcp> )

returns the identity element of <G>.

\bigbreak
The two main  features of pcp are the  possibility to compute exponent
vectors  with respect to to   a pcp  and   to compute  the  group   defined by the
corresponding igs of $U/N$.

\>ExponentsByPcp( <pcp>, <g> )

returns the exponent vector  of <g> with  respect to the generators of
<pcp>.  This is the exponent vector of <g>$N$ with  respect to the igs
of <U/N>.

\>PcpGroupByPcp( <pcp> )

let <pcp> be a Pcp of a subgroup or a factor group of a pcp-group. This
function computes a new pcp-group whose defining generators correspond
to the generators in <pcp>.


\beginexample
gap>  G := DihedralPcpGroup(0);
Pcp-group with orders [ 2, 0 ]
gap>  pcp := Pcp(G);
Pcp [ g1, g2 ] with orders [ 2, 0 ]
gap>  pcp[1];
g1
gap>  Length(pcp);
2
gap>  RelativeOrdersOfPcp(pcp);
[ 2, 0 ]
gap>  DenominatorOfPcp(pcp);
[  ]
gap>  NumeratorOfPcp(pcp);
[ g1, g2 ]
gap>  GroupOfPcp(pcp);
Pcp-group with orders [ 2, 0 ]
gap> OneOfPcp(pcp);
identity
\endexample

\beginexample
gap> G := ExamplesOfSomePcpGroups(5);
Pcp-group with orders [ 2, 0, 0, 0 ]
gap> D := DerivedSubgroup( G );
Pcp-group with orders [ 0, 0, 0 ]
gap>  GeneratorsOfGroup( G );
[ g1, g2, g3, g4 ]
gap>  GeneratorsOfGroup( D );
[ g2^-2, g3^-2, g4^2 ]

# an ordinary pcp for G / D
gap> pcp1 := Pcp( G, D );
Pcp [ g1, g2, g3, g4 ] with orders [ 2, 2, 2, 2 ]

# a pcp for G/D in independent generators
gap>  pcp2 := Pcp( G, D, "snf" );
Pcp [ g2, g3, g1 ] with orders [ 2, 2, 4 ]

gap>  g := Random( G );
g1*g2^-4*g3*g4^2

# compute the exponent vector of g in G/D with respect to pcp1
gap> ExponentsByPcp( pcp1, g );
[ 1, 0, 1, 0 ]

# compute the exponent vector of g in G/D with respect to pcp2
gap>  ExponentsByPcp( pcp2, g );
[ 0, 1, 1 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Factor groups of pcp-groups}

Pcp's for subfactors of  pcp-groups have already been described above.
These are usually used within  algorithms to compute with  pcp-groups.
However, it is also possible to explicitly construct factor groups and
their corresponding natural homomorphisms.

\>NaturalHomomorphism( <G>, <N> )

returns  the natural homomorphism   $G \ra  G/N$.  Its image  is the
factor group $G/N$.

\>`G/N'{factor group}
\>FactorGroup( <G>, <N> )

returns  the desired factor as  pcp-group without  giving the explicit
homomorphism. This function is just a wrapper for 
`PcpGroupByPcp( Pcp( G, N ) )'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Homomorphisms for pcp-groups}

$IsPcpGHBI$ is a representation used to  define group homomorphisms by
generators  and images from a pcp-group  into another pcp-group.  Such
homomorphisms can be compared and multiplied. Moreover, we provide the
following functions.

\bigbreak
$IsToPcpGHBI$ is a  representation used to define group  homomorphisms
by  generators and images  from an  arbitrary  group into a pcp-group.
Here,  only very restricted functionality is  provided. This is mostly
used for converting other groups to pcp-groups.

\>GroupHomomorphismByImages( <G>, <H>, <gens>, <imgs> )

returns the homomorphism from the (pcp-) group <G> to the pcp-group <H>
mapping the generators of <G> in the  list <gens> to the corresponding
images in the list <imgs> of elements of <H>.

\>Kernel( <hom> )

returns the kernel of  the homomorphism <hom> from   a pcp-group to  a
pcp-group.

\>Image( <hom> )
\>Image( <hom>, <U> )
\>Image( <hom>, <g> )

returns the image of the whole group, of <U> and of <g>, respectively,
under the homomorphism <hom>.

\>PreImage( <hom>, <U> )

returns   the  complete  preimage of    the   subgroup <U>  under  the
homomorphism <hom>.  If the domain of <hom> is  not a pcp-group, then
this function only works properly if <hom> is injective.


\>PreImagesRepresentative( <hom>, <g> )

returns a preimage of the element <g> under the homomorphism <hom>.

\>IsInjective( <hom> )

checks if the homomorphism <hom> is injective.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Changing the defining pc-presentation}

\>RefinedPcpGroup( <G> )

returns a new  pcp-group isomorphic to  <G>  whose defining polycyclic
presentation is refined;  that is, the corresponding polycyclic series
has  prime or infinite  factors only. If  $H$ is  the  new group, then
$H!.bijection$ is the isomorphism $G \ra H$.

\>PcpGroupBySeries( <ser> )
\>PcpGroupBySeries( <ser>, "snf" )

returns a  new pcp-group isomorphic to  the first subgroup  $G$ of the
given  series <ser>  such  that  its defining  pcp  refines the  given
series.  The  series  must  be  subnormal and  $H!.bijection$  is  the
isomorphism  $G \ra  H$.  In  the second  form, the  series  must have
abelian  factors.  The  pcp of  the  group returned  corresponds to  a
decomposition of each  abelian factor into a direct  product of cyclic
groups.

\beginexample
gap> G := DihedralPcpGroup(0);
Pcp-group with orders [ 2, 0 ]
gap>  U := Subgroup( G, [Pcp(G)[2]^1440]);
Pcp-group with orders [ 0 ]
gap>  F := G/U;
Pcp-group with orders [ 2, 1440 ]
gap> RefinedPcpGroup(F);
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 3, 3, 5 ]

gap> ser := [G, U, TrivialSubgroup(G)];
[ Pcp-group with orders [ 2, 0 ],
  Pcp-group with orders [ 0 ],
  Pcp-group with orders [  ] ]
gap>  PcpGroupBySeries(ser);
Pcp-group with orders [ 2, 1440, 0 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Printing a pc-presentation}

By default, a pcp-group is printed using its relative orders only. The
following methods can be used to view the pcp presentation of the group.

\> PrintPcpPresentation( <G> )
\> PrintPcpPresentation( <pcp> )

prints the pcp presentation defined by the igs of <G> or the pcp <pcp>. 
As usual, the trivial conjugate relations are omitted from this 
presentation to shorten notation. Also, the relations obtained from
conjugating with inverse generators are included only if the conjugating
generator has infinite order. If this generator has finite order, then
the conjugation relation is a consequence of the remaining relations.

\> PrintPcpPresentation( <G>, "all" )
\> PrintPcpPresentation( <pcp>, "all" )

prints the full defining pcp presentation defined by the igs of <G> or the 
pcp <pcp>. Here the trivial conjugate relations are always included and also
the conjugation with inverses is always included.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Converting to and from a presentation}

\>IsomorphismPcpGroup( <G> )

returns an isomorphism from <G> onto a pcp-group <H>. There are various
methods installed for this operation and some of these methods are part
of the Polycyclic package, while others may be part of other packages. 

For example, Polycyclic contains methods for this function in the case
that <G> is a finite pc-group or a finite solvable permutation group. 
Further, Polycyclic can convert a finitely presented group with a 
polycyclic presentation into a pcp group via IsomorphismPcpGroup.

Other examples for methods for IsomorphismPcpGroup are the methods for
the case that <G> is a crystallographic group (see Cryst) or the case
that <G> is an almost crystallographic group (see AClib). A general 
method for the case that <G> is a rational polycyclic matrix group will
be included in the Polenta package. A general method for the case that
<G> is a polycyclic finitely presented group will be included in the
IPCQ package. 

\>IsomorphismPcGroup( <G> )

pc-groups are a representation for finite polycyclic groups. This function
can convert finite pcp-groups to pc-groups.