Goto Chapter: Top 1 2 3 4 5 6 Bib Ind

4 Subgroups of L-presented groups

As shown in [Har11] it is possible to deal with finite index subgroups of L-presented groups algorithmically. The lpres-package provides straightforward methods to deal with these subgroups.

The Reidemeister-Schreier algorithm from [Har12] is implemented, and computes presentations for such subgroups.

4.1 Creating a subgroup of an L-presented group

There are two ways of defining subgroups of finite index of an lpgroup. The first is to define the subgroup by its generators while the second defines the subgroup by a coset-table. Generators of subgroup of the latter type can be computed with the usual Schreier-algorithm.

4.1-1 Subgroup
 ‣ Subgroup( G, gens ) ( function )

creates the subgroup U of G generated by gens. The Parent value of U will be G.

For example, the branching subgroup of the Grigorchuk group can be defined as follows, and a presentation can be computed using IsomorphismLpGroup (2.6-4):

gap> G := ExamplesOfLPresentations(1);;
gap> a := G.1;; b := G.2;; c := G.3;; d := G.4;;
gap> K := Subgroup( G, [ Comm( a, b ), Comm( b^a, d ), Comm( b, d^a ) ] );
Group([ a^-1*b^-1*a*b, b^-1*a^-1*d^-1*a*b*a^-1*d*a, a^-1*b^-1*a*d^-1*a^-1*b*a*d ])
gap> iso := IsomorphismLpGroup(K);
[ a^-1*b^-1*a*b, a^-1*b^-1*a*d^-1*a^-1*b*a*d, b^-1*a^-1*d^-1*a*b*a^-1*d*a ] ->
[ x1^-1*x13^-1*x12*x3, x1^-1*x13^-1*x12*x8^-1*x22^-1*x23*x24*x11, x3^-1*x12^-1*x18^-1*x29*x21*x1 ]
gap> Range(iso);
<LpGroup with 98 generators>


4.1-2 SubgroupLpGroupByCosetTable
 ‣ SubgroupLpGroupByCosetTable( G, Tab ) ( operation )

creates the subgroup U of G which is represented by the coset-table Tab.

For instance, the branching subgroup of the Grigorchuk group can be defined by the following coset-table:

gap> Tab := [ [ 2, 1, 6, 9, 10, 3, 11, 12, 4, 5, 7, 8, 15, 16, 13, 14 ],
[ 2, 1, 6, 9, 10, 3, 11, 12, 4, 5, 7, 8, 15, 16, 13, 14 ],
[ 3, 6, 1, 5, 4, 2, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15 ],
[ 3, 6, 1, 5, 4, 2, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15 ],
[ 4, 7, 5, 1, 3, 8, 2, 6, 13, 14, 15, 16, 9, 10, 11, 12 ],
[ 4, 7, 5, 1, 3, 8, 2, 6, 13, 14, 15, 16, 9, 10, 11, 12 ],
[ 5, 8, 4, 3, 1, 7, 6, 2, 14, 13, 16, 15, 10, 9, 12, 11 ],
[ 5, 8, 4, 3, 1, 7, 6, 2, 14, 13, 16, 15, 10, 9, 12, 11 ] ]
gap> U := SubgroupLpGroupByCosetTable( G, Tab );
Group(<A>subgroup of L-presented group, no generators known</A>)
gap> U = K;
true


The generators of U can be computed with the Schreier-algorithm which is implemented in the method GeneratorsOfGroup (Reference: GeneratorsOfGroup).

4.2 Computing the index of finite-index subgroups

In principle, it is possible to compute the index of a finite index subgroup of an lpgroup [Har11]. The method reduces the case to certain finitely presented groups by applying only finitely many endomorphisms to the iterated relations. It then uses coset enumeration for finitely presented groups to compute an upper bound on the index of the subgroup. If the coset enumeration for finitely presented groups terminated, the method attempts to prove that the upper bound is sharp. For further details we refer to [Har11].

4.2-1 IndexInWholeGroup
 ‣ IndexInWholeGroup( H ) ( method )
 ‣ FactorCosetAction( G, H ) ( method )

The first command attempts to compute the index of H in its parent group. The second one gives the permutation action of G on the right cosets of H.

gap> G := ExamplesOfLPresentations(1);;
gap> a := G.1;; b := G.2;; c := G.3;; d := G.4;;
gap> K := Subgroup( G, [ Comm(a,b), Comm( b, d^a ), Comm( b^a, d )] );;
gap> IndexInWholeGroup( K );
16
gap> FactorCosetAction( G, K );
[ a, b, c, d ] -> [ (1,2)(3,6)(4,9)(5,10)(7,11)(8,12)(13,15)(14,16),
(1,3)(2,6)(4,5)(7,8)(9,10)(11,12)(13,14)(15,16), (1,4)(2,7)(3,5)(6,8)(9,13)(10,14)(11,15)(12,16),
(1,5)(2,8)(3,4)(6,7)(9,14)(10,13)(11,16)(12,15) ]


4.2-2 Index
 ‣ Index( H, I ) ( method )

attempts to compute the index of I in the subgroup H. The subgroup I must be contained in H.

gap> G := ExamplesOfLPresentations(1);;
gap> a := G.1;; b := G.2;; c := G.3;; d := G.4;;
gap> K := Subgroup( G, [ Comm(a,b), Comm( b, d^a ), Comm( b^a, d )] );;
gap> KxK := Subgroup( G, [ Comm(b,d^a), Comm(b^a,d), Comm(d^a,c^(a*c)),
</A> Comm( d^(a*c), c^a), Comm( d, c^(a*c*a) ), Comm( d^(a*c*a), c) ] );;
gap> Index( K, KxK );
4


4.2-3 CosetTableInWholeGroup
 ‣ CosetTableInWholeGroup( H ) ( method )

computes a coset-table for the subgroup H in its parent group.

gap> CosetTableInWholeGroup( K );
[ [ 2, 1, 6, 9, 10, 3, 11, 12, 4, 5, 7, 8, 15, 16, 13, 14 ],
[ 2, 1, 6, 9, 10, 3, 11, 12, 4, 5, 7, 8, 15, 16, 13, 14 ],
[ 3, 6, 1, 5, 4, 2, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15 ],
[ 3, 6, 1, 5, 4, 2, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15 ],
[ 4, 7, 5, 1, 3, 8, 2, 6, 13, 14, 15, 16, 9, 10, 11, 12 ],
[ 4, 7, 5, 1, 3, 8, 2, 6, 13, 14, 15, 16, 9, 10, 11, 12 ],
[ 5, 8, 4, 3, 1, 7, 6, 2, 14, 13, 16, 15, 10, 9, 12, 11 ],
[ 5, 8, 4, 3, 1, 7, 6, 2, 14, 13, 16, 15, 10, 9, 12, 11 ] ]


4.3 Technical details

For performance issues the following global variables can be used to modify the behaviour of the coset enumeration:

4.3-1 LPRES_TCSTART
 ‣ LPRES_TCSTART ( global variable )

defines the maximal word-length of endomorphisms in the free monoid which are applied to the iterated relations.

4.3-2 LPRES_CosetEnumerator
 ‣ LPRES_CosetEnumerator ( global variable )

defines the coset enumeration process used for finitely presented groups. It should be a function which take as input a subgroup h of a finitely presented group and it computes a coset table in the whole group. The default uses the following method of the ACE-package

function ( h )
local  f, rels, gens;
f := FreeGeneratorsOfFpGroup( Parent( h ) );
rels := RelatorsOfFpGroup( Parent( h ) );
gens := List( GeneratorsOfGroup( h ), UnderlyingElement );
return ACECosetTable( f, rels, gens : silent := true,
hard := true,
max := 10 ^ 8,
Wo := 10 ^ 8 );


If the ACE-package is not available, the library coset enumeration process is used.

Goto Chapter: Top 1 2 3 4 5 6 Bib Ind

generated by GAPDoc2HTML