Quelle  chap1.html   Sprache: HTML

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (lpres) - Chapter 1: The lpres package</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap1"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap0.html">[Previous Chapter]</a>    <a href="chap2.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap1_mj.html">[MathJax on]</a></p>
<p><a id="X86B8787287B59CA4" name="X86B8787287B59CA4"></a></p>
<div class="ChapSects"><a href="chap1.html#X86B8787287B59CA4">1 <span class="Heading">The <strong class="pkg">lpres</strong> package</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X7DFB63A97E67C0A1">1.1 <span class="Heading">Introduction</span></a>
</span>
</div>
</div>

<h3>1 <span class="Heading">The <strong class="pkg">lpres</strong> package</span></h3>

<p>This package was written by René Hartung in 2009; maintenance has been overtaken by Laurent Bartholdi, who translated the manual to <strong class="pkg">GAPDoc</strong>.</p>

<p><a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a></p>

<h4>1.1 <span class="Heading">Introduction</span></h4>

<p>In 1980, Grigorchuk <a href="chapBib.html#biBGrigorchuk80">[Gri80]</a> 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 <em>Grigorchuk group</em> 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 <a href="chapBib.html#biBGrigorchuk83">[Gri83]</a>) and was used in the construction of a finitely presented amenable group which is not elementary amenable (see <a href="chapBib.html#biBGrigorchuk98">[Gri98]</a>).</p>

<p>The Grigorchuk group is not finitely presentable (see <a href="chapBib.html#biBGrigorchuk99">[Gri99]</a>). However, in 1985, Igor Lysenok (see <a href="chapBib.html#biBLysenok85">[Lys85]</a>) determined the following recursive presentation for the Grigorchuk group:</p>

<p class="pcenter">\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,</p>

<p>where <span class="SimpleMath">σ</span> is the homomorphism of the free group over <span class="SimpleMath">{a,b,c,d}</span> which is induced by <span class="SimpleMath">a↦ c^a, b↦ d, c↦ b</span>, and <span class="SimpleMath">d↦ c</span>. Hence, the infinitely many relators of this recursive presentation can be described in finite terms using powers of the endomorphism <span class="SimpleMath">σ</span>.</p>

<p>In 2003, Bartholdi <a href="chapBib.html#biBBartholdi03">[Bar03]</a> introduced the notion of an <em>L-presentation</em> for presentations of this type; that is, a group presentation of the form</p>

<p class="pcenter">G=\left\langle S \left|  Q\cup \bigcup_{\varphi\in\Phi^*} R^\varphi\right.\right\rangle,</p>

<p>where <span class="SimpleMath">Φ^*</span> denotes the free monoid generated by a set of free group endomorphisms <span class="SimpleMath">Φ</span>. 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 <span class="SimpleMath">n</span>-Engel groups).</p>

<p>The <strong class="pkg">lpres</strong>-package defines new <strong class="pkg">GAP</strong> 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 <span class="SimpleMath">G</span> and a positive integer <span class="SimpleMath">c</span>. It computes a polycyclic presentation for the lower central series quotient <span class="SimpleMath">G/γ_c+1(G)</span>. Therefore, a nilpotent quotient algorithm can be used to determine the abelian invariants of the lower central series sections <span class="SimpleMath">γ_c(G)/γ_c+1(G)</span> and the largest nilpotent quotient of <span class="SimpleMath">G</span> if it exists.</p>

<p>Our nilpotent quotient algorithm generalizes Nickel's algorithm for finitely presented groups (see <a href="chapBib.html#biBNickel96">[Nic96]</a>) which is implemented in the <strong class="pkg">NQ</strong>-package; see <a href="chapBib.html#biBnq">[Nic03]</a>. In difference to the <strong class="pkg">NQ</strong>-package, the <strong class="pkg">lpres</strong>-package is implemented in <strong class="pkg">GAP</strong> only.</p>

<p>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.</p>

<p>A detailed description of our algorithm can be found in <a href="chapBib.html#biBBEH08">[BEH08]</a> or in the diploma thesis <a href="chapBib.html#biBH08">[Har08]</a>. Furthermore the <strong class="pkg">lpres</strong>-package includes the algorithms of <a href="chapBib.html#biBMR2678952">[Har10]</a> for approximating the Schur multiplier of finitely L-presented groups.</p>

<p>The <strong class="pkg">lpres</strong>-package also includes the Reidemeister-Schreier algorithm from <a href="chapBib.html#biBMR2876891">[Har12]</a>. L-presented groups were introduced as a tool to understand self-similar groups such as the Grigorchuk group. As such, <strong class="pkg">lpres</strong> works in close contact with the package <strong class="pkg">fr</strong>. See <a href="chapBib.html#biBMR3133711">[Har13]</a> for more on the relationships between L-presented groups and self-similar groups.</p>

<p>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.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap0.html">[Previous Chapter]</a>    <a href="chap2.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>