Goto Chapter: Top 1 2 3 4 5 6 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

1 The lpres package
 1.1 Introduction

1 The lpres package

This package was written by René Hartung in 2009; maintenance has been overtaken by Laurent Bartholdi, who translated the manual to GAPDoc.

1.1 Introduction

In 1980, Grigorchuk [Gri80] gave an example of an infinite, finitely generated torsion group which provided a first explicit counter-example to the General Burnside Problem. This counter-example is nowadays called the Grigorchuk group and was originally defined as a group of transformations of the unit interval which preserve the Lebesgue measure. Beside being a counter-example to the General Burnside Problem, the Grigorchuk group was a first example of a group with an intermediate growth function (see [Gri83]) and was used in the construction of a finitely presented amenable group which is not elementary amenable (see [Gri98]).

The Grigorchuk group is not finitely presentable (see [Gri99]). However, in 1985, Igor Lysenok (see [Lys85]) determined the following recursive presentation for the Grigorchuk group:

\[\langle a,b,c,d\mid a^2,b^2,c^2,d^2,bcd,[d,d^a]^{\sigma^n},[d,d^{acaca}]^{\sigma^n}, (n\inℕ)\rangle,\]

where \(\sigma\) is the homomorphism of the free group over \(\{a,b,c,d\}\) which is induced by \(a\mapsto c^a, b\mapsto d, c\mapsto b\), and \(d\mapsto c\). Hence, the infinitely many relators of this recursive presentation can be described in finite terms using powers of the endomorphism \(\sigma\).

In 2003, Bartholdi [Bar03] introduced the notion of an L-presentation for presentations of this type; that is, a group presentation of the form

\[G=\left\langle S \left| Q\cup \bigcup_{\varphi\in\Phi^*} R^\varphi\right.\right\rangle,\]

where \(\Phi^*\) denotes the free monoid generated by a set of free group endomorphisms \(\Phi\). He proved that various branch groups are finitely L-presented but not finitely presentable and that every free group in a variety of groups satisfying finitely many identities is finitely L-presented (e.g. the Free Burnside- and the Free \(n\)-Engel groups).

The lpres-package defines new GAP objects to work with finitely L-presented groups. The main part of the package is a nilpotent quotient algorithm for finitely L-presented groups; that is, an algorithm which takes as input a finitelyL-presented group \(G\) and a positive integer \(c\). It computes a polycyclic presentation for the lower central series quotient \(G/\gamma_{c+1}(G)\). Therefore, a nilpotent quotient algorithm can be used to determine the abelian invariants of the lower central series sections \(\gamma_c(G)/\gamma_{c+1}(G)\) and the largest nilpotent quotient of \(G\) if it exists.

Our nilpotent quotient algorithm generalizes Nickel's algorithm for finitely presented groups (see [Nic96]) which is implemented in the NQ-package; see [Nic03]. In difference to the NQ-package, the lpres-package is implemented in GAP only.

Since finite L-presentations generalize finite presentations, our algorithm also applies to finitely presented groups. It coincides with Nickel's algorithm in this special case.

A detailed description of our algorithm can be found in [BEH08] or in the diploma thesis [Har08]. Furthermore the lpres-package includes the algorithms of [Har10] for approximating the Schur multiplier of finitely L-presented groups.

The lpres-package also includes the Reidemeister-Schreier algorithm from [Har12]. L-presented groups were introduced as a tool to understand self-similar groups such as the Grigorchuk group. As such, lpres works in close contact with the package fr. See [Har13] for more on the relationships between L-presented groups and self-similar groups.

Finally, we note that we use the term "algorithm" somewhat loosely: many of the algorithms in this package are in fact semi-algorithms, guaranteed to give a correct answer but not guaranteed to terminate.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 Bib Ind

generated by GAPDoc2HTML