Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/lpres/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 12.6.2024 mit Größe 14 kB image not shown  

Quelle  chap4.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/lpres/doc/chap4.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 4: Subgroups of L-presented groups</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="chap4"  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="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X874D64AA789F224E" name="X874D64AA789F224E"></a></p>
<div class="ChapSects"><a href="chap4.html#X874D64AA789F224E">4 <span class="Heading">Subgroups of L-presented groups</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86B9E4BD7F5D1610">4.1 <span class="Heading">Creating a subgroup of an L-presented group</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7C82AA387A42DCA0">4.1-1 Subgroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7FC6C908782DEA48">4.1-2 SubgroupLpGroupByCosetTable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7A4EB4E0819ACB91">4.2 <span class="Heading">Computing the index of finite-index subgroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8014135884DCC53E">4.2-1 IndexInWholeGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X83A0356F839C696F">4.2-2 Index</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X846EC8AB7803114D">4.2-3 CosetTableInWholeGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X87A9EC0A7DF04931">4.3 <span class="Heading">Technical details</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X823EECA37A8EC3FE">4.3-1 LPRES_TCSTART</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7C46A9B57BA4CA84">4.3-2 LPRES_CosetEnumerator</a></span>
</div></div>
</div>

<h3>4 <span class="Heading">Subgroups of L-presented groups</span></h3>

<p>As shown in <a href="chapBib.html#biBMR2864562">[Har11]</a> it is possible to deal with finite index subgroups of L-presented groups algorithmically. The <strong class="pkg">lpres</strong>-package provides straightforward methods to deal with these subgroups.</p>

<p>The Reidemeister-Schreier algorithm from <a href="chapBib.html#biBMR2876891">[Har12]</a> is implemented, and computes presentations for such subgroups.</p>

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

<h4>4.1 <span class="Heading">Creating a subgroup of an L-presented group</span></h4>

<p>There are two ways of defining subgroups of finite index of an <var class="Arg">lpgroup</var>. 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.</p>

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

<h5>4.1-1 Subgroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Subgroup</code>( <var class="Arg">G</var>, <var class="Arg">gens</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>creates the subgroup <var class="Arg">U</var> of <var class="Arg">G</var> generated by <var class="Arg">gens</var>. The Parent value of <var class="Arg">U</var> will be <var class="Arg">G</var>.</p>

<p>For example, the branching subgroup of the Grigorchuk group can be defined as follows, and a presentation can be computed using <code class="func">IsomorphismLpGroup</code> (<a href="chap2.html#X856F237B7BAC3BC8"><span class="RefLink">2.6-4</span></a>):</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := ExamplesOfLPresentations(1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := G.1;; b := G.2;; c := G.3;; d := G.4;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K := Subgroup( G, [ Comm( a, b ), Comm( b^a, d ), Comm( b, d^a ) ] );</span>
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 ])
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := IsomorphismLpGroup(K);</span>
[ a^-1*b^-1*a*b, a^-1*b^-1*a*d^-1*a^-1*b*a*d, b^-1*a^-1*d^-1*a*b*a^-1*d*a ] ->
[ x1^-1*x13^-1*x12*x3, x1^-1*x13^-1*x12*x8^-1*x22^-1*x23*x24*x11, x3^-1*x12^-1*x18^-1*x29*x21*x1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Range(iso);</span>
<LpGroup with 98 generators>
</pre></div>

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

<h5>4.1-2 SubgroupLpGroupByCosetTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubgroupLpGroupByCosetTable</code>( <var class="Arg">G</var>, <var class="Arg">Tab</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>creates the subgroup <var class="Arg">U</var> of <var class="Arg">G</var> which is represented by the coset-table <var class="Arg">Tab</var>.</p>

<p>For instance, the branching subgroup of the Grigorchuk group can be defined by the following coset-table:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Tab := [ [ 2, 1, 6, 9, 10, 3, 11, 12, 4, 5, 7, 8, 15, 16, 13, 14 ],</span>
  [ 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 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">U := SubgroupLpGroupByCosetTable( G, Tab );</span>
Group(<A>subgroup of L-presented group, no generators known</A>)
<span class="GAPprompt">gap></span> <span class="GAPinput">U = K;</span>
true
</pre></div>

<p>The generators of <var class="Arg">U</var> can be computed with the Schreier-algorithm which is implemented in the method <code class="func">GeneratorsOfGroup</code> (<a href="../../../doc/ref/chap39.html#X79C44528864044C5"><span class="RefLink">Reference: GeneratorsOfGroup</span></a>).</p>

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

<h4>4.2 <span class="Heading">Computing the index of finite-index subgroups</span></h4>

<p>In principle, it is possible to compute the index of a finite index subgroup of an <var class="Arg">lpgroup</var> <a href="chapBib.html#biBMR2864562">[Har11]</a>. 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 <a href="chapBib.html#biBMR2864562">[Har11]</a>.</p>

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

<h5>4.2-1 IndexInWholeGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IndexInWholeGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorCosetAction</code>( <var class="Arg">G</var>, <var class="Arg">H</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The first command attempts to compute the index of <var class="Arg">H</var> in its parent group. The second one gives the permutation action of <var class="Arg">G</var> on the right cosets of <var class="Arg">H</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := ExamplesOfLPresentations(1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := G.1;; b := G.2;; c := G.3;; d := G.4;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K := Subgroup( G, [ Comm(a,b), Comm( b, d^a ), Comm( b^a, d )] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IndexInWholeGroup( K );</span>
16
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorCosetAction( G, K );</span>
[ a, b, c, d ] -> [ (1,2)(3,6)(4,9)(5,10)(7,11)(8,12)(13,15)(14,16),
  (1,3)(2,6)(4,5)(7,8)(9,10)(11,12)(13,14)(15,16), (1,4)(2,7)(3,5)(6,8)(9,13)(10,14)(11,15)(12,16),
  (1,5)(2,8)(3,4)(6,7)(9,14)(10,13)(11,16)(12,15) ]
</pre></div>

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

<h5>4.2-2 Index</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Index</code>( <var class="Arg">H</var>, <var class="Arg">I</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>attempts to compute the index of <var class="Arg">I</var> in the subgroup <var class="Arg">H</var>. The subgroup <var class="Arg">I</var> must be contained in <var class="Arg">H</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := ExamplesOfLPresentations(1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := G.1;; b := G.2;; c := G.3;; d := G.4;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K := Subgroup( G, [ Comm(a,b), Comm( b, d^a ), Comm( b^a, d )] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">KxK := Subgroup( G, [ Comm(b,d^a), Comm(b^a,d), Comm(d^a,c^(a*c)),                         </span>
</A> Comm( d^(a*c), c^a), Comm( d, c^(a*c*a) ), Comm( d^(a*c*a), c) ] );;
<span class="GAPprompt">gap></span> <span class="GAPinput">Index( K, KxK );</span>
4
</pre></div>

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

<h5>4.2-3 CosetTableInWholeGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CosetTableInWholeGroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>computes a coset-table for the subgroup <var class="Arg">H</var> in its parent group.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">CosetTableInWholeGroup( K );</span>
[ [ 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 ] ]
</pre></div>

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

<h4>4.3 <span class="Heading">Technical details</span></h4>

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

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

<h5>4.3-1 LPRES_TCSTART</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LPRES_TCSTART</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>defines the maximal word-length of endomorphisms in the free monoid which are applied to the iterated relations.</p>

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

<h5>4.3-2 LPRES_CosetEnumerator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LPRES_CosetEnumerator</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>defines the coset enumeration process used for finitely presented groups. It should be a function which take as input a subgroup <var class="Arg">h</var> of a finitely presented group and it computes a coset table in the whole group. The default uses the following method of the <strong class="pkg">ACE</strong>-package</p>


<div class="example"><pre>
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 );
</pre></div>

<p>If the <strong class="pkg">ACE</strong>-package is not available, the library coset enumeration process is used.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.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>

100%


¤ Dauer der Verarbeitung: 0.2 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.