[Up] [Previous] [Next] [Index]

2 An Introduction to L-presented groups

Sections

  1. Creating an L-presented group
  2. The underlying free group
  3. Accessing an L-presentation
  4. Attributes and properties of L-presented groups
  5. Methods for L-presented groups

Let S be an alphabet, Q and R be subsets of the free group FS over this alphabet, and Phi be a set of free group endomorphisms varphicolonFStoFS. An L-presentation is a quadruple (S,Q,Phi,R) and it is called finite if the sets S, Q, Phi, and R are finite. A (finite) L-presentation (S,Q,Phi,R) defines the (finitely) L-presented group

G=leftlangleS left|  QcupbigcupvarphiinPhi^* R^varphiright.rightrangle

where Phi^* denotes the free monoid generated by Phi; that is, the closure of Phicup{id} under composition.

The elements in Q are the fixed relators and the elements in R are the iterated relators of the L-presentation (S,Q,Phi,R). An L-presentation of the form (S,emptyset,Phi,R) is an ascending L-presentation and it is an invariant L-presentation if the normal subgroup

K=leftlangleQcupbigcupvarphiinPhi^* R^varphirightrangleF_S

is varphi-invariant for each varphiinPhi; that is, if K satisfies K^varphisubsetK for each varphiinPhi. Note that every ascending L-presentation is invariant and for each L-presentation (S,Q,Phi,R) there is a unique underlying ascending L-presentation (S,emptyset,Phi,R) which is invariant. In general it is not decidable whether or not a given L-presentation is invariant as this would require a solution to the word-problem.

In the remainder of this manual, an L-presented group is always finitely L-presented.

2.1 Creating an L-presented group

The construction of an L-presented group is similar to the construction of a finitely presented group (see Chapter Creating Finitely Presented Groups of the GAP Reference manual for further details).

  • LPresentedGroup( F, frels, endos, irels ) F

    returns the GAP object of an L-presented group with the underlying free group F, the fixed relators frels, the set of endomorphisms endos, and the iterated relators irels. The input variables frels and irels need to be finite subsets of the underlying free group F and endos needs to be a finite list of homomorphisms FtoF.

    For example, the Grigorchuk group,

    Biglanglea,b,c,d Big| a2,b2,c2,d2,bcd,[d,da]sigma^n, [d,dacaca]sigma^n,(ninN0) Bigrangle,

    can be constructed as follows.

    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> frels:=[ a^2, b^2, c^2, d^2, b*c*d ];;
    gap> endos:=[ GroupHomomorphismByImagesNC( F, F, [ a, b, c, d ], [ c^a, d, b, c ]) ];;
    gap> irels:=[ Comm( d, d^a ), Comm( d, d^(a*c*a*c*a) ) ];;
    gap> G:=LPresentedGroup( F, frels, endos, irels );
    <L-presented group on the generators [ a, b, c, d ]>
    

    There are various examples of finitely L-presented groups available in the library of the NQL-package.

  • ExamplesOfLPresentations( n ) F

    returns some well-known examples of finitely L-presented groups. The input of this function needs to be a positive integer at most 10.

    n=1 The Grigorchuk group on 4 generators; cf. Grigorchuk80, Lysenok85, and Bartholdi03, Theorem 4.6,

    n=2 the Grigorchuk group on 3 generators; cf. Grigorchuk80, Lysenok85, and Bartholdi03, Theorem 4.6,

    n=3 the lamplighter group Z2wrZ; cf. Bartholdi03, Theorem 4.1,

    n=4 the Brunner-Sidki-Vieira group; cf. BrunnerVieiraSidki99 and Bartholdi03, Theorem 4.4,

    n=5 the Grigorchuk supergroup; cf. BartholdiGrigorchuk02 and Bartholdi03, Theorem 4.6,

    n=6 the Fabrykowski-Gupta group; cf. FabrykowskiGupta85 and BEH07,

    n=7 the Gupta-Sidki group; cf. Sidki87 and BEH07,

    n=8 an index-3 subgroup of the Gupta-Sidki group

    n=9 the Basilica group; cf. GrigorchukZuk02 and BartholdiVirag05,

    n=10 Baumslag's finitely generated, infinitely related group with a trivial multiplier; cf. Baumslag71.

    Furthermore, every free group in a variety of groups satisfying finitely many identities is finitely L-presented. Some of these groups are available from the NQL-package using the following operations; for further details we refer to the diploma thesis H08.

  • FreeEngelGroup( n, num ) O

    returns an L-presentation for the free n-Engel group on num generators; that is, the free group in the variety of num-generated groups satisfying the n-Engel identity.

  • FreeBurnsideGroup( exp, num) O

    returns an L-presentation for the free Burnside group on num generators with exponent exp; that is, the free group in the variety of num-generated groups with exponent exp.

  • FreeNilpotentGroup( c, num ) O

    returns an L-presentation for the free nilpotent group of class c on n generators; that is, the free group in the variety of num-generated, nilpotent groups with nilpotency class c.

  • GeneralizedFabrykowskiGuptaLpGroup( n ) O

    returns an L-presentation for the n-th generalized Fabrykowski-Gupta group as constructed in BEH07.

  • LamplighterGroup( fil, int) C
  • LamplighterGroup( fil, PcGroup) C

    returns a finite L-presentation for the lamplighter group on int lamp states in the first case, if fil is the filter IsLpGroup. In the second case, the group PcGroup must be a finite cyclic group. Then the method returns a finite L-presentation for the lamplighter group on Size(PcGroup) lamp states; for details on the L-presentation see Bartholdi03.

    gap> LamplighterGroup( IsLpGroup, 2 );
    <L-presented group on the generators [ a, t, u ]>
    gap> LamplighterGroup( IsLpGroup, CyclicGroup(3) );
    <L-presented group on the generators [ a, t, u ]>
    

    2.2 The underlying free group

    An L-presented group is defined as an image of its underlying free group. Note that these are two different GAP objects. The elements of the L-presented group are represented by words in the underlying free group.

  • FreeGroupOfLpGroup( LpGroup ) A

    returns the underlying free group of the L-presented group LpGroup.

  • FreeGeneratorsOfLpGroup( LpGroup ) A

    returns the generators of the free group which underlies the L-presented group LpGroup.

  • GeneratorsOfGroup( LpGroup ) O

    returns the generators of the L-presented group LpGroup. These are the images of the generators of the underlying free group under the natural homomorphism.

  • UnderlyingElement( elm ) O

    returns the preimage of an L-presented group element elm in the underlying free group. More precisely, each element of an L-presented group is represented by an element in the free group. This method returns the corresponding element in the free group.

  • ElementOfLpGroup( fam, elm ) O

    returns the element in the L-presented group represented by the word elm on the generators of the underlying free group, if fam is the family of L-presented group elements.

    gap> F:=FreeGroup( 2 );;
    gap> G:=LPresentedGroup( F, [ F.1^2 ], [ IdentityMapping( F ) ], [ F.2 ] );;
    gap> FreeGroupOfLpGroup( G ) = F;
    true
    gap> GeneratorsOfGroup( G );
    [ f1, f2 ]
    gap> FreeGeneratorsOfLpGroup( G );
    [ f1, f2 ]
    gap> last = last2;
    false
    gap> UnderlyingElement( G.1 );
    f1
    gap> last in F;
    true
    gap> ElementOfLpGroup( ElementsFamily( FamilyObj( G ) ), last2 ) in G;
    true
    

    2.3 Accessing an L-presentation

    The fixed relators, the iterated relators, and the endomorphisms of an L-presented group are accessible with the following methods.

  • FixedRelatorsOfLpGroup( LpGroup ) A

    returns the fixed relators of the L-presented group LpGroup as elements of the underlying free group.

  • IteratedRelatorsOfLpGroup( LpGroup ) A

    returns the iterated relators of the L-presented group LpGroup as elements of the underlying free group.

  • EndomorphismsOfLpGroup( LpGroup ) A

    returns the endomorphisms of the L-presented group LpGroup as endomorphisms of the underlying free group.

    gap> F:=FreeGroup( 2 );;
    gap> G:=LPresentedGroup( F, [ F.1^2 ], [ IdentityMapping( F ) ], [ F.2 ] );
    <L-presented group on the generators [ f1, f2 ]>
    gap> FixedRelatorsOfLpGroup( G );
    [ f1^2 ]
    gap> IteratedRelatorsOfLpGroup( G );
    [ f2 ]
    gap> EndomorphismsOfLpGroup( G );
    [ IdentityMapping( <free group on the generators [ f1, f2 ]> ) ]
    

    2.4 Attributes and properties of L-presented groups

    For the method-selection of the nilpotent quotient algorithm, an L-presented group may have the following attributes and properties.

  • UnderlyingAscendingLPresentation( LpGroup ) A

    returns the underlying ascending L-presentation of LpGroup; that is, if LpGroup is finitely L-presented by (S,Q,Phi,R), the underlying ascending L-presentation is (S,emptyset,Phi,R).

  • UnderlyingInvariantLPresentation( LpGroup ) A

    attempts to compute a 'good' underlying invariant L-presentation for LpGroup; that is, if LpGroup is finitely L-presented by (S,Q,Phi,R), then this method seeks to find a subset Q'subseteqQ such that (S,Q',Phi,R) is an invariant L-presentation. Note that there is always the underlying ascending L-presentation (S,emptyset,Phi,R). However, for the efficiency of the nilpotent quotient algorithm it is important that the subset Q' is as big as possible.

    Since it is undecidable, in general, whether or not a given L-presentation is invariant, there is no algorithm which can determine the best possible underlying invariant L-presentation. The method implemented for this attribute tries to compute a 'good' invariant L-presentation and will return the underlying ascending L-presentation in the worst case.

    This attribute can be set manually using SetUnderlyingInvariantLPresentation. For instance, the Grigorchuk group

    Biglanglea,b,c,d Big| a2,b2,c2,d2,bcd,[d,da]sigma^n, [d,dacaca]sigma^n,(ninN0) Bigrangle,

    is invariantly L-presented and therefore, it should be constructed as follows

    gap> F:=FreeGroup( "a", "b", "c", "d" );;
    gap> AssignGeneratorVariables( F );
    #I  Assigned the global variables [ a, b, c, d ]
    gap> frels:=[ a^2, b^2, c^2, d^2, b*c*d ];;
    gap> endos:=[ GroupHomomorphismByImagesNC( F, F, [ a, b, c, d ], [ c^a, d, b, c ]) ];;
    gap> irels:=[ Comm( d, d^a ), Comm( d, d^(a*c*a*c*a) ) ];;
    gap> G:=LPresentedGroup( F, frels, endos, irels );
    <L-presented group on the generators [ a, b, c, d ]>
    gap> SetUnderlyingInvariantLPresentation( G, G );;
    

  • IsAscendingLPresentation( LpGroup ) P

    checks whether the L-presentation of LpGroup is ascending; that is, if the set of fixed relators is empty. This property is set automatically when creating an L-presented group with no fixed relators using the function LPresentedGroup.

  • IsInvariantLPresentation( LpGroup ) P

    attempts to check whether the L-presentation of LpGroup is invariant. In general, one cannot decide whether or not a given L-presentation is invariant. There are mainly two methods implemented for this property. The first method seeks to find a 'good' underlying invariant L-presentation using the operation UnderlyingInvariantLPresentation. If this latter L-presentation coincides with the L-presentation of LpGroup, then LpGroup is invariantly L-presented. If this method fails, then the second method uses the nilpotent quotient algorithm for L-presented groups which yields a necessary condition for an L-presented group to be invariantly L-presented. Note that the latter method may not terminate. For instance, both methods fail on Baumslag's finitely generated, infinitely related group with trivial multiplier returned by ExamplesOfLPresentations.

  • EmbeddingOfAscendingSubgroup( LpGroup ) A

    stores an embedding of an ascendingly L-presented subgroup of the L-presented group LpGroup. This attribute is set for ascending L-presentations only. In this case, the identity map of LpGroup is returned. This attribute is used in the FR-package which can construct various finitely L-presented groups. The embedding is useful for a nilpotent quotient algorithm of a non-invariantly L-presented group.

    2.5 Methods for L-presented groups

  • MappedWord( x, gens, imgs ) O

    returns the group element obtained from x by replacing each occurrence of a generator in gens by the corresponding element in the list imgs. The lists gens and imgs need to have the same length.

  • EpimorphismFromFpGroup( LpGroup, n ) O

    returns an epimorphism from a finitely presented group onto LpGroup. The finitely presented group is obtained from LpGroup by applying only words of length at most n in the endomorphisms of LpGroup to the iterated relators of LpGroup.

  • SplitExtensionByAutomorphismsLpGroup( LpGroup, H, auts) O

    returns an L-presentation for the split extension of LpGroup by an L-presented or by a finitely presented group H. The action of a generator of H on LpGroup is given by an automorphism in the list auts. Thus for each generator of H there must be an automorphism in the list auts.

    gap> F := FreeGroup( "a" );
    <free group on the generators [ a ]>
    gap> H := F / [ F.1^3 ];
    <fp group on the generators [ a ]>
    gap> U := ExamplesOfLPresentations( 8 );
    <L-presented group on the generators [ t, u, v ]>
    gap> aut:=GroupHomomorphismByImagesNC( U, U, [ U.1, U.2, U.3 ], [ U.2, U.3, U.1 ] );
    [ t, u, v ] -> [ u, v, t ]
    gap> SplitExtensionByAutomorphismsLpGroup( U, H, [ aut ] );
    <L-presented group on the generators [ t, u, v, a ]>
    

  • = ( elm1, elm2 ) O

    uses the operation NqEpimorphismNilpotentQuotient to compare the images of elm1 and elm2 in a nilpotent quotient of the group. The implemented method successively increases the class of the considered quotient until the images differ. Hence, this method may not terminate and it will only determine whether the elements elm1 and elm2 are different.

  • AsLpGroup( G ) O

    returns an ascending L-presentation for a finitely presented group G or for a free group G.

  • IsomorphismLpGroup( G ) O

    returns an isomorphism from a finitely presented group G or from a free group G to the L-presented group obtained from the method AsLpGroup.

  • Display( G ) O

    prints the L-presentation of G.

    gap> F:=FreeGroup( 2 );
    <free group on the generators [ f1, f2 ]>
    gap> G:=F/[ F.1^2, F.2^2, Comm( F.1, F.2 ) ];
    <fp group on the generators [ f1, f2 ]>
    gap> IsomorphismLpGroup( G );
    [ f1, f2 ] -> [ f1, f2 ]
    gap> Range(last);
    <L-presented group on the generators [ f1, f2 ]>
    gap> Display(last);
    generators = [ f1, f2 ]
    fixed relators = [ ]
    endomorphism = [
    IdentityMapping( <free group on the generators [ f1, f2 ]> ) ]
    iterated relators = [
    f1^2,
    f2^2,
    f1^-1*f2^-1*f1*f2 ]
    

    [Up] [Previous] [Next] [Index]

    NQL manual
    November 2008