Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/doc/ref/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 18.9.2025 mit Größe 125 kB image not shown  

Impressum chap45.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/doc/ref/chap45.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 (ref) - Chapter 45: Polycyclic 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="chap45"  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="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</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="chap44.html">[Previous Chapter]</a>    <a href="chap46.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap45_mj.html">[MathJax on]</a></p>
<p><a id="X86007B0083F60470" name="X86007B0083F60470"></a></p>
<div class="ChapSects"><a href="chap45.html#X86007B0083F60470">45 <span class="Heading">Polycyclic Groups</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7F18A01785DBAC4E">45.1 <span class="Heading">Polycyclic Generating Systems</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X87F7E31879AFA06C">45.2 <span class="Heading">Computing a Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X84C3750C7A4EEC34">45.2-1 Pcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8635E61A7DB73BA6">45.2-2 IsPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7B561B1685CEC2AB">45.2-3 CanEasilyComputePcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7CAAD6D2838354D9">45.3 <span class="Heading">Defining a Pcgs Yourself</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7E139C3D80847D76">45.3-1 PcgsByPcSequence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X816C5E8E7F71C9D8">45.4 <span class="Heading">Elementary Operations for a Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7DD0DF677AC1CF10">45.4-1 RelativeOrders</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X80D526848427A5C6">45.4-2 IsFiniteOrdersPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X866C3A5382FF231A">45.4-3 IsPrimeOrdersPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X827A7B097A959579">45.4-4 PcSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7903702E8194EF29">45.4-5 GroupOfPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X878FB11887524E2C">45.4-6 OneOfPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X84243AA07DA5A827">45.5 <span class="Heading">Elementary Operations for a Pcgs and an Element</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7B941D4A7CAFCD73">45.5-1 RelativeOrderOfPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X78134914842E2F5F">45.5-2 ExponentOfPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X848DAEBF7DC448A5">45.5-3 ExponentsOfPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X829BCB267CDBC5C0">45.5-4 DepthOfPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7D47966479EA2890">45.5-5 LeadingExponentOfPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X87AF746B8328F5D0">45.5-6 PcElementByExponents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7F8BD7A87DB3933A">45.5-7 LinearCombinationPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8066B66D8069BAB4">45.5-8 SiftedPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7B52ADE7878A749A">45.5-9 CanonicalPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A94AA357DB2F86C">45.5-10 ReducedPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8702D76D8284CF3E">45.5-11 CleanedTailPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X830A0D037DBEAA97">45.5-12 HeadPcElementByNumber</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7EF61EA4822870E7">45.6 <span class="Heading">Exponents of Special Products</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X868D6DB07D349460">45.6-1 ExponentsConjugateLayer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X874F70697FE7B6DF">45.6-2 ExponentsOfRelativePower</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X78CAF32F864EF656">45.6-3 ExponentsOfConjugate</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X875689897DD0CAFC">45.6-4 ExponentsOfCommutator</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X8676397383093D1E">45.7 <span class="Heading">Subgroups of Polycyclic Groups – Induced Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X81FA878C854D63F8">45.7-1 IsInducedPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X83F6759184937F1B">45.7-2 InducedPcgsByPcSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X86308E80843BF9E5">45.7-3 ParentPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7F0EB20080590B23">45.7-4 InducedPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8332F1197DF6FEDE">45.7-5 InducedPcgsByGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7AF82BD079D811E5">45.7-6 InducedPcgsByPcSequenceAndGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X845FF8CA783D6CB3">45.7-7 LeadCoeffsIGS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X800287C680C5DEC3">45.7-8 ExtendedPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X817E16D67B31389B">45.7-9 SubgroupByPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X84068D2478C134C1">45.8 <span class="Heading">Subgroups of Polycyclic Groups – Canonical Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X80D122B986B42F80">45.8-1 IsCanonicalPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X816F6B4187032A10">45.8-2 CanonicalPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X8294F5EF81B7ABA0">45.9 <span class="Heading">Factor Groups of Polycyclic Groups – Modulo Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7FE689A37E559F66">45.9-1 ModuloPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X868207D77D09D915">45.9-2 IsModuloPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8027CC9878031D74">45.9-3 NumeratorOfModuloPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X87DBE2797D51B2F1">45.9-4 DenominatorOfModuloPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7E923519832F2D08"><code>45.9-5 \mod</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X876A41F97FBA7754">45.9-6 CorrespondingGeneratorsByModuloPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8480852A7D49BC3F">45.9-7 CanonicalPcgsByGeneratorsWithImages</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X8254C0F485F945BD">45.10 <span class="Heading">Factor Groups of Polycyclic Groups in their Own Representation</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X806C2D827E04ACF3">45.10-1 ProjectedPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X82F39CCE7C928D3A">45.10-2 ProjectedInducedPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X816813A078B93A6B">45.10-3 LiftedPcElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X83C60F1587577D65">45.10-4 LiftedInducedPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X83FE235E7B208EC0">45.11 <span class="Heading">Pcgs and Normal Series</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7E7E89C278DDE20D">45.11-1 IsPcgsElementaryAbelianSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X863A20B57EA37BAC">45.11-2 PcgsElementaryAbelianSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7BCC1E2A80544CC7">45.11-3 IndicesEANormalSteps</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7FCE308887F621FC">45.11-4 EANormalSeriesByPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X79675266796D7254">45.11-5 IsPcgsCentralSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X8187FCF483659E69">45.11-6 PcgsCentralSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7FB73FEB7BED5BFA">45.11-7 IndicesCentralNormalSteps</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X82266ADA86B2A689">45.11-8 CentralNormalSeriesByPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X786E60AF7B61BF9E">45.11-9 IsPcgsPCentralSeriesPGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X86F19DBD7D346E7F">45.11-10 PcgsPCentralSeriesPGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X863968F08509E7D4">45.11-11 IndicesPCentralNormalStepsPGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A92C9EA7BAF60CA">45.11-12 PCentralNormalSeriesByPcgsPGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7EA5BC3B7FE9D98D">45.11-13 IsPcgsChiefSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7E7326947EAE4BC9">45.11-14 PcgsChiefSeries</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7C05E84A78CA405E">45.11-15 IndicesChiefNormalSteps</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X83C5ABC587074B14">45.11-16 ChiefNormalSeriesByPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A954E3887189842">45.11-17 IndicesNormalSteps</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7947B0FB87F44042">45.11-18 NormalSeriesByPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7E624B4E8224DE2D">45.12 <span class="Heading">Sum and Intersection of Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7833DAAA7C07CFD7">45.12-1 SumFactorizationFunctionPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X83039CF97D27D819">45.13 <span class="Heading">Special Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7C8A82FA786AC021">45.13-1 IsSpecialPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X827EB7767BACD023">45.13-2 <span class="Heading">SpecialPcgs</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X82DC7CE682140588">45.13-3 LGWeights</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X824645C97E347EEE">45.13-4 LGLayers</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A655F4C7D9AE130">45.13-5 LGFirst</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7C3912F77B12C8B6">45.13-6 LGLength</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X814C35BF7C9A8DEF">45.13-7 IsInducedPcgsWrtSpecialPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7C14AE5C82FB0771">45.13-8 InducedPcgsWrtSpecialPcgs</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7E86EB517DC08809">45.14 <span class="Heading">Action on Subfactors Defined by a Pcgs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A9BB9D0817CA949">45.14-1 VectorSpaceByPcgsOfElementaryAbelianGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X81FC09DD7FC06C6E">45.14-2 LinearAction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7C2135B98732BBC3">45.14-3 LinearActionLayer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X79C2D6BF7DD69ED6">45.14-4 AffineAction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7E4CB1358524497B">45.14-5 AffineActionLayer</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7EEA8D638492F432">45.15 <span class="Heading">Orbit Stabilizer Methods for Polycyclic Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7CFCCF607A30B5EE">45.15-1 StabilizerPcgs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7A87E72F86813132">45.15-2 Pcgs_OrbitStabilizer</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X7A19DF1E7E841074">45.16 <span class="Heading">Operations which have Special Methods for Groups with Pcgs</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap45.html#X79DCCF6D80351859">45.17 <span class="Heading">Conjugacy Classes in Solvable Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X79593F667A68A21D">45.17-1 ClassesSolvableGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap45.html#X7B358D3B7E236973">45.17-2 CentralizerSizeLimitConsiderFunction</a></span>
</div></div>
</div>

<h3>45 <span class="Heading">Polycyclic Groups</span></h3>

<p>A group <var class="Arg">G</var> is <em>polycyclic</em> if there exists a subnormal series <span class="SimpleMath">G = C_1 > C_2 > ... > C_n > C_{n+1} = { 1 }</span> with cyclic factors. Such a series is called <em>pc series</em> of <var class="Arg">G</var>.</p>

<p>Every polycyclic group is solvable and every finite solvable group is polycyclic. However, there are infinite solvable groups which are not polycyclic.</p>

<p>In <strong class="pkg">GAP</strong> there exists a large number of methods for polycyclic groups which are based upon the polycyclic structure of these groups. These methods are usually very efficient, especially for groups which are given by a pc-presentation (see chapter <a href="chap46.html#X7EAD57C97EBF7E67"><span class="RefLink">46</span></a>), and can be applied to many types of groups. Hence <strong class="pkg">GAP</strong> tries to use them whenever possible, for example, for permutation groups and matrix groups over finite fields that are known to be polycyclic (the only exception is the representation as finitely presented group for which the polycyclic methods cannot be used in general).</p>

<p>At the current state of implementations the <strong class="pkg">GAP</strong> library contains methods to compute with finite polycyclic groups, while the <strong class="pkg">GAP</strong> package <strong class="pkg">Polycyclic</strong> by Bettina Eick and Werner Nickel allows also computations with infinite polycyclic groups which are given by a pc-presentation.</p>

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

<h4>45.1 <span class="Heading">Polycyclic Generating Systems</span></h4>

<p>Let <var class="Arg">G</var> be a polycyclic group with a pc series as above. A <em>polycyclic generating sequence</em> (<em>pcgs</em> for short) of <var class="Arg">G</var> is a sequence <span class="SimpleMath">P := (g_1, ..., g_n)</span> of elements of <var class="Arg">G</var> such that <span class="SimpleMath">C_i = ⟨ C_{i+1}, g_i ⟩</span> for <span class="SimpleMath">1 ≤ i ≤ n</span>. Note that each polycyclic group has a pcgs, but except for very small groups, a pcgs is not unique.</p>

<p>For each index <span class="SimpleMath">i</span> the subsequence of elements <span class="SimpleMath">(g_i, ..., g_n)</span> forms a pcgs of the subgroup <span class="SimpleMath">C_i</span>. In particular, these <em>tails</em> generate the subgroups of the pc series and hence we say that the pc series is <em>determined</em> by <span class="SimpleMath">P</span>.</p>

<p>Let <span class="SimpleMath">r_i</span> be the index of <span class="SimpleMath">C_{i+1}</span> in <span class="SimpleMath">C_i</span> which is either a finite positive number or infinity. Then <span class="SimpleMath">r_i</span> is the order of <span class="SimpleMath">g_i C_{i+1}</span> and we call the resulting list of indices the <em>relative orders</em> of the pcgs <var class="Arg">P</var>.</p>

<p>Moreover, with respect to a given pcgs <span class="SimpleMath">(g_1, ..., g_n)</span> each element <var class="Arg">g</var> of <var class="Arg">G</var> can be represented in a unique way as a product <span class="SimpleMath">g = g_1^{e_1} ⋅ g_2^{e_2} ⋯ g_n^{e_n}</span> with exponents <span class="SimpleMath">e_i ∈ {0, ..., r_i-1}</span>, if <span class="SimpleMath">r_i</span> is finite, and <span class="SimpleMath">e_i ∈ ℤ</span> otherwise. Words of this form are called <em>normal words</em> or <em>words in normal form</em>. Then the integer vector <span class="SimpleMath">[ e_1, ..., e_n ]</span> is called the <em>exponent vector</em> of the element <span class="SimpleMath">g</span>. Furthermore, the smallest index <span class="SimpleMath">k</span> such that <span class="SimpleMath">e_k ≠ 0</span> is called the <em>depth</em> of <var class="Arg">g</var> and <span class="SimpleMath">e_k</span> is the <em>leading exponent</em> of <var class="Arg">g</var>.</p>

<p>For many applications we have to assume that each of the relative orders <span class="SimpleMath">r_i</span> is either a prime or infinity. This is equivalent to saying that there are no trivial factors in the pc series and the finite factors of the pc series are maximal refined. Then we obtain that <span class="SimpleMath">r_i</span> is the order of <span class="SimpleMath">g C_{i+1}</span> for all elements <span class="SimpleMath">g</span> in <span class="SimpleMath">C_i ∖ C_{i+1}</span> and we call <span class="SimpleMath">r_i</span> the <em>relative order</em> of the element <span class="SimpleMath">g</span>.</p>

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

<h4>45.2 <span class="Heading">Computing a Pcgs</span></h4>

<p>Suppose a group <var class="Arg">G</var> is given; for example, let <var class="Arg">G</var> be a permutation or matrix group. Then we can ask <strong class="pkg">GAP</strong> to compute a pcgs of this group. If <var class="Arg">G</var> is not polycyclic, the result will be <code class="keyw">fail</code>.</p>

<p>Note that these methods can only be applied if <var class="Arg">G</var> is not given as finitely presented group. For finitely presented groups one can try to compute a pcgs via the polycyclic quotient methods, see <a href="chap47.html#X846072F779B51087"><span class="RefLink">47.14</span></a>.</p>

<p>Note also that a pcgs behaves like a list.</p>

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

<h5>45.2-1 Pcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Pcgs</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a pcgs for the group <var class="Arg">G</var>. If <var class="Arg">grp</var> is not polycyclic it returns <code class="keyw">fail</code> <em>and this result is not stored as attribute value</em>, in particular in this case the filter <code class="code">HasPcgs</code> is <em>not</em> set for <var class="Arg">G</var>!</p>

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

<h5>45.2-2 IsPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPcgs</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>The category of pcgs.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group((1,2,3,4),(1,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := Pcgs(G);</span>
Pcgs([ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPcgs( p );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">p[1];</span>
(3,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group((1,2,3,4,5),(1,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Pcgs(G);</span>
fail
</pre></div>

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

<h5>45.2-3 CanEasilyComputePcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanEasilyComputePcgs</code>( <var class="Arg">grp</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>This filter indicates whether it is possible to compute a pcgs for <var class="Arg">grp</var> cheaply. Clearly, <var class="Arg">grp</var> must be polycyclic in this case. However, not for every polycyclic group there is a method to compute a pcgs at low costs. This filter is used in the method selection mainly. Note that this filter may change its value from <code class="keyw">false</code> to <code class="keyw">true</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4),(1,2) );</span>
Group([ (1,2,3,4), (1,2) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">CanEasilyComputePcgs(G);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Pcgs(G);</span>
Pcgs([ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">CanEasilyComputePcgs(G);</span>
true
</pre></div>

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

<h4>45.3 <span class="Heading">Defining a Pcgs Yourself</span></h4>

<p>In a number of situations it might be useful to supply a pcgs to a group.</p>

<p>Note that the elementary operations for such a pcgs might be rather inefficient, since <strong class="pkg">GAP</strong> has to use generic methods in this case. It might be helpful to supply the relative orders of the self-defined pcgs as well by <code class="code">SetRelativeOrder</code>. See also <code class="func">IsPrimeOrdersPcgs</code> (<a href="chap45.html#X866C3A5382FF231A"><span class="RefLink">45.4-3</span></a>).</p>

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

<h5>45.3-1 PcgsByPcSequence</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcgsByPcSequence</code>( <var class="Arg">fam</var>, <var class="Arg">pcs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcgsByPcSequenceNC</code>( <var class="Arg">fam</var>, <var class="Arg">pcs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>constructs a pcgs for the elements family <var class="Arg">fam</var> from the elements in the list <var class="Arg">pcs</var>. The elements must lie in the family <var class="Arg">fam</var>. <code class="func">PcgsByPcSequence</code> and its <code class="code">NC</code> variant will always create a new pcgs which is not induced by any other pcgs (cf. <code class="func">InducedPcgsByPcSequence</code> (<a href="chap45.html#X83F6759184937F1B"><span class="RefLink">45.7-2</span></a>)).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">fam := FamilyObj( (1,2) );; # the family of permutations</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := PcgsByPcSequence( fam, [(1,2),(1,2,3)] );</span>
Pcgs([ (1,2), (1,2,3) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">RelativeOrders(p);</span>
[ 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ExponentsOfPcElement( p, (1,3,2) );</span>
[ 0, 2 ]
</pre></div>

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

<h4>45.4 <span class="Heading">Elementary Operations for a Pcgs</span></h4>

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

<h5>45.4-1 RelativeOrders</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RelativeOrders</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the list of relative orders of the pcgs <var class="Arg">pcgs</var>.</p>

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

<h5>45.4-2 IsFiniteOrdersPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFiniteOrdersPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>tests whether the relative orders of <var class="Arg">pcgs</var> are all finite.</p>

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

<h5>45.4-3 IsPrimeOrdersPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimeOrdersPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>tests whether the relative orders of <var class="Arg">pcgs</var> are prime numbers. Many algorithms require a pcgs to have this property. The operation <code class="func">IsomorphismRefinedPcGroup</code> (<a href="chap46.html#X7E6226597DFE5F8F"><span class="RefLink">46.4-8</span></a>) can be of help here.</p>

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

<h5>45.4-4 PcSeries</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcSeries</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the subnormal series determined by <var class="Arg">pcgs</var>.</p>

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

<h5>45.4-5 GroupOfPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GroupOfPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The group generated by <var class="Arg">pcgs</var>.</p>

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

<h5>45.4-6 OneOfPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OneOfPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The identity of the group generated by <var class="Arg">pcgs</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4),(1,2) );; p := Pcgs(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelativeOrders(p);</span>
[ 2, 3, 2, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFiniteOrdersPcgs(p);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimeOrdersPcgs(p);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">PcSeries(p);</span>
[ Group([ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ]),
  Group([ (2,4,3), (1,4)(2,3), (1,3)(2,4) ]),
  Group([ (1,4)(2,3), (1,3)(2,4) ]), Group([ (1,3)(2,4) ]), Group(())
 ]
</pre></div>

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

<h4>45.5 <span class="Heading">Elementary Operations for a Pcgs and an Element</span></h4>

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

<h5>45.5-1 RelativeOrderOfPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RelativeOrderOfPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The relative order of <var class="Arg">elm</var> with respect to the prime order pcgs <var class="Arg">pcgs</var>.</p>

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

<h5>45.5-2 ExponentOfPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentOfPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var>, <var class="Arg">pos</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the <var class="Arg">pos</var>-th exponent of <var class="Arg">elm</var> with respect to <var class="Arg">pcgs</var>.</p>

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

<h5>45.5-3 ExponentsOfPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentsOfPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var>[, <var class="Arg">posran</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the exponents of <var class="Arg">elm</var> with respect to <var class="Arg">pcgs</var>. The three argument version returns the exponents in the positions given in <var class="Arg">posran</var>.</p>

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

<h5>45.5-4 DepthOfPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DepthOfPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the depth of the element <var class="Arg">elm</var> with respect to <var class="Arg">pcgs</var>.</p>

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

<h5>45.5-5 LeadingExponentOfPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeadingExponentOfPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the leading exponent of <var class="Arg">elm</var> with respect to <var class="Arg">pcgs</var>.</p>

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

<h5>45.5-6 PcElementByExponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcElementByExponents</code>( <var class="Arg">pcgs</var>, <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcElementByExponentsNC</code>( <var class="Arg">pcgs</var>[, <var class="Arg">basisind</var>], <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the element corresponding to the exponent vector <var class="Arg">list</var> with respect to <var class="Arg">pcgs</var>. The exponents in <var class="Arg">list</var> must be in the range of permissible exponents for <var class="Arg">pcgs</var>. <em>It is not guaranteed that <code class="func">PcElementByExponents</code> will reduce the exponents modulo the relative orders</em>. (You should use the operation <code class="func">LinearCombinationPcgs</code> (<a href="chap45.html#X7F8BD7A87DB3933A"><span class="RefLink">45.5-7</span></a>) for this purpose.) The <code class="code">NC</code> version does not check that the lengths of the lists fit together and does not check the exponent range.</p>

<p>The three argument version gives exponents only w.r.t. the generators in <var class="Arg">pcgs</var> indexed by <var class="Arg">basisind</var>.</p>

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

<h5>45.5-7 LinearCombinationPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LinearCombinationPcgs</code>( <var class="Arg">pcgs</var>, <var class="Arg">list</var>[, <var class="Arg">one</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the product <span class="SimpleMath">∏_i <var class="Arg">pcgs</var>[i]^{<var class="Arg">list</var>[i]}</span>. In contrast to <code class="func">PcElementByExponents</code> (<a href="chap45.html#X87AF746B8328F5D0"><span class="RefLink">45.5-6</span></a>) this permits negative exponents. <var class="Arg">pcgs</var> might be a list of group elements. In this case, an appropriate identity element <var class="Arg">one</var> must be given. <var class="Arg">list</var> can be empty.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4),(1,2) );; P := Pcgs(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := PcElementByExponents(P, [0,1,1,1]);</span>
(1,2,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">ExponentsOfPcElement(P, g);</span>
[ 0, 1, 1, 1 ]
</pre></div>

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

<h5>45.5-8 SiftedPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SiftedPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>sifts <var class="Arg">elm</var> through <var class="Arg">pcgs</var>, reducing it if the depth is the same as the depth of one of the generators in <var class="Arg">pcgs</var>. Thus the identity is returned if <var class="Arg">elm</var> lies in the group generated by <var class="Arg">pcgs</var>. <var class="Arg">pcgs</var> must be an induced pcgs (see section <a href="chap45.html#X8676397383093D1E"><span class="RefLink">45.7</span></a>) and <var class="Arg">elm</var> must lie in the span of the parent of <var class="Arg">pcgs</var>.</p>

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

<h5>45.5-9 CanonicalPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalPcElement</code>( <var class="Arg">ipcgs</var>, <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>reduces <var class="Arg">elm</var> at the induces pcgs <var class="Arg">ipcgs</var> such that the exponents of the reduced result <var class="Arg">r</var> are zero at the depths for which there are generators in <var class="Arg">ipcgs</var>. Elements, whose quotient lies in the group generated by <var class="Arg">ipcgs</var> yield the same canonical element.</p>

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

<h5>45.5-10 ReducedPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>reduces the element <var class="Arg">x</var> by dividing off (from the left) a power of <var class="Arg">y</var> such that the leading coefficient of the result with respect to <var class="Arg">pcgs</var> becomes zero. The elements <var class="Arg">x</var> and <var class="Arg">y</var> therefore have to have the same depth.</p>

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

<h5>45.5-11 CleanedTailPcElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CleanedTailPcElement</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var>, <var class="Arg">dep</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns an element in the span of <var class="Arg">pcgs</var> whose exponents for indices <span class="SimpleMath">1</span> to <span class="SimpleMath"><var class="Arg">dep</var>-1</span> with respect to <var class="Arg">pcgs</var> are the same as those of <var class="Arg">elm</var>, the remaining exponents are undefined. This can be used to obtain more <q>simple</q> elements if only representatives in a factor are required, see <a href="chap45.html#X8294F5EF81B7ABA0"><span class="RefLink">45.9</span></a>.</p>

<p>The difference to <code class="func">HeadPcElementByNumber</code> (<a href="chap45.html#X830A0D037DBEAA97"><span class="RefLink">45.5-12</span></a>) is that this function is guaranteed to zero out trailing coefficients while <code class="func">CleanedTailPcElement</code> will only do this if it can be done cheaply.</p>

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

<h5>45.5-12 HeadPcElementByNumber</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HeadPcElementByNumber</code>( <var class="Arg">pcgs</var>, <var class="Arg">elm</var>, <var class="Arg">dep</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns an element in the span of <var class="Arg">pcgs</var> whose exponents for indices <span class="SimpleMath">1</span> to <var class="Arg">dep</var><span class="SimpleMath">-1</span> with respect to <var class="Arg">pcgs</var> are the same as those of <var class="Arg">elm</var>, the remaining exponents are zero. This can be used to obtain more <q>simple</q> elements if only representatives in a factor are required.</p>

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

<h4>45.6 <span class="Heading">Exponents of Special Products</span></h4>

<p>There are certain products of elements whose exponents are used often within algorithms, and which might be obtained more easily than by computing the product first and to obtain its exponents afterwards. The operations in this section provide a way to obtain such exponent vectors directly.</p>

<p>(The circumstances under which these operations give a speedup depend very much on the pcgs and the representation of elements that is used. So the following operations are not guaranteed to give a speedup in every case, however the default methods are not slower than to compute the exponents of a product and thus these operations should <em>always</em> be used if applicable.)</p>

<p>The second class are exponents of products of the generators which make up the pcgs. If the pcgs used is a family pcgs (see <code class="func">FamilyPcgs</code> (<a href="chap46.html#X79EDB35E82C99304"><span class="RefLink">46.1-1</span></a>)) then these exponents can be looked up and do not need to be computed.</p>

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

<h5>45.6-1 ExponentsConjugateLayer</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentsConjugateLayer</code>( <var class="Arg">mpcgs</var>, <var class="Arg">elm</var>, <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Computes the exponents of <var class="Arg">elm</var><code class="code">^</code><var class="Arg">e</var> with respect to <var class="Arg">mpcgs</var>; <var class="Arg">elm</var> must be in the span of <var class="Arg">mpcgs</var>, <var class="Arg">e</var> a pc element in the span of the parent pcgs of <var class="Arg">mpcgs</var> and <var class="Arg">mpcgs</var> must be the modulo pcgs for an abelian layer. (This is the usual case when acting on a chief factor). In this case if <var class="Arg">mpcgs</var> is induced by the family pcgs (see section <a href="chap45.html#X8676397383093D1E"><span class="RefLink">45.7</span></a>), the exponents can be computed directly by looking up exponents without having to compute in the group and having to collect a potential tail.</p>

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

<h5>45.6-2 ExponentsOfRelativePower</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentsOfRelativePower</code>( <var class="Arg">pcgs</var>, <var class="Arg">i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>For <span class="SimpleMath">p = <var class="Arg">pcgs</var>[<var class="Arg">i</var>]</span> this function returns the exponent vector with respect to <var class="Arg">pcgs</var> of the element <span class="SimpleMath">p^e</span> where <span class="SimpleMath">e</span> is the relative order of <var class="Arg">p</var> in <var class="Arg">pcgs</var>. For the family pcgs or pcgs induced by it (see section <a href="chap45.html#X8676397383093D1E"><span class="RefLink">45.7</span></a>), this might be faster than computing the element and computing its exponent vector.</p>

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

<h5>45.6-3 ExponentsOfConjugate</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentsOfConjugate</code>( <var class="Arg">pcgs</var>, <var class="Arg">i</var>, <var class="Arg">j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the exponents of <code class="code"><var class="Arg">pcgs</var>[<var class="Arg">i</var>]^<var class="Arg">pcgs</var>[<var class="Arg">j</var>]</code> with respect to <var class="Arg">pcgs</var>. For the family pcgs or pcgs induced by it (see section <a href="chap45.html#X8676397383093D1E"><span class="RefLink">45.7</span></a>), this might be faster than computing the element and computing its exponent vector.</p>

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

<h5>45.6-4 ExponentsOfCommutator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExponentsOfCommutator</code>( <var class="Arg">pcgs</var>, <var class="Arg">i</var>, <var class="Arg">j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the exponents of the commutator <code class="code">Comm( </code><span class="SimpleMath"><var class="Arg">pcgs</var>[<var class="Arg">i</var>], <var class="Arg">pcgs</var>[<var class="Arg">j</var>]</span><code class="code"> )</code> with respect to <var class="Arg">pcgs</var>. For the family pcgs or pcgs induced by it, (see section <a href="chap45.html#X8676397383093D1E"><span class="RefLink">45.7</span></a>), this might be faster than computing the element and computing its exponent vector.</p>

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

<h4>45.7 <span class="Heading">Subgroups of Polycyclic Groups – Induced Pcgs</span></h4>

<p>Let <var class="Arg">U</var> be a subgroup of <var class="Arg">G</var> and let <var class="Arg">P</var> be a pcgs of <var class="Arg">G</var> as above such that <var class="Arg">P</var> determines the subnormal series <span class="SimpleMath">G = C_1 > ... > C_{n+1} = { 1 }</span>. Then the series of subgroups <span class="SimpleMath">U ∩ C_i</span> is a subnormal series of <var class="Arg">U</var> with cyclic or trivial factors. Hence, if we choose an element <span class="SimpleMath">u_{i_j} ∈ (U ∩ C_{i_j}) ∖ (U ∩ C_{i_j+1})</span> whenever this factor is non-trivial, then we obtain a pcgs <span class="SimpleMath">Q = (u_{i_1}, ..., u_{i_m})</span> of <span class="SimpleMath">U</span>. We say that <span class="SimpleMath">Q</span> is an <em>induced pcgs</em> with respect to <var class="Arg">P</var>. The pcgs <var class="Arg">P</var> is the <em>parent pcgs</em> to the induced pcgs <var class="Arg">Q</var>.</p>

<p>Note that the pcgs <span class="SimpleMath">Q</span> is induced with respect to <var class="Arg">P</var> if and only if the matrix of exponent vectors of the elements <span class="SimpleMath">u_{i_j}</span> with respect to <var class="Arg">P</var> is in upper triangular form. Thus <span class="SimpleMath">Q</span> is not unique in general.</p>

<p>In particular, the elements of an induced pcgs do <em>not necessarily</em> have leading coefficient 1 relative to the inducing pcgs. The attribute <code class="func">LeadCoeffsIGS</code> (<a href="chap45.html#X845FF8CA783D6CB3"><span class="RefLink">45.7-7</span></a>) holds the leading coefficients in case they have to be renormed in an algorithm.</p>

<p>Each induced pcgs is a pcgs and hence allows all elementary operations for pcgs. On the other hand each pcgs could be transformed into an induced pcgs for the group defined by the pcgs, but note that an arbitrary pcgs is in general not an induced pcgs for technical reasons.</p>

<p>An induced pcgs is <q>compatible</q> with its parent, see <code class="func">ParentPcgs</code> (<a href="chap45.html#X86308E80843BF9E5"><span class="RefLink">45.7-3</span></a>).</p>

<p>In <a href="chapBib.html#biBSOGOS">[LNS84]</a> a <q>non-commutative Gauss</q> algorithm is described to compute an induced pcgs of a subgroup <var class="Arg">U</var> from a generating set of <var class="Arg">U</var>. For calling this in <strong class="pkg">GAP</strong>, see <a href="chap45.html#X7F0EB20080590B23"><span class="RefLink">45.7-4</span></a> to <a href="chap45.html#X800287C680C5DEC3"><span class="RefLink">45.7-8</span></a>.</p>

<p>To create a subgroup generated by an induced pcgs such that the induced pcgs gets stored automatically, use <code class="func">SubgroupByPcgs</code> (<a href="chap45.html#X817E16D67B31389B"><span class="RefLink">45.7-9</span></a>).</p>

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

<h5>45.7-1 IsInducedPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsInducedPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>The category of induced pcgs. This a subcategory of pcgs.</p>

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

<h5>45.7-2 InducedPcgsByPcSequence</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgsByPcSequence</code>( <var class="Arg">pcgs</var>, <var class="Arg">pcs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgsByPcSequenceNC</code>( <var class="Arg">pcgs</var>, <var class="Arg">pcs</var>[, <var class="Arg">depths</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">pcs</var> is a list of elements that form an induced pcgs with respect to <var class="Arg">pcgs</var> this operation returns an induced pcgs with these elements.</p>

<p>In the third version, the depths of <var class="Arg">pcs</var> with respect to <var class="Arg">pcgs</var> can be given (they are computed anew otherwise).</p>

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

<h5>45.7-3 ParentPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ParentPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the pcgs by which <var class="Arg">pcgs</var> was induced. If <var class="Arg">pcgs</var> was not induced, it simply returns <var class="Arg">pcgs</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4),(1,2) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Pcgs(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K := InducedPcgsByPcSequence( P, [(1,2,3,4),(1,3)(2,4)] );</span>
Pcgs([ (1,2,3,4), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">ParentPcgs( K );</span>
Pcgs([ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInducedPcgs( K );</span>
true
</pre></div>

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

<h5>45.7-4 InducedPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgs</code>( <var class="Arg">pcgs</var>, <var class="Arg">grp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>computes a pcgs for <var class="Arg">grp</var> which is induced by <var class="Arg">pcgs</var>. If <var class="Arg">pcgs</var> has a parent pcgs, then the result is induced with respect to this parent pcgs.</p>

<p><code class="func">InducedPcgs</code> is a wrapper function only. Therefore, methods for computing an induced pcgs should be installed for the operation <code class="code">InducedPcgsOp</code>.</p>

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

<h5>45.7-5 InducedPcgsByGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgsByGenerators</code>( <var class="Arg">pcgs</var>, <var class="Arg">gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgsByGeneratorsNC</code>( <var class="Arg">pcgs</var>, <var class="Arg">gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns an induced pcgs with respect to <var class="Arg">pcgs</var> for the subgroup generated by <var class="Arg">gens</var>.</p>

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

<h5>45.7-6 InducedPcgsByPcSequenceAndGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InducedPcgsByPcSequenceAndGenerators</code>( <var class="Arg">pcgs</var>, <var class="Arg">ind</var>, <var class="Arg">gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns an induced pcgs with respect to <var class="Arg">pcgs</var> of the subgroup generated by <var class="Arg">ind</var> and <var class="Arg">gens</var>. Here <var class="Arg">ind</var> must be an induced pcgs with respect to <var class="Arg">pcgs</var> (or a list of group elements that form such an igs) and it will be used as initial sequence for the computation.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4),(1,2) );;  P := Pcgs(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">I := InducedPcgsByGenerators( P, [(1,2,3,4)] );</span>
Pcgs([ (1,2,3,4), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">J := InducedPcgsByPcSequenceAndGenerators( P, I, [(1,2)] );</span>
Pcgs([ (1,2,3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ])
</pre></div>

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

<h5>45.7-7 LeadCoeffsIGS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeadCoeffsIGS</code>( <var class="Arg">igs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>This attribute is used to store leading coefficients with respect to the parent pcgs. the <var class="Arg">i</var>-th entry –if bound– is the leading exponent of the element of <var class="Arg">igs</var> that has depth <var class="Arg">i</var> in the parent. (It cannot be assigned to a component in the object created by <code class="func">InducedPcgsByPcSequenceNC</code> (<a href="chap45.html#X83F6759184937F1B"><span class="RefLink">45.7-2</span></a>) as the permutation group methods call it from within the postprocessing, before this postprocessing however no coefficients may be computed.)</p>

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

<h5>45.7-8 ExtendedPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtendedPcgs</code>( <var class="Arg">N</var>, <var class="Arg">gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>extends the pcgs <var class="Arg">N</var> (induced w.r.t. <var class="Arg">home</var>) to a new induced pcgs by prepending <var class="Arg">gens</var>. No checks are performed that this really yields an induced pcgs.</p>

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

<h5>45.7-9 SubgroupByPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubgroupByPcgs</code>( <var class="Arg">G</var>, <var class="Arg">pcgs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a subgroup of <var class="Arg">G</var> generated by the elements of <var class="Arg">pcgs</var>.</p>

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

<h4>45.8 <span class="Heading">Subgroups of Polycyclic Groups – Canonical Pcgs</span></h4>

<p>The induced pcgs <var class="Arg">Q</var> of <var class="Arg">U</var> is called <em>canonical</em> if the matrix of exponent vectors contains normed vectors only and above each leading entry in the matrix there are 0's only. The canonical pcgs of U with respect to P is unique and hence such pcgs can be used to compare subgroups.



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

<h5>45.8-1 IsCanonicalPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCanonicalPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>An induced pcgs is canonical if the matrix of the exponent vectors of the elements of <var class="Arg">pcgs</var> with respect to the <code class="func">ParentPcgs</code> (<a href="chap45.html#X86308E80843BF9E5"><span class="RefLink">45.7-3</span></a>) value of <var class="Arg">pcgs</var> is in Hermite normal form (see <a href="chapBib.html#biBSOGOS">[LNS84]</a>). While a subgroup can have various induced pcgs with respect to a parent pcgs a canonical pcgs is unique.</p>

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

<h5>45.8-2 CanonicalPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the canonical pcgs corresponding to the induced pcgs <var class="Arg">pcgs</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group((1,2,3,4),(5,6,7));</span>
Group([ (1,2,3,4), (5,6,7) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Pcgs(G);</span>
Pcgs([ (5,6,7), (1,2,3,4), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">I := InducedPcgsByPcSequence(P, [(5,6,7)*(1,3)(2,4),(1,3)(2,4)] );</span>
Pcgs([ (1,3)(2,4)(5,6,7), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalPcgs(I);</span>
Pcgs([ (5,6,7), (1,3)(2,4) ])
</pre></div>

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

<h4>45.9 <span class="Heading">Factor Groups of Polycyclic Groups – Modulo Pcgs</span></h4>

<p>Let <var class="Arg">N</var> be a normal subgroup of <var class="Arg">G</var> such that <var class="Arg">G/N</var> is polycyclic with pcgs <span class="SimpleMath">(h_1 N, ..., h_r N)</span>. Then we call the sequence of preimages <span class="SimpleMath">(h_1, ... h_r)</span> a <em>modulo pcgs</em> of <var class="Arg">G/N</var>. <var class="Arg">G</var> is called the <em>numerator</em> of the modulo pcgs and <var class="Arg">N</var> is the <em>denominator</em> of the modulo pcgs.</p>

<p>Modulo pcgs are often used to facilitate efficient computations with factor groups, since they allow computations with factor groups without formally defining the factor group at all.</p>

<p>All elementary operations of pcgs, see Sections <a href="chap45.html#X816C5E8E7F71C9D8"><span class="RefLink">45.4</span></a> and <a href="chap45.html#X84243AA07DA5A827"><span class="RefLink">45.5</span></a>, apply to modulo pcgs as well. However, it is in general not possible to compute induced pcgs with respect to a modulo pcgs.</p>

<p>Two more elementary operations for modulo pcgs are <code class="func">NumeratorOfModuloPcgs</code> (<a href="chap45.html#X8027CC9878031D74"><span class="RefLink">45.9-3</span></a>) and <code class="func">DenominatorOfModuloPcgs</code> (<a href="chap45.html#X87DBE2797D51B2F1"><span class="RefLink">45.9-4</span></a>).</p>

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

<h5>45.9-1 ModuloPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ModuloPcgs</code>( <var class="Arg">G</var>, <var class="Arg">N</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a modulo pcgs for the factor <span class="SimpleMath"><var class="Arg">G</var>/<var class="Arg">N</var></span> which must be solvable, while <var class="Arg">N</var> may be non-solvable. <code class="func">ModuloPcgs</code> will return <em>a</em> pcgs for the factor, there is no guarantee that it will be <q>compatible</q> with any other pcgs. If this is required, the <code class="keyw">mod</code> operator must be used on induced pcgs, see <code class="func">\mod</code> (<a href="chap45.html#X7E923519832F2D08"><span class="RefLink">45.9-5</span></a>).</p>

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

<h5>45.9-2 IsModuloPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsModuloPcgs</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>The category of modulo pcgs. Note that each pcgs is a modulo pcgs for the trivial subgroup.</p>

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

<h5>45.9-3 NumeratorOfModuloPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumeratorOfModuloPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a generating set for the numerator of the modulo pcgs <var class="Arg">pcgs</var>.</p>

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

<h5>45.9-4 DenominatorOfModuloPcgs</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DenominatorOfModuloPcgs</code>( <var class="Arg">pcgs</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a generating set for the denominator of the modulo pcgs <var class="Arg">pcgs</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group( (1,2,3,4,5),(1,2) );</span>
Group([ (1,2,3,4,5), (1,2) ])
--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.91 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.