%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  pcpmeths.tex           GAP documentation                 Bettina Eick
%W                                                          Werner Nickel
%%
%H  $Id: pcpmeths.tex,v 1.10 2000/04/13 15:35:55 gap Exp $
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Methods for pcp-groups}

This is a description of some higher level functions of the {\sf polycyclic}
share package of GAP 4. Throughout this chapter we let <G> be a pc-presented 
group and we consider algorithms for subgroups <U> and <V> of <G>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Orbit stabilizer methods for pcp-groups}

The following two functions are implementations of the polycyclic 
group algorithm to compute orbits and stabilizers, if the orbits
are finite.

\> PcpOrbitStabilizer( <point>, <gens>, <acts>, <oper> ) 
\> PcpOrbitsStabilizers( <points>, <gens>, <acts>, <oper> )

The input <gens> can an igs or a pcp of a pcp-group <U>. The elements
in the list <gens> act as the elements in the list <acts> and the function
<oper> on the given points. The first function returns a record containing 
'orbit' and 'stab'. The latter is an induced igs of the stabilizer. The 
second function returns a list of records, each record contains 'repr' and 
'stab'.

Both of these functions run forever on infinite orbits.

\beginexample
gap> G := DihedralPcpGroup( 0 );
Pcp-group with orders [ 2, 0 ]
gap> mats := [ [[-1,0],[0,1]], [[1,1],[0,1]] ];;
gap> pcp := Pcp(G);
Pcp [ g1, g2 ] with orders [ 2, 0 ]
gap> PcpOrbitStabilizer( [0,1], pcp, mats, OnRight );
rec( orbit := [ [ 0, 1 ] ],
     stab := [ g1, g2 ],
     word := [ [ [ 1, 1 ] ], [ [ 2, 1 ] ] ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subgroup series in pcp-groups}

Many algorithm for pcp-groups work by induction using some series
through the group. In this section we prove a number of useful series
for pcp-groups. Note that an *efa series* is a normal series with
elementary or free abelian factors. See \cite{Eic00} for an outline
on the algorithms of a number of the available series.

\>PcpSeries( <U> )

returns the polycyclic series of <U> defined by an igs of <U>.

\>EfaSeries( <U> )

returns a normal series of <U> with elementary or free abelian factors.

\>DerivedSeries( <U> )

the derived series of <U>.

\>RefinedDerivedSeries( <U> )

the  derived series of <U> refined  to an efa series such that
in each abelian factor of the  derived series the free abelian
factor is at the top.

\>RefinedDerivedSeriesDown( <U> )

the  derived series of <U> refined  to an efa series such that
in each abelian factor of  the derived series the free abelian
factor is at the bottom.

\>LowerCentralSeries( <U> )

the lower  central  series of <U>.  If  <U>  does not   have a
largest  nilpotent quotient group, then  this function may not
terminate.

\>TorsionByPolyEFSeries( <U> )

returns  an  efa series  of   <U> such  that  all torsion-free
factors  are  at the  top and  all  finite  factors are at the
bottom. Such a series might not exist for <U> and in this case
the function returns fail.

\beginexample
gap> G := PcpExamples[5];
Pcp-group with orders [ 2, 0, 0, 0 ]
gap> Igs(G);
[ g1, g2, g3, g4 ]

gap> PcpSeries(G);
[ Pcp-group with orders [ 2, 0, 0, 0 ],
  Pcp-group with orders [ 0, 0, 0 ],
  Pcp-group with orders [ 0, 0 ],
  Pcp-group with orders [ 0 ],
  Pcp-group with orders [  ] ]

gap> List( PcpSeries(G), Igs );
[ [ g1, g2, g3, g4 ], [ g2, g3, g4 ], [ g3, g4 ], [ g4 ], [  ] ]
\endexample

Algorithms for pcp-groups often use an efa series of $G$ and work down
over the factors of  this series. Usually,   pcp's of the factors  are
more useful than the actual factors. Hence we provide the following.

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

returns  a  list of  pcp's corresponding  to  the factors of the
series.   If   the second argument  is  present,  then  each pcp
corresponds to a decomposition of  the abelian groups into direct
factors.

\>PcpsOfEfaSeries( <U> )

return a list of pcp's corresponding to an efa series of <U>.

\beginexample
gap> G := PcpExamples[5];
Pcp-group with orders [ 2, 0, 0, 0 ]

gap> PcpsBySeries( DerivedSeries(G));
[ Pcp [ g1, g2, g3, g4 ] with orders [ 2, 2, 2, 2 ],
  Pcp [ g2^-2, g3^-2, g4^2 ] with orders [ 0, 0, 4 ],
  Pcp [ g4^8 ] with orders [ 0 ] ]
gap> PcpsBySeries( RefinedDerivedSeries(G));
[ Pcp [ g1, g2, g3 ] with orders [ 2, 2, 2 ],
  Pcp [ g4 ] with orders [ 2 ],
  Pcp [ g2^2, g3^2 ] with orders [ 0, 0 ],
  Pcp [ g4^2 ] with orders [ 2 ],
  Pcp [ g4^4 ] with orders [ 2 ],
  Pcp [ g4^8 ] with orders [ 0 ] ]

gap> PcpsBySeries( RefinedDerivedSeries(G), "snf");
[ Pcp [ g1, g2, g3 ] with orders [ 2, 2, 2 ],
  Pcp [ g4 ] with orders [ 2 ],
  Pcp [ g2^2, g3^2 ] with orders [ 0, 0 ],
  Pcp [ g4^2 ] with orders [ 2 ],
  Pcp [ g4^4 ] with orders [ 2 ],
  Pcp [ g4^8 ] with orders [ 0 ] ]

gap>  PcpsOfEfaSeries( G );
[ Pcp [ g1 ] with orders [ 2 ],
  Pcp [ g2 ] with orders [ 0 ],
  Pcp [ g3 ] with orders [ 0 ],
  Pcp [ g4 ] with orders [ 0 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Random methods and functions available for pcp-groups}

Below we introduce a function which computes orbit and stabilizer using 
a random method. This function always terminates, also if the orbit is 
infinite. But the returned orbit or stabilizer might be incomplete. This 
function is used in the random methods to compute normalizers and 
centralizers.

\> RandomOrbitStabilizerPcpGroup( <U>, <point>, <oper> )

\> RandomCentralizerPcpGroup( <U>, <g> )

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

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

\beginexample
gap> G := DihedralPcpGroup(0);
Pcp-group with orders [ 2, 0 ]
gap> mats := [[[-1, 0],[0,1]], [[1,1],[0,1]]];
[ [ [ -1, 0 ], [ 0, 1 ] ], [ [ 1, 1 ], [ 0, 1 ] ] ]
gap> pcp := Pcp(G);
Pcp [ g1, g2 ] with orders [ 2, 0 ]

gap> RandomPcpOrbitStabilizer( [1,0], pcp, mats, OnRight ).stab;
#I  Orbit longer than limit: exiting.
[  ]

gap> g := Igs(G)[1];
g1
gap> RandomCentralizerPcpGroup( G, g );
#I  Stabilizer not increasing: exiting.
Pcp-group with orders [ 2 ]
gap> Igs(last);
[ g1 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Intersection of subgroups}

Currently, only intersections of subgroups $U, N \leq G$ can be computed
if $N$ is normalising $U$. See \cite{Sims94} for an outline of the 
algorithm.

\>NormalIntersection( <U>, <N> )

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finite subgroups}

There are various finite subgroups of interest in polycyclic groups. See
\cite{Eic00} for a description of the algorithms underlying the functions
in this section.

\> TorsionSubgroup( <U> )

If the set of elements of finite order forms a subgroup, then we call
it the *torsion subgroup*. This function determines the torsion subgroup
of <U>, if it exists, and returns fail otherwise. Note that a torsion
subgroup does always exist if <U> is nilpotent.

\> NormalTorsionSubgroup( <U> )

Each polycyclic groups has a unique largest finite normal subgroup.
This function computes it for <U>. 

\> IsTorsionFree( <U> )

This function checks if <U> is torsion free. It returns true or false.

\> FiniteSubgroupClasses( <U> )

There exist only finitely many conjugacy classes of finite subgroups
in a polycyclic group <U> and this function can be used to compute
them. The algorithm underlying this function proceeds by working down
a normal series of <U> with elementary or free abelian factors. The
following function can be used to give the algorithm a specific series.

\> FiniteSubgroupClassesBySeries( <U>, <pcps> )

\beginexample
gap> G := NqExamples[2];
Pcp-group with orders [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 4, 0 ]
gap> TorsionSubgroup(G);
Pcp-group with orders [ 5, 2 ]
gap> NormalTorsionSubgroup(G);
Pcp-group with orders [ 5, 2 ]
gap> IsTorsionFree(G);
false
gap> FiniteSubgroupClasses(G);
[ Pcp-group with orders [ 5, 2 ]^G,
  Pcp-group with orders [ 2 ]^G,
  Pcp-group with orders [ 5 ]^G,
  Pcp-group with orders [  ]^G ]

gap> G := DihedralPcpGroup( 0 );
Pcp-group with orders [ 2, 0 ]
gap> TorsionSubgroup(G);
fail
gap> NormalTorsionSubgroup(G);
Pcp-group with orders [  ]
gap> IsTorsionFree(G);
false
gap> FiniteSubgroupClasses(G);
[ Pcp-group with orders [ 2 ]^G,
  Pcp-group with orders [ 2 ]^G,
  Pcp-group with orders [  ]^G ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subgroups of finite index}

Here we outline functions to determine various types of subgroups of 
finite index in polycyclic groups. Again, see \cite{Eic00} for a 
description of the algorithms underlying the functions in this section.

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

Each maximal subgroup of a polycyclic group <U> has <p>-power index for
some prime <p>. This function can be used to determine conjugacy class
representatives of all maximal subgroups of <p>-power index for a given 
prime <p>.

\>LowIndexSubgroupClasses( <U>, <n> )

There are only finitely many subgroups of a given index in a polycyclic
group <U>. This function computes conjugacy classes of all subgroups of 
index <n> in <U>.

\>LowIndexNormals( <U>, <n> )

This function computes the normal subgroups of index <n> in <U>.

\>NilpotentByAbelianNormalSubgroup( <U> )

This function returns a normal subgroup <N> of finite index in <U>
such that <N> is nilpotent-by-abelian. Note that such a subgroup
exists in every polycyclic group. Note that this function is not
very efficient.

\beginexample
gap> G := PcpExamples[2];
Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ]

gap> MaximalSubgroupClassesPIndex( G, 61 );;
gap> max := List( last, Representative );;
gap> List( max, x -> Index( G, x ) );
[ 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61, 226981 ]

gap> LowIndexSubgroupClasses( G, 61 );;
gap> low := List( last, Representative );;
gap> List( low, x -> Index( G, x ) );
[ 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
  61, 61, 61, 61, 61, 61 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions for nilpotent groups}

\>MinimalGeneratingSet( <U> )

\>Centre( <U> )

\>UpperCentralSeries( <U> )

\beginexample
gap> G := NqExamples[1];
Pcp-group with orders [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 4, 0, 5, 5, 4, 0, 6,
  5, 5, 4, 0, 10, 6 ]
gap> IsNilpotent(G);
true

gap> PcpsBySeries( LowerCentralSeries(G));
[ Pcp [ g1, g2 ] with orders [ 0, 0 ],
  Pcp [ g3 ] with orders [ 0 ],
  Pcp [ g4 ] with orders [ 0 ],
  Pcp [ g5 ] with orders [ 0 ],
  Pcp [ g6, g7 ] with orders [ 0, 0 ],
  Pcp [ g8 ] with orders [ 0 ],
  Pcp [ g9, g10 ] with orders [ 0, 0 ],
  Pcp [ g11, g12, g13 ] with orders [ 5, 4, 0 ],
  Pcp [ g14, g15, g16, g17, g18 ] with orders [ 5, 5, 4, 0, 6 ],
  Pcp [ g19, g20, g21, g22, g23, g24 ] with orders [ 5, 5, 4, 0, 10, 6 ] ]

gap> PcpsBySeries( UpperCentralSeries(G));
[ Pcp [ g1, g2 ] with orders [ 0, 0 ],
  Pcp [ g3 ] with orders [ 0 ],
  Pcp [ g4 ] with orders [ 0 ],
  Pcp [ g5 ] with orders [ 0 ],
  Pcp [ g6, g7 ] with orders [ 0, 0 ],
  Pcp [ g8 ] with orders [ 0 ],
  Pcp [ g9, g10 ] with orders [ 0, 0 ],
  Pcp [ g11, g12, g13 ] with orders [ 5, 4, 0 ],
  Pcp [ g14, g15, g16, g17, g18 ] with orders [ 5, 5, 4, 0, 6 ],
  Pcp [ g19, g20, g21, g22, g23, g24 ] with orders [ 5, 5, 4, 0, 10, 6 ] ]

gap> MinimalGeneratingSet(G);
[ g1, g2 ]
\endexample

