%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  nq.tex		NQL Doc				Rene Hartung
%%
%H  $Id: nq.tex,v 1.8 2008/08/29 07:10:02 gap Exp $
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Nilpotent Quotients of L-presented groups}

Our nilpotent quotient algorithm for finitely $L$-presented groups
generalizes Nickel's algorithm for finitely presented groups;
see~\cite{Nickel96}. It determines a nilpotent presentation for the lower
central series quotient of an invariantly $L$-presented group. A nilpotent
presentation is a polycyclic presentation whose polycyclic series refines
the lower central series of the group (see the description
in the {\NQ}-package for further details). In general, our algorithm
determines a polycyclic presentation for the nilpotent quotient of
an arbitrary finitely $L$-presented group. For further details on our
algorithm we refer to~\cite{BEH07} or to the diploma thesis~\cite{H08}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{New methods for L-presented groups}

\> NilpotentQuotient( <LpGroup>[, <c>] ) O

returns a polycyclic presentation for the class-<c> quotient ${\rm
<LpGroup>}/\gamma_{c+1}({\rm <LpGroup>})$ if <c> is specified.  If <c>
is not given, this method attempts to compute the largest nilpotent
quotient of <LpGroup> and will terminate only if <LpGroup> has a largest
nilpotent quotient.

The following example computes the class-$5$ quotient of the Grigorchuk
group.
\beginexample
gap> G := ExamplesOfLPresentations( 1 );;
gap> H := NilpotentQuotient( G, 5 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 
gap> lcs := LowerCentralSeries( H );
[ Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ], 
  Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2 ], 
  Pcp-group with orders [ 2, 2, 2, 2, 2 ], Pcp-group with orders [ 2, 2, 2 ], 
  Pcp-group with orders [ 2, 2 ], Pcp-group with orders [  ] ]
gap> List( [ 1..5 ], x -> lcs[ x ] / lcs[ x+1 ] ); 
[ Pcp-group with orders [ 2, 2, 2 ], Pcp-group with orders [ 2, 2 ], 
  Pcp-group with orders [ 2, 2 ], Pcp-group with orders [ 2 ], 
  Pcp-group with orders [ 2, 2 ] ]
\endexample

\> LargestNilpotentQuotient( <LpGroup> )  A

returns the largest nilpotent quotient of the $L$-presented group
<LpGroup> if it exists. It uses the method `NilpotentQuotient' described
above. If <LpGroup> has no largest nilpotent quotient, this method will
not terminate.

\> NqEpimorphismNilpotentQuotient( <LpGroup>[, <c>] ) O
\> NqEpimorphismNilpotentQuotient( <LpGroup>[, <PcpGroup>] ) O

In the first case, this method returns an epimorphism from the
$L$-presented group <LpGroup> onto its class-<c> quotient ${\rm
<LpGroup>}/\gamma_{c+1}({\rm <LpGroup>})$ if <c> is specified. If <c>
is not given, this method attempts to compute an epimorphism onto the
largest nilpotent quotient of <LpGroup>. If <LpGroup> does not have a
largest nilpotent quotient, this method will not terminate.

If a pcp-group <PcpGroup> is given as additional parameter, then
<PcpGroup> has to be a nilpotent quotient of <LpGroup>. The method
computes an epimorphism from the $L$-presented group <LpGroup> onto
<PcpGroup>.

The following example computes an epimorphism from the Grigorchuk group
onto its class-$5$, class-$7$, and class-$10$ quotient.

\beginexample
gap> G := ExamplesOfLPresentations( 1 );
<L-presented group on the generators [ a, b, c, d ]>
gap> epi := NqEpimorphismNilpotentQuotient( G, 5 );
[ a, b, c, d ] -> [ g1, g2*g3, g2, g3 ]
gap> H := Image( epi );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> NilpotencyClassOfGroup( H );
5
gap> H := NilpotentQuotient( G, 7 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> NilpotentQuotient( G, 10 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> NqEpimorphismNilpotentQuotient( G, H );
[ a, b, c, d ] -> [ g1, g2*g3, g2, g3 ]
gap> Image( last );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
\endexample

\> AbelianInvariants( <LpGroup> ) O

computes the abelian invariants of the $L$-presented group
<LpGroup>. It uses the operation `NilpotentQuotient' described above
(see~"NilpotentQuotient").

\beginexample
gap> G := ExamplesOfLPresentations( 1 );;
gap> AbelianInvariants( G );
[ 2, 2, 2 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{A brief description of the algorithm}

In the following we give a brief description of the nilpotent quotient
algorithm for an arbitrary finitely $L$-presented group. For further
details, we refer to \cite{BEH07} and the diploma thesis~\cite{H08} .

Let $(S,Q,\Phi,R)$ be a finite $L$-presentation defining the
$L$-presented group $G$ and let $(S,Q',\Phi,R)$ be an underlying invariant
$L$-presentation. Write $\bar G$ for the invariantly $L$-presented group
defined by $(S,Q',\Phi,R)$.

The first step in computing a polycyclic presentation for $G/\gamma_c(G)$
is to determine a nilpotent presentation for $\bar G/\gamma_c(\bar G)$.
This will be done by induction on $c$. The induction step of our algorithm
generalizes the induction step of Nickel's algorithm which mainly relies
on Hermite normal form computations. In order to use this rather fast
linear algebra, we must require the group to be invariantly $L$-presented.
Therefore, the fixed relators must be handled separately by reducing to
an underlying invariant $L$-presentation first.

The induction step of our algorithm then returns a nilpotent presentation
$H$ for the quotient $\bar G/\gamma_c(\bar G)$ and an epimorphism
$\delta\colon\bar G\to H$.  Both are used to determine a polycyclic
presentation for the nilpotent quotient $G/\gamma_c(G)$ using an
extension $\delta'\colon F_S\to H$ of the epimorphism $\delta$. The
quotient $G/\gamma_c(G)$ is isomorphic to the factor group $H/\langle
Q^{\delta'}\rangle^H$.  We use the {\Polycyclic}-package to compute a
polycyclic presentation for $H/\langle Q^{\delta'}\rangle^H$.

The efficiency of this general approach depends on the underlying
invariant $L$-presentation $(S,Q',\Phi,R)$.  The set of fixed relators
$Q'$ should be as large as possible. Otherwise, the nilpotent quotient
$H$ can be large even if the nilpotent quotient $G/\gamma_c(G)$ is
rather small.

The following example demonstrates the different behavior of our nilpotent
quotient algorithm for the Grigorchuk group with its finite $L$-presentation
$$ \Big(\{a,c,b,d\},\{a^2,b^2,c^2,d^2,bcd\},\{\sigma\},
	            \{[d,d^a],[d,d^{acaca}]\} \Big). $$
This latter $L$-presentation is obviously an
invariant $L$-presentation. Hence, we can either use
the property `IsInvariantLPresentation' or the attribute
`UnderlyingInvariantLPresentation'. First, one has to construct the
group as described in Section~"Creating an L-presented group":

\beginexample
gap> F := FreeGroup( "a", "b", "c", "d" );
<free group on the generators [ a, b, c, d ]>
gap> AssignGeneratorVariables( F );
#I  Assigned the global variables [ a, b, c, d ]
gap> rels := [ a^2, b^2, c^2, d^2, b*d*c ];;
gap> endos := [ GroupHomomorphismByImagesNC( F, F, [ a, b, c, d ], [ c^a, d, b, c ]) ];;
gap> itrels := [ Comm( d, d^a ), Comm( d, d^(a*c*a*c*a) ) ];;
gap> G := LPresentedGroup( F, rels, endos, itrels );
<L-presented group on the generators [ a, b, c, d ]>
gap> List( rels, x -> x^endos[1] );
[ a^-1*c^2*a, d^2, b^2, c^2, d*c*b ]
\endexample

The property `IsInvariantLPresentation' can be set manually using
`SetInvariantLPresentation'.
\beginexample
gap> SetIsInvariantLPresentation( G, true );
gap> NilpotentQuotient( G, 4 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> StringTime( time );
" 0:00:00.032"
\endexample

On the other hand, one can use the attribute
`UnderlyingInvariantLPresentation' as follows.

\beginexample
gap> U := LPresentedGroup( F, rels, endos, itrels );
<L-presented group on the generators [ a, b, c, d ]>
gap> SetUnderlyingInvariantLPresentation( G, U );
gap> NilpotentQuotient( G, 4 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> StringTime( time );
" 0:00:00.028"
\endexample

For saving memory the first method should be preferred in this case. In
general, the $L$-presentation is not invariant (or not known to be
invariant) and thus the underlying invariant $L$-presentation has fewer
fixed relators than the group $G$ itself. In this case, the second method
is the method of choice.

There is a brute-force method implemented for the operation
`UnderlyingInvariantLPresentation' which works quite well on the
`ExamplesOfLPresentations'. However, in the worst case, this method will
return the underlying ascending $L$-presentation. The following example
shows the influence of this choice to the runtime of the nilpotent
quotient algorithm. After defining the group $G$ as above, we set the
attribute `UnderlyingInvariantLPresentation' as follows.

\beginexample
gap> SetUnderlyingInvariantLPresentation( G, UnderlyingAscendingLPresentation( G ) );
gap> NilpotentQuotient( G, 4 );
Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> StringTime( time );
" 0:00:02.700"
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E  nq.tex  . . . . . . . . . . . . . . . . . . . . . . . . . . . ends here