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

# 5 Subgroups of L-presented groups

### Sections

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

## 5.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.

• `Subgroup( `G`, `gens` ) F`

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

```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 ])
```

• `SubgroupLpGroupByCosetTable( `G`, `Tab` ) O`

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(<subgroup of L-presented group, no generators known>)
gap> U = K;
true
```

The generators of U can be computed with the Schreier-algorithm which is implemented in the method 'GeneratorsOfGroup'.

## 5.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 Har10. 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 Har10.

• `IndexInWholeGroup( `H` ) M`

attempts to compute the index of H in its parent group.

```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
```

• `Index( `H`, `I` ) M`

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)),
> Comm( d^(a*c), c^a), Comm( d, c^(a*c*a) ), Comm( d^(a*c*a), c) ] );;
gap> Index( K, KxK );
4
```

• `CosetTableInWholeGroup( `H` ) M`

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 ] ]
```

## 5.3 Technical details

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

• `NQL_TCSTART`

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

• `NQL_CosetEnumerator`

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.

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

NQL manual
September 2010