In 1980, Grigorchuk Grigorchuk80 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 Grigorchuk83) and was used in the construction of a finitely presented amenable group which is not elementary amenable (see Grigorchuk98).
The Grigorchuk group is not finitely presentable (see Grigorchuk99). However, in 1985, Igor Lysenok (see Lysenok85) determined the following recursive presentation for the Grigorchuk group:
langlea,b,c,dmida2,b2,c2,d2,bcd,[d,da]sigma^n,[d,dacaca] sigma^n, (ninN)rangle, where sigma is the homomorphism of the free group over {a,b,c,d} which is induced by amapstoca, bmapstod, cmapstob, and dmapstoc. Hence, the infinitely many relators of this recursive presentation can be described in finite terms using powers of the endomorphism sigma.
In 2003, Bartholdi Bartholdi03 introduced the notion of an L-presentation for presentations of this type; that is, a group presentation of the form
G=leftlangleS left| QcupbigcupvarphiinPhi^* R^varphiright.rightrangle, 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 NQL-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/gammac+1(G). Therefore, a nilpotent quotient algorithm can be used to determine the abelian invariants of the lower central series sections gammac(G)/gammac+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 Nickel96) which is implemented in the NQ-package; see nq. In difference to the NQ-package, the NQL-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.
Our algorithm can be readily modified to determine the p-quotients of a finitely L-presented group. An implementation is planned for future expansions of the package.
A detailed description of our algorithm can be found in BEH07 or in the diploma thesis H08 which is publicly available from the website http://www-public.tu-bs.de:8080/~y0019492/pub/index.html
NQL manual