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 σ is the homomorphism of the free group over {a,b,c,d} which is induced by a↦ c^a, b↦ d, c↦ b, and d↦ c. Hence, the infinitely many relators of this recursive presentation can be described in finite terms using powers of the endomorphism σ.

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 Φ^* denotes the free monoid generated by a set of free group endomorphisms Φ. 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/γ_c+1(G). Therefore, a nilpotent quotient algorithm can be used to determine the abelian invariants of the lower central series sections γ_c(G)/γ_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