Our nilpotent quotient algorithm for finitely L-presented groups generalizes Nickel's algorithm for finitely presented groups; see [Nic96]. 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 [BEH08] or to the diploma thesis [Har08].
‣ NilpotentQuotient( g[, c] ) | ( operation ) |
returns a polycyclic presentation for the class-c quotient \(g/\gamma_{c+1}(g)\) of the L-presented group g if c is specified. If c is not given, this method attempts to compute the largest nilpotent quotient of g and will terminate only if g has a largest nilpotent quotient.
The following example computes the class-5 quotient of the Grigorchuk group.
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 ] ]
‣ LargestNilpotentQuotient( g ) | ( operation ) |
returns the largest nilpotent quotient of the L-presented group g if it exists. It uses the method NilpotentQuotient (3.1-1). If g has no largest nilpotent quotient, this method will not terminate.
‣ NqEpimorphismNilpotentQuotient( g[, p/c] ) | ( operation ) |
This method returns an epimorphism from the L-presented group g onto a nilpotent quotient. If the optional argument is an integer c, the epimorphism is onto the maximal class-c quotient \(g//\gamma_{c+1}(g)\). If no second argument is given, this method attempts to compute an epimorphism onto the largest nilpotent quotient of g. If g does not have a largest nilpotent quotient, this method will not terminate.
If a pcp-group p is given as additional parameter, then p has to be a nilpotent quotient of g. The method computes an epimorphism from the L-presented group g onto p.
The following example computes an epimorphism from the Grigorchuk group onto its class-5, class-7, and class-10 quotients.
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 ]
‣ AbelianInvariants( g ) | ( operation ) |
computes the abelian invariants of the L-presented group g. It uses the operation NilpotentQuotient (3.1-1).
gap> G := ExamplesOfLPresentations( 1 );; gap> AbelianInvariants( G ); [ 2, 2, 2 ]
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 [BEH08] and the diploma thesis [Har08].
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+1}(G)\) is to determine a nilpotent presentation for \(\bar G/\gamma_{c+1}(\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+1}(\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+1}(G)\) using an extension \(\delta'\colon F_S\to H\) of the epimorphism \(\delta\). The quotient \(G/\gamma_{c+1}(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+1}(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 (2.5-4) or the attribute UnderlyingInvariantLPresentation (2.5-2). First, one has to construct the group as described in Section 2.2:
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 ]
The property IsInvariantLPresentation (2.5-4) can be set manually using SetInvariantLPresentation:
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"
On the other hand, one can use the attribute UnderlyingInvariantLPresentation (2.5-2) as follows:
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"
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 (2.5-2) which works quite well on the ExamplesOfLPresentations (2.2-2). 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 (2.5-2) as follows:
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"
For an invariantly L-presented group \(G\), our algorithm computes a nilpotent presentation for \(G/\gamma_{c+1}(G)\) by computing a weighted nilpotent quotient system for \(G/G'\) and extending it inductively to a weighted nilpotent quotient system for \(G/\gamma_{c+1}(G)\).
In the lpres package, a weighted nilpotent quotient system is a record containing the following entries:
the invariantly L-presented group \(G\).
FromTheLeftCollector (polycyclic: FromTheLeftCollector) of the nilpotent quotient represented by this quotient system.
the images of the generators of the L-presented group \(G\) under the epimorphism onto the nilpotent quotient Pccol. For each generator of \(G\) there is an integer or a generator exponent list. If the image is an integer int, the image is a definition of the int-th generator of the nilpotent presentation Pccol.
an epimorphism from the L-presented group \(G\) onto its nilpotent quotient Pccol with the images of the generators given by Imgs.
a list of the weight of each generator of the nilpotent presentation Pccol.
the definition of each generator of Pccol. Each generator in the quotient system has a definition as an image or as a commutator of the form \([a_j,a_i]\) where \(a_j\) and \(a_i\) are generators of a certain weight. If the i-th entry is an integer, the i-th generator of Pccol has a definition as an image. Otherwise, the i-th entry is a \(2\)-tuple \([k,l]\) and the i-th generator has a definition as commutator \([a_k,a_l]\).
A weighted nilpotent quotient system of an invariantly L-presented group can be computed with the following functions.
‣ InitQuotientSystem( lpgroup ) | ( operation ) |
computes a weighted nilpotent quotient system for the abelian quotient of the L-presented group lpgroup.
‣ ExtendQuotientSystem( QS ) | ( operation ) |
extends the weighted nilpotent quotient system QS for a class-\(c\) quotient of an invariantly L-presented group to a weighted nilpotent quotient system of its class-\(c+1\) quotient.
gap> G := ExamplesOfLPresentations( 1 ); <L-presented group on the generators [ a, b, c, d ]> gap> Q := InitQuotientSystem( G ); rec( Lpres := <L-presented group on the generators [ a, b, c, d ]>, Pccol := <<from the left collector with 3 generators>>, Imgs := [ 1, [ 2, 1, 3, 1 ], 2, 3 ], Epimorphism := [ a, b, c, d ] -> [ g1, g2*g3, g2, g3 ], Weights := [ 1, 1, 1 ], Definitions := [ 1, 3, 4 ] ) gap> ExtendQuotientSystem( Q ); rec( Lpres := <L-presented group on the generators [ a, b, c, d ]>, Pccol := <<from the left collector with 5 generators>>, Imgs := [ 1, [ 2, 1, 3, 1 ], 2, 3 ], Definitions := [ 1, 3, 4, [ 2, 1 ], [ 3, 1 ] ], Weights := [ 1, 1, 1, 2, 2 ], Epimorphism := [ a, b, c, d ] -> [ g1, g2*g3, g2, g3 ] )
To avoid repeated extensions of a weighted nilpotent quotient system the largest known quotient system is stored as an attribute of the invariantly L-presented group. For non-invariantly L-presented groups (or groups which are not known to be invariantly L-presented) the known epimorphisms onto the nilpotent quotients are stored as an attribute.
‣ NilpotentQuotientSystem( lpgroup ) | ( attribute ) |
stores the largest known weighted nilpotent quotient system of an invariantly L-presented group.
gap> G := ExamplesOfLPresentations( 1 );; gap> NilpotentQuotient( G, 5 ); Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] gap> NilpotentQuotientSystem( G ); rec( Lpres := <L-presented group on the generators [ a, b, c, d ]>, Pccol := <<from the left collector with 10 generators>>, Imgs := [ 1, [ 2, 1, 3, 1 ], 2, 3 ], Definitions := [ 1, 3, 4, [ 2, 1 ], [ 3, 1 ], [ 4, 2 ], [ 4, 3 ], [ 7, 1 ], [ 8, 2 ], [ 8, 3 ] ], Weights := [ 1, 1, 1, 2, 2, 3, 3, 4, 5, 5 ], Epimorphism := [ a, b, c, d ] -> [ g1, g2*g3, g2, g3 ] ) gap> NilpotencyClassOfGroup( PcpGroupByCollectorNC( last.Pccol ) ); 5
‣ NilpotentQuotients( lpgroup ) | ( attribute ) |
stores all known epimorphisms onto the nilpotent quotients of lpgroup. The nilpotent quotients are accessible by the operation Range (Reference: Range of a general mapping).
gap> G:=ExamplesOfLPresentations( 3 );; gap> HasIsInvariantLPresentation( G ); false gap> NilpotentQuotient( G, 3 ); Pcp-group with orders [ 0, 2, 2, 2 ] gap> NilpotentQuotients( G ); [ [ a, t, u ] -> [ g2, g1, g2 ], [ a, t, u ] -> [ g2, g1, g2 ], [ a, t, u ] -> [ g2, g1, g2 ] ] gap> Range( last[2] ); Pcp-group with orders [ 0, 2, 2 ]
The underlying invariant L-presentation has stored its largest weighted nilpotent quotient system as an attribute.
gap> NilpotentQuotientSystem( UnderlyingInvariantLPresentation( G ) ); rec( Lpres := <L-presented group on the generators [ a, t, u ]>, Pccol := <<from the left collector with 9 generators>>, Imgs := [ 1, 2, 3 ], Definitions := [ 1, 2, 3, [ 2, 1 ], [ 3, 2 ], [ 4, 1 ], [ 4, 2 ], [ 5, 2 ], [ 5, 3 ] ], Weights := [ 1, 1, 1, 2, 2, 3, 3, 3, 3 ], Epimorphism := [ a, t, u ] -> [ g1, g2, g3 ] )
To get some information about the progress of the algorithm, one can use the info class InfoLPRES (3.5-1).
‣ InfoLPRES | ( info class ) |
is the info class of the lpres-package. If the info-level is \(1\), the info-class gives further information on the progress of the nilpotent quotient algorithm for L-presented groups. The info-level \(2\) also includes some information on the runtime of our algorithm while the info-level \(3\) is mainly used for debugging-purposes. An example of such a session for the Grigorchuk group is shown below:
gap> SetInfoLevel( InfoLPRES, 1 );; gap> G:=ExamplesOfLPresentations( 1 ); #I The Grigorchuk group on 4 generators <L-presented group on the generators [ a, b, c, d ]> gap> NilpotentQuotient( G, 3 ); #I Class 1: 3 generators with relative orders: [ 2, 2, 2 ] #I Class 2: 2 generators with relative orders: [ 2, 2 ] #I Class 3: 2 generators with relative orders: [ 2, 2 ] Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2 ] gap> SetInfoLevel( InfoLPRES, 2 ); gap> NilpotentQuotient( G, 5 ); #I Time spent for spinning algo: 0:00:00.004 #I Class 4: 1 generators with relative orders: [ 2 ] #I Runtime for this step 0:00:00.028 #I Time spent for spinning algo: 0:00:00.008 #I Class 5: 2 generators with relative orders: [ 2, 2 ] #I Runtime for this step 0:00:00.036 Pcp-group with orders [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
‣ InfoLPRES_MAX_GENS | ( global variable ) |
this global variable sets the limit of generators whose relative order will be shown on each step of the nilpotent quotient algorithm, if the info-level of InfoLPRES (3.5-1) is positive.
generated by GAPDoc2HTML