Quelle chap43_mj.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/doc/ref/chap43_mj.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>
<script type="text/javascript"
src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (ref) - Chapter 43: Permutation 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="chap43" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chap19_mj.html">19</a> <a href="chap20_mj.html">20</a> <a href="chap21_mj.html">21</a> <a href="chap22_mj.html">22</a> <a href="chap23_mj.html">23</a> <a href="chap24_mj.html">24</a> <a href="chap25_mj.html">25</a> <a href="chap26_mj.html">26</a> <a href="chap27_mj.html">27</a> <a href="chap28_mj.html">28</a> <a href="chap29_mj.html">29</a> <a href="chap30_mj.html">30</a> <a href="chap31_mj.html">31</a> <a href="chap32_mj.html">32</a> <a href="chap33_mj.html">33</a> <a href="chap34_mj.html">34</a> <a href="chap35_mj.html">35</a> <a href="chap36_mj.html">36</a> <a href="chap37_mj.html">37</a> <a href="chap38_mj.html">38</a> <a href="chap39_mj.html">39</a> <a href="chap40_mj.html">40</a> <a href="chap41_mj.html">41</a> <a href="chap42_mj.html">42</a> <a href="chap43_mj.html">43</a> <a href="chap44_mj.html">44</a> <a href="chap45_mj.html">45</a> <a href="chap46_mj.html">46</a> <a href="chap47_mj.html">47</a> <a href="chap48_mj.html">48</a> <a href="chap49_mj.html">49</a> <a href="chap50_mj.html">50</a> <a href="chap51_mj.html">51</a> <a href="chap52_mj.html">52</a> <a href="chap53_mj.html">53</a> <a href="chap54_mj.html">54</a> <a href="chap55_mj.html">55</a> <a href="chap56_mj.html">56</a> <a href="chap57_mj.html">57</a> <a href="chap58_mj.html">58</a> <a href="chap59_mj.html">59</a> <a href="chap60_mj.html">60</a> <a href="chap61_mj.html">61</a> <a href="chap62_mj.html">62</a> <a href="chap63_mj.html">63</a> <a href="chap64_mj.html">64</a> <a href="chap65_mj.html">65</a> <a href="chap66_mj.html">66</a> <a href="chap67_mj.html">67</a> <a href="chap68_mj.html">68</a> <a href="chap69_mj.html">69</a> <a href="chap70_mj.html">70</a> <a href="chap71_mj.html">71</a> <a href="chap72_mj.html">72</a> <a href="chap73_mj.html">73</a> <a href="chap74_mj.html">74</a> <a href="chap75_mj.html">75</a> <a href="chap76_mj.html">76</a> <a href="chap77_mj.html">77</a> <a href="chap78_mj.html">78</a> <a href="chap79_mj.html">79</a> <a href="chap80_mj.html">80</a> <a href="chap81_mj.html">81</a> <a href="chap82_mj.html">82</a> <a href="chap83_mj.html">83</a> <a href="chap84_mj.html">84</a> <a href="chap85_mj.html">85</a> <a href="chap86_mj.html">86</a> <a href="chap87_mj.html">87</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap42_mj.html">[Previous Chapter]</a> <a href="chap44_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap43.html">[MathJax off]</a></p>
<p><a id="X85ED46007CED6191" name="X85ED46007CED6191"></a></p>
<div class="ChapSects"><a href="chap43_mj.html#X85ED46007CED6191">43 <span class="Heading">Permutation Groups</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7F38777E7BBE12AE">43.1 <span class="Heading">IsPermGroup (Filter)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7879877482F59676">43.1-1 IsPermGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X85D769FF85545AAB">43.2 <span class="Heading">The Natural Action</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X84CFA16D858B00B8">43.2-1 OrbitPerms</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X81F98222818DA35B">43.2-2 OrbitsPerms</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7E468B64860D5604">43.3 <span class="Heading">Computing a Permutation Representation</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X80B7B1C783AA1567">43.3-1 IsomorphismPermGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8086628878AFD3EA">43.3-2 SmallerDegreePermutationRepresentation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X834208CD7C2956A3">43.4 <span class="Heading">Symmetric and Alternating Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8129BE59781478E1">43.4-1 IsNaturalSymmetricGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X85CA6AD17BE90C95">43.4-2 IsSymmetricGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8514BE9E79C608E0">43.4-3 IsAlternatingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7ED60F7E81F1B614">43.4-4 SymmetricParentGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X83F8D3B578A7BEEB">43.5 <span class="Heading">Primitive Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7E50211A7B92455F">43.5-1 ONanScottType</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7E89A46A86A3F4A2">43.5-2 SocleTypePrimitiveGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7FA58C3A8283F3BD">43.6 <span class="Heading">Stabilizer Chains</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7C2406B97E057196">43.7 <span class="Heading">Randomized Methods for Permutation Groups</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7C7EA55C80E457FA">43.8 <span class="Heading">Construction of Stabilizer Chains</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X80B5CF78829495C2">43.8-1 StabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X790C27B8783EDE68">43.8-2 StabChainOptions</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X87E1292E85A5D31C">43.8-3 DefaultStabChainOptions</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X86D64D2B81D58431">43.8-4 StabChainBaseStrongGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7BEC5F5A7851CAAB">43.8-5 MinimalStabChain</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X81D7FCE47AC7F942">43.9 <span class="Heading">Stabilizer Chain Records</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X7ECF8A4586346FD4">43.10 <span class="Heading">Operations for Stabilizer Chains</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7FBE6EB57EBE8B7D">43.10-1 BaseStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7D2A190D8308ED39">43.10-2 BaseOfGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7EF36DC78465026A">43.10-3 SizeStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8384170881B9B531">43.10-4 StrongGeneratorsStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X87F473777EFDE867">43.10-5 GroupStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X87FB6DED80692D3F">43.10-6 OrbitStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7AC8F165875906DE">43.10-7 IndicesStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7CF607BC82C2C202">43.10-8 ListStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7F40E52D7B0438BF">43.10-9 ElementsStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X780875477CD2A57D">43.10-10 IteratorStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X861062AE87ACF340">43.10-11 InverseRepresentative</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X79D2248C8787EAF2">43.10-12 SiftedPermutation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7B870C217D0B9997">43.10-13 MinimalElementCosetStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X87435B7884D9B353">43.10-14 LargestElementStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X809B2C3B7C5F77AB">43.10-15 ApproximateSuborbitsStabilizerPermGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X8188051F79E72A95">43.11 <span class="Heading">Low Level Routines to Modify and Create Stabilizer Chains</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X86B31E6A81AE5FCB">43.11-1 CopyStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7E167E557B567C6A">43.11-2 CopyOptionsDefaults</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X87FF64AB87BFC779">43.11-3 ChangeStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8778B4657D3FD97B">43.11-4 ExtendStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7E5E9F727D0B19D9">43.11-5 ReduceStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X85BF290D848C4091">43.11-6 RemoveStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X84E4906B86E5C089">43.11-7 EmptyStabChain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X80C7D2E87E6EE357">43.11-8 InsertTrivialStabilizer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7B47B379824F6150">43.11-9 IsFixedStabilizer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X8373007880EBF736">43.11-10 AddGeneratorsExtendSchreierTree</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X86C78160854C7F30">43.12 <span class="Heading">Backtrack</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7BE3F03C80BF8B08">43.12-1 SubgroupProperty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7EE7DDCC87C4BC31">43.12-2 ElementProperty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X7A2D046B83DD5F5F">43.12-3 TwoClosure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap43_mj.html#X861461AB7964DC64">43.12-4 InfoBckt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap43_mj.html#X78A68F5A80ADD1B6">43.13 <span class="Heading">Working with large degree permutation groups</span></a>
</span>
</div>
</div>
<h3>43 <span class="Heading">Permutation Groups</span></h3>
<p><a id="X7F38777E7BBE12AE" name="X7F38777E7BBE12AE"></a></p>
<h4>43.1 <span class="Heading">IsPermGroup (Filter)</span></h4>
<p><a id="X7879877482F59676" name="X7879877482F59676"></a></p>
<h5>43.1-1 IsPermGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPermGroup</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A permutation group is a group of permutations on a finite set <span class="SimpleMath">\(\Omega\)</span> of positive integers. <strong class="pkg">GAP</strong> does <em>not</em> require the user to specify the operation domain <span class="SimpleMath">\(\Omega\)</span> when a permutation group is defined.</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) ])
</pre></div>
<p>Permutation groups are groups and therefore all operations for groups (see Chapter <a href="chap39_mj.html#X8716635F7951801B"><span class="RefLink">39</span></a>) can be applied to them. In many cases special methods are installed for permutation groups that make computations more effective.</p>
<p><a id="X85D769FF85545AAB" name="X85D769FF85545AAB"></a></p>
<h4>43.2 <span class="Heading">The Natural Action</span></h4>
<p>The functions <code class="func">MovedPoints</code> (<a href="chap42_mj.html#X85E61B9C7A6B0CCA"><span class="RefLink">42.3-3</span></a>), <code class="func">NrMovedPoints</code> (<a href="chap42_mj.html#X85E7B1E28430F49E"><span class="RefLink">42.3-4</span></a>), <code class="func">LargestMovedPoint</code> (<a href="chap42_mj.html#X84AA603987C94AC0"><span class="RefLink">42.3-2</span></a>), and <code class="func">SmallestMovedPoint</code> (<a href="chap42_mj.html#X84EF0A697F7A87DC"><span class="RefLink">42.3-1</span></a>) are defined for arbitrary collections of permutations (see <a href="chap42_mj.html#X82C255E2821C0721"><span class="RefLink">42.3</span></a>), in particular they can be applied to permutation groups.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:= Group( (2,3,5,6), (2,3) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">MovedPoints( g ); NrMovedPoints( g );</span>
[ 2, 3, 5, 6 ]
4
<span class="GAPprompt">gap></span> <span class="GAPinput">LargestMovedPoint( g ); SmallestMovedPoint( g );</span>
6
2
</pre></div>
<p>The action of a permutation group on the positive integers is a group action (via the acting function <code class="func">OnPoints</code> (<a href="chap41_mj.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>)). Therefore all action functions can be applied (see the Chapter <a href="chap41_mj.html#X87115591851FB7F4"><span class="RefLink">41</span></a>), for example <code class="func">Orbit</code> (<a href="chap41_mj.html#X80E0234E7BD79409"><span class="RefLink">41.4-1</span></a>), <code class="func">Stabilizer</code> (<a href="chap41_mj.html#X86FB962786397E02"><span class="RefLink">41.5-2</span></a>), <code class="func">Blocks</code> (<a href="chap41_mj.html#X84FE699F85371643"><span class="RefLink">41.11-1</span></a>), <code class="func">IsTransitive</code> (<a href="chap41_mj.html#X79B15750851828CB"><span class="RefLink">41.10-1</span></a>), <code class="func">IsPrimitive</code> (<a href="chap41_mj.html#X84C19AD68247B760"><span class="RefLink">41.10-7</span></a>).</p>
<p>If one has a list of group generators and is interested in the moved points (see above) or orbits, it may be useful to avoid the explicit construction of the group for efficiency reasons. For the special case of the action of permutations on positive integers via <code class="code">^</code>, the functions <code class="func">OrbitPerms</code> (<a href="chap43_mj.html#X84CFA16D858B00B8"><span class="RefLink">43.2-1</span></a>) and <code class="func">OrbitsPerms</code> (<a href="chap43_mj.html#X81F98222818DA35B"><span class="RefLink">43.2-2</span></a>) are provided for this purpose.</p>
<p>Similarly, several functions concerning the natural action of permutation groups address stabilizer chains (see <a href="chap43_mj.html#X7FA58C3A8283F3BD"><span class="RefLink">43.6</span></a>) rather than permutation groups themselves, for example <code class="func">BaseStabChain</code> (<a href="chap43_mj.html#X7FBE6EB57EBE8B7D"><span class="RefLink">43.10-1</span></a>).</p>
<p><a id="X84CFA16D858B00B8" name="X84CFA16D858B00B8"></a></p>
<h5>43.2-1 OrbitPerms</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitPerms</code>( <var class="Arg">perms</var>, <var class="Arg">pnt</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the orbit of the positive integer <var class="Arg">pnt</var> under the group generated by the permutations in the list <var class="Arg">perms</var>.</p>
<p><a id="X81F98222818DA35B" name="X81F98222818DA35B"></a></p>
<h5>43.2-2 OrbitsPerms</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitsPerms</code>( <var class="Arg">perms</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the list of orbits of the positive integers in the list <var class="Arg">D</var> under the group generated by the permutations in the list <var class="Arg">perms</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">OrbitPerms( [ (1,2,3)(4,5), (3,6) ], 1 );</span>
[ 1, 2, 3, 6 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">OrbitsPerms( [ (1,2,3)(4,5), (3,6) ], [ 1 .. 6 ] );</span>
[ [ 1, 2, 3, 6 ], [ 4, 5 ] ]
</pre></div>
<p><a id="X7E468B64860D5604" name="X7E468B64860D5604"></a></p>
<h4>43.3 <span class="Heading">Computing a Permutation Representation</span></h4>
<p><a id="X80B7B1C783AA1567" name="X80B7B1C783AA1567"></a></p>
<h5>43.3-1 IsomorphismPermGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismPermGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns an isomorphism from the group <var class="Arg">G</var> onto a permutation group which is isomorphic to <var class="Arg">G</var>. The method will select a suitable permutation representation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=SmallGroup(24,12);</span>
<pc group of size 24 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso:=IsomorphismPermGroup(g);</span>
[ f1, f2, f3, f4 ] -> [ (2,3), (2,3,4), (1,2)(3,4), (1,3)(2,4) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Image(iso,g.3*g.4);</span>
(1,4)(2,3)
</pre></div>
<p>In many cases the permutation representation constructed by <code class="func">IsomorphismPermGroup</code> is regular.</p>
<p><a id="X8086628878AFD3EA" name="X8086628878AFD3EA"></a></p>
<h5>43.3-2 SmallerDegreePermutationRepresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallerDegreePermutationRepresentation</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">G</var> be a permutation group. <code class="func">SmallerDegreePermutationRepresentation</code> tries to find a faithful permutation representation of smaller degree. The result is a group homomorphism onto a permutation group, in the worst case this is the identity mapping on <var class="Arg">G</var>.</p>
<p>If the <code class="code">cheap</code> option is given, the function only tries to reduce to orbits or actions on blocks, otherwise also actions on cosets of random subgroups are tried.</p>
<p>Note that the result is not guaranteed to be a faithful permutation representation of smallest degree, or of smallest degree among the transitive permutation representations of <var class="Arg">G</var>. Using <strong class="pkg">GAP</strong> interactively, one might be able to choose subgroups of small index for which the cores intersect trivially; in this case, the actions on the cosets of these subgroups give rise to an intransitive permutation representation the degree of which may be smaller than the original degree.</p>
<p>The methods used might involve the use of random elements and the permutation representation (or even the degree of the representation) is not guaranteed to be the same for different calls of <code class="func">SmallerDegreePermutationRepresentation</code>.</p>
<p>If the option cheap is given less work is spent on trying to get a small degree representation, if the value of this option is set to the string "skip" the identity mapping is returned. (This is useful if a function called internally might try a degree reduction.)</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso:=RegularActionHomomorphism(SymmetricGroup(4));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">image:= Image( iso );; NrMovedPoints( image );</span>
24
<span class="GAPprompt">gap></span> <span class="GAPinput">small:= SmallerDegreePermutationRepresentation( image );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Image( small );</span>
Group([ (2,5,4,3), (1,4)(2,6)(3,5) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=Image(IsomorphismPermGroup(GL(4,5)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">sm:=SmallerDegreePermutationRepresentation(g:cheap);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NrMovedPoints(Range(sm));</span>
624
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p:=Group((1,2,3,4,5,6),(1,2));;p:=Action(p,AsList(p),OnRight);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(MovedPoints(p));</span>
720
<span class="GAPprompt">gap></span> <span class="GAPinput">q:=SmallerDegreePermutationRepresentation(p);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NrMovedPoints(Image(q));</span>
6
</pre></div>
<p><a id="X834208CD7C2956A3" name="X834208CD7C2956A3"></a></p>
<h4>43.4 <span class="Heading">Symmetric and Alternating Groups</span></h4>
<p>The commands <code class="func">SymmetricGroup</code> (<a href="chap50_mj.html#X858666F97BD85ABB"><span class="RefLink">50.1-12</span></a>) and <code class="func">AlternatingGroup</code> (<a href="chap50_mj.html#X7E54D3E778E6A53E"><span class="RefLink">50.1-11</span></a>) (see Section <a href="chap50_mj.html#X839981CC7D9B671B"><span class="RefLink">50.1</span></a>) construct symmetric and alternating permutation groups. <strong class="pkg">GAP</strong> can also detect whether a given permutation group is a symmetric or alternating group on the set of its moved points; if so then the group is called a <em>natural</em> symmetric or alternating group, respectively.</p>
<p>The functions <code class="func">IsSymmetricGroup</code> (<a href="chap43_mj.html#X85CA6AD17BE90C95"><span class="RefLink">43.4-2</span></a>) and <code class="func">IsAlternatingGroup</code> (<a href="chap43_mj.html#X8514BE9E79C608E0"><span class="RefLink">43.4-3</span></a>) can be used to check whether a given group (not necessarily a permutation group) is isomorphic to a symmetric or alternating group.</p>
<p><a id="X8129BE59781478E1" name="X8129BE59781478E1"></a></p>
<h5>43.4-1 IsNaturalSymmetricGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNaturalSymmetricGroup</code>( <var class="Arg">group</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNaturalAlternatingGroup</code>( <var class="Arg">group</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A group is a natural symmetric or alternating group if it is a permutation group acting as symmetric or alternating group, respectively, on its moved points.</p>
<p>For groups that are known to be natural symmetric or natural alternating groups, very efficient methods for computing membership, conjugacy classes, Sylow subgroups etc. are used.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=Group((1,5,7,8,99),(1,99,13,72));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNaturalSymmetricGroup(g);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g;</span>
Sym( [ 1, 5, 7, 8, 13, 72, 99 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNaturalSymmetricGroup( Group( (1,2)(4,5), (1,2,3)(4,5,6) ) );</span>
false
</pre></div>
<p><a id="X85CA6AD17BE90C95" name="X85CA6AD17BE90C95"></a></p>
<h5>43.4-2 IsSymmetricGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSymmetricGroup</code>( <var class="Arg">group</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is <code class="keyw">true</code> if the group <var class="Arg">group</var> is isomorphic to a symmetric group.</p>
<p><a id="X8514BE9E79C608E0" name="X8514BE9E79C608E0"></a></p>
<h5>43.4-3 IsAlternatingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAlternatingGroup</code>( <var class="Arg">group</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is <code class="keyw">true</code> if the group <var class="Arg">group</var> is isomorphic to an alternating group.</p>
<p><a id="X7ED60F7E81F1B614" name="X7ED60F7E81F1B614"></a></p>
<h5>43.4-4 SymmetricParentGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SymmetricParentGroup</code>( <var class="Arg">grp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>For a permutation group <var class="Arg">grp</var> this function returns the symmetric group that moves the same points as <var class="Arg">grp</var> does.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SymmetricParentGroup( Group( (1,2), (4,5), (7,8,9) ) );</span>
Sym( [ 1, 2, 4, 5, 7, 8, 9 ] )
</pre></div>
<p><a id="X83F8D3B578A7BEEB" name="X83F8D3B578A7BEEB"></a></p>
<h4>43.5 <span class="Heading">Primitive Groups</span></h4>
<p><a id="X7E50211A7B92455F" name="X7E50211A7B92455F"></a></p>
<h5>43.5-1 ONanScottType</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ONanScottType</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the type of a primitive permutation group <var class="Arg">G</var>, according to the O'Nan-Scott classification. The labelling of the different types is not consistent in the literature, we use the following identifications. The two-letter code given is the name of the type as used by Praeger.
<dl>
<dt><strong class="Mark">1</strong></dt>
<dd><p>Affine. (HA)</p>
</dd>
<dt><strong class="Mark">2</strong></dt>
<dd><p>Almost simple. (AS)</p>
</dd>
<dt><strong class="Mark">3a</strong></dt>
<dd><p>Diagonal, Socle consists of two normal subgroups. (HS)</p>
</dd>
<dt><strong class="Mark">3b</strong></dt>
<dd><p>Diagonal, Socle is minimal normal. (SD)</p>
</dd>
<dt><strong class="Mark">4a</strong></dt>
<dd><p>Product action with the first factor primitive of type 3a. (HC)</p>
</dd>
<dt><strong class="Mark">4b</strong></dt>
<dd><p>Product action with the first factor primitive of type 3b. (CD)</p>
</dd>
<dt><strong class="Mark">4c</strong></dt>
<dd><p>Product action with the first factor primitive of type 2. (PA)</p>
</dd>
<dt><strong class="Mark">5</strong></dt>
<dd><p>Twisted wreath product (TW)</p>
</dd>
</dl>
<p>See <a href="chapBib_mj.html#biBEickHulpke01">[EH01]</a> for correspondence to other labellings used in the literature. As it can contain letters, the type is returned as a string.</p>
<p>If <var class="Arg">G</var> is not a permutation group or does not act primitively on the points moved by it, the result is undefined.</p>
<p><a id="X7E89A46A86A3F4A2" name="X7E89A46A86A3F4A2"></a></p>
<h5>43.5-2 SocleTypePrimitiveGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SocleTypePrimitiveGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the socle type of the primitive permutation group <var class="Arg">G</var>. The socle of a primitive group is the direct product of isomorphic simple groups, therefore the type is indicated by a record with components <code class="code">series</code>, <code class="code">parameter</code> (both as described under <code class="func">IsomorphismTypeInfoFiniteSimpleGroup</code> (<a href="chap39_mj.html#X7C6AA6897C4409AC"><span class="RefLink">39.15-13</span></a>)), and <code class="code">width</code> for the number of direct factors.</p>
<p>If <var class="Arg">G</var> does not act primitively on its moved points, an error is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=AlternatingGroup(5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:=DirectProduct(g,g);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p:=List([1,2],i->Projection(h,i));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ac:=Action(h,AsList(g),</span>
<span class="GAPprompt">></span> <span class="GAPinput">function(g,h) return Image(p[1],h)^-1*g*Image(p[2],h);end);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(ac);NrMovedPoints(ac);IsPrimitive(ac,[1..60]);</span>
3600
60
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ONanScottType(ac);</span>
"3a"
<span class="GAPprompt">gap></span> <span class="GAPinput">SocleTypePrimitiveGroup(ac);</span>
rec(
name := "A(5) ~ A(1,4) = L(2,4) ~ B(1,4) = O(3,4) ~ C(1,4) = S(2,4) \
~ 2A(1,4) = U(2,4) ~ A(1,5) = L(2,5) ~ B(1,5) = O(3,5) ~ C(1,5) = S(2,\
5) ~ 2A(1,5) = U(2,5)", parameter := 5, series := "A", width := 2 )
</pre></div>
<p><a id="X7FA58C3A8283F3BD" name="X7FA58C3A8283F3BD"></a></p>
<h4>43.6 <span class="Heading">Stabilizer Chains</span></h4>
<p>Many of the algorithms for permutation groups use a <em>stabilizer chain</em> of the group. The concepts of stabilizer chains, <em>bases</em>, and <em>strong generating sets</em> were introduced by Charles Sims in <a href="chapBib_mj.html#biBSim70">[Sim70]</a>. An extensive account of basic algorithms together with asymptotic runtime analysis can be found in reference <a href="chapBib_mj.html#biBSeress2003">[Ser03, Chapter 4]</a>. A further discussion of base change is given in section <a href="chap87_mj.html#X870717BA831A0365"><span class="RefLink">87.1</span></a>.</p>
<p>Let <span class="SimpleMath">\(B = [ b_1, \ldots, b_n ]\)</span> be a list of points, <span class="SimpleMath">\(G^{(1)} = G\)</span> and <span class="SimpleMath">\(G^{{(i+1)}} = Stab_{{G^{(i)}}}(b_i)\)</span>, such that <span class="SimpleMath">\(G^{(n+1)} = \{ () \}\)</span>. Then the list <span class="SimpleMath">\([ b_1, \ldots, b_n ]\)</span> is called a <em>base</em> of <span class="SimpleMath">\(G\)</span>, the points <span class="SimpleMath">\(b_i\)</span> are called <em>base points</em>. A set <span class="SimpleMath">\(S\)</span> of generators for <span class="SimpleMath">\(G\)</span> satisfying the condition <span class="SimpleMath">\(\langle S \cap G^{(i)} \rangle = G^{(i)}\)</span> for each <span class="SimpleMath">\(1 \leq i \leq n\)</span>, is called a <em>strong generating set</em> (SGS) of <span class="SimpleMath">\(G\)</span>. (More precisely we ought to say that it is a SGS of <span class="SimpleMath">\(G\)</span> <em>relative</em> to <span class="SimpleMath">\(B\)</span>). The chain of subgroups <span class="SimpleMath">\(G^{(i)}\)</span> of <span class="SimpleMath">\(G\)</span> itself is called the <em>stabilizer chain</em> of <span class="SimpleMath">\(G\)</span> relative to <span class="SimpleMath">\(B\)</span>.</p>
<p>Since <span class="SimpleMath">\([ b_1, \ldots, b_n ]\)</span>, where <span class="SimpleMath">\(n\)</span> is the degree of <span class="SimpleMath">\(G\)</span> and <span class="SimpleMath">\(b_i\)</span> are the moved points of <span class="SimpleMath">\(G\)</span>, certainly is a base for <span class="SimpleMath">\(G\)</span> there exists a base for each permutation group. The number of points in a base is called the <em>length</em> of the base. A base <span class="SimpleMath">\(B\)</span> is called <em>reduced</em> if there exists no <span class="SimpleMath">\(i\)</span> such that <span class="SimpleMath">\(G^{(i)} = G^{(i+1)}\)</span>. (This however does not imply that no subset of <span class="SimpleMath">\(B\)</span> could also serve as a base.) Note that different reduced bases for one permutation group <span class="SimpleMath">\(G\)</span> may have different lengths. For example, the irreducible degree <span class="SimpleMath">\(416\)</span> permutation representation of the Chevalley Group <span class="SimpleMath">\(G_2(4)\)</span> possesses reduced bases of lengths <span class="SimpleMath">\(5\)</span> and <span class="SimpleMath">\(7\)</span>.</p>
<p>Let <span class="SimpleMath">\(R^{(i)}\)</span> be a right transversal of <span class="SimpleMath">\(G^{(i+1)}\)</span> in <span class="SimpleMath">\(G^{(i)}\)</span>, i.e. a set of right coset representatives of the cosets of <span class="SimpleMath">\(G^{(i+1)}\)</span> in <span class="SimpleMath">\(G^{(i)}\)</span>. Then each element <span class="SimpleMath">\(g\)</span> of <span class="SimpleMath">\(G\)</span> has a unique representation as a product of the form <span class="SimpleMath">\(g = r_n \ldots r_1\)</span> with <span class="SimpleMath">\(r_i \in R^{(i)}\)</span>. The cosets of <span class="SimpleMath">\(G^{(i+1)}\)</span> in <span class="SimpleMath">\(G^{(i)}\)</span> are in bijective correspondence with the points in <span class="SimpleMath">\(O^{(i)} := b_i^{{G^{(i)}}}\)</span>. So we could represent a transversal as a list <span class="SimpleMath">\(T\)</span> such that <span class="SimpleMath">\(T[p]\)</span> is a representative of the coset corresponding to the point <span class="SimpleMath">\(p \in O^{(i)}\)</span>, i.e., an element of <span class="SimpleMath">\(G^{(i)}\)</span> that takes <span class="SimpleMath">\(b_i\)</span> to <span class="SimpleMath">\(p\)</span>. (Note that such a list has holes in all positions corresponding to points not contained in <span class="SimpleMath">\(O^{(i)}\)</span>.)</p>
<p>This approach however will store many different permutations as coset representatives which can be a problem if the degree <span class="SimpleMath">\(n\)</span> gets bigger. Our goal therefore is to store as few different permutations as possible such that we can still reconstruct each representative in <span class="SimpleMath">\(R^{(i)}\)</span>, and from them the elements in <span class="SimpleMath">\(G\)</span>. A <em>factorized inverse transversal</em> <span class="SimpleMath">\(T\)</span> is a list where <span class="SimpleMath">\(T[p]\)</span> is a generator of <span class="SimpleMath">\(G^{(i)}\)</span> such that <span class="SimpleMath">\(p^{{T[p]}}\)</span> is a point that lies earlier in <span class="SimpleMath">\(O^{(i)}\)</span> than <span class="SimpleMath">\(p\)</span> (note that we consider <span class="SimpleMath">\(O^{(i)}\)</span> as a list, not as a set). If we assume inductively that we know an element <span class="SimpleMath">\(r \in G^{(i)}\)</span> that takes <span class="SimpleMath">\(b_i\)</span> to <span class="SimpleMath">\(p^{{T[p]}}\)</span>, then <span class="SimpleMath">\(r T[p]^{{-1}}\)</span> is an element in <span class="SimpleMath">\(G^{(i)}\)</span> that takes <span class="SimpleMath">\(b_i\)</span> to <span class="SimpleMath">\(p\)</span>. <strong class="pkg">GAP</strong> uses such factorized inverse transversals.</p>
<p>Another name for a factorized inverse transversal is a <em>Schreier tree</em>. The vertices of the tree are the points in <span class="SimpleMath">\(O^{(i)}\)</span>, and the root of the tree is <span class="SimpleMath">\(b_i\)</span>. The edges are defined as the ordered pairs <span class="SimpleMath">\((p, p^{{T[p]}})\)</span>, for <span class="SimpleMath">\(p \in O^{(i)} \setminus \{ b_i \}\)</span>. The edge <span class="SimpleMath">\((p, p^{{T[p]}})\)</span> is labelled with the generator <span class="SimpleMath">\(T[p]\)</span>, and the product of edge labels along the unique path from <span class="SimpleMath">\(p\)</span> to <span class="SimpleMath">\(b_i\)</span> is the inverse of the transversal element carrying <span class="SimpleMath">\(b_i\)</span> to <span class="SimpleMath">\(p\)</span>.</p>
<p>Before we describe the construction of stabilizer chains in <a href="chap43_mj.html#X7C7EA55C80E457FA"><span class="RefLink">43.8</span></a>, we explain in <a href="chap43_mj.html#X7C2406B97E057196"><span class="RefLink">43.7</span></a> the idea of using non-deterministic algorithms; this is necessary for understanding the options available for the construction of stabilizer chains. After that, in <a href="chap43_mj.html#X81D7FCE47AC7F942"><span class="RefLink">43.9</span></a> it is explained how a stabilizer chain is stored in <strong class="pkg">GAP</strong>, <a href="chap43_mj.html#X7ECF8A4586346FD4"><span class="RefLink">43.10</span></a> lists operations for stabilizer chains, and <a href="chap43_mj.html#X8188051F79E72A95"><span class="RefLink">43.11</span></a> lists low level routines for manipulating stabilizer chains.</p>
<p><a id="X7C2406B97E057196" name="X7C2406B97E057196"></a></p>
<h4>43.7 <span class="Heading">Randomized Methods for Permutation Groups</span></h4>
<p>For most computations with permutation groups, it is crucial to construct stabilizer chains efficiently. Sims's original construction in [Sim70] is deterministic, and is called the Schreier-Sims algorithm, because it is based on Schreier's Lemma (<a href="chapBib_mj.html#biBHall">[HJ59, p. 96]</a>): given <span class="SimpleMath">\(K = \langle S \rangle\)</span> and a transversal <span class="SimpleMath">\(T\)</span> for <span class="SimpleMath">\(K\)</span> mod <span class="SimpleMath">\(L\)</span>, one can obtain <span class="SimpleMath">\(|S||T|\)</span> generators for <span class="SimpleMath">\(L\)</span>. This lemma is applied recursively, with consecutive point stabilizers <span class="SimpleMath">\(G^{(i)}\)</span> and <span class="SimpleMath">\(G^{(i+1)}\)</span> playing the role of <span class="SimpleMath">\(K\)</span> and <span class="SimpleMath">\(L\)</span>.</p>
<p>In permutation groups of large degree, the number of Schreier generators to be processed becomes too large, and the deterministic Schreier-Sims algorithm becomes impractical. Therefore, <strong class="pkg">GAP</strong> uses randomized algorithms. The method selection process, which is quite different from Version 3, works the following way.</p>
<p>If a group acts on not more than a hundred points, Sims's original deterministic algorithm is applied. In groups of degree greater than hundred, a heuristic algorithm based on ideas in [BCFS91] constructs a stabilizer chain. This construction is complemented by a verify-routine that either proves the correctness of the stabilizer chain or causes the extension of the chain to a correct one. The user can influence the verification process by setting the value of the record component random (cf. 43.8).
<p>If the <code class="code">random</code> value equals <span class="SimpleMath">\(1000\)</span> then a slight extension of an unpublished method of Sims is used. The outcome of this verification process is always correct. The user also can prescribe any integer <span class="SimpleMath">\(x\)</span>, <span class="SimpleMath">\(1 \leq x \leq 999\)</span> as the value of <code class="code">random</code>. In this case, a randomized verification process from <a href="chapBib_mj.html#biBBCFS91">[BCFS91]</a> is applied, and the result of the stabilizer chain construction is guaranteed to be correct with probability at least <span class="SimpleMath">\(x/1000\)</span>. The practical performance of the algorithm is much better than the theoretical guarantee.</p>
<p>If the stabilizer chain is not correct then the elements in the product of transversals <span class="SimpleMath">\(R^{(m)} R^{(m-1)} \cdots R^{(1)}\)</span> constitute a proper subset of the group <span class="SimpleMath">\(G\)</span> in question. This means that a membership test with this stabilizer chain returns <code class="keyw">false</code> for all elements that are not in <span class="SimpleMath">\(G\)</span>, but it may also return <code class="keyw">false</code> for some elements of <span class="SimpleMath">\(G\)</span>; in other words, the result <code class="keyw">true</code> of a membership test is always correct, whereas the result <code class="keyw">false</code> may be incorrect.</p>
<p>The construction and verification phases are separated because there are situations where the verification step can be omitted; if one happens to know the order of the group in advance then the randomized construction of the stabilizer chain stops as soon as the product of the lengths of the basic orbits of the chain equals the group order, and the chain will be correct (see the <code class="code">size</code> option of the <code class="func">StabChain</code> (<a href="chap43_mj.html#X80B5CF78829495C2"><span class="RefLink">43.8-1</span></a>) command).</p>
<p>Although the worst case running time is roughly quadratic for Sims's verification and roughly linear for the randomized one, in most examples the running time of the stabilizer chain construction with random value \(1000\) (i.e., guaranteed correct output) is about the same as the running time of randomized verification with guarantee of at least \(90\) percent correctness. Therefore, we suggest to use the default value random \(= 1000\). Possible uses of random values less than \(1000\) are when one has to run through a large collection of subgroups, and a low value of random is used to choose quickly a candidate for more thorough examination; another use is when the user suspects that the quadratic bottleneck of the guaranteed correct verification is hit.
<p>We will give two examples to illustrate these ideas.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:= SL(4,7);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">o:= Orbit( h, [1,0,0,0]*Z(7)^0, OnLines );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">op:= Action( h, o, OnLines );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NrMovedPoints( op );</span>
400
</pre></div>
<p>We created a permutation group on <span class="SimpleMath">\(400\)</span> points. First we compute a guaranteed correct stabilizer chain (see <code class="func">StabChain</code> (<a href="chap43_mj.html#X80B5CF78829495C2"><span class="RefLink">43.8-1</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:= Group( GeneratorsOfGroup( op ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StabChain( h );; time;</span>
1120
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( h );</span>
2317591180800
</pre></div>
<p>Now randomized verification will be used. We require that the result is guaranteed correct with probability <span class="SimpleMath">\(90\)</span> percent. This means that if we would do this calculation many times over, <strong class="pkg">GAP</strong> would <em>guarantee</em> that in least <span class="SimpleMath">\(90\)</span> percent of all calculations the result is correct. In fact the results are much better than the guarantee, but we cannot promise that this will really happen. (For the meaning of the <code class="code">random</code> component in the second argument of <code class="func">StabChain</code> (<a href="chap43_mj.html#X80B5CF78829495C2"><span class="RefLink">43.8-1</span></a>).)</p>
<p>First the group is created anew.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:= Group( GeneratorsOfGroup( op ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StabChain( h, rec( random:= 900 ) );; time;</span>
1410
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( h );</span>
2317591180800
</pre></div>
<p>The result is still correct, and the running time is actually somewhat slower. If you give the algorithm the order of the group, then it can check its result, and so things become faster and the result is guaranteed to be correct. This can be done with the <code class="code">size</code> option (see <code class="func">StabChain</code> (<a href="chap43_mj.html#X80B5CF78829495C2"><span class="RefLink">43.8-1</span></a>)), or by setting the size of the group beforehand with <code class="code">SetSize</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:=Group( GeneratorsOfGroup( op ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetSize( h, 2317591180800 );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StabChain( h );; time;</span>
170
</pre></div>
<p>The second example gives a typical group when the verification with <code class="code">random</code> value <span class="SimpleMath">\(1000\)</span> is slow. The problem is that the group has a stabilizer subgroup <span class="SimpleMath">\(G^{(i)}\)</span> such that the fundamental orbit <span class="SimpleMath">\(O^{(i)}\)</span> is split into a lot of orbits when we stabilize <span class="SimpleMath">\(b_i\)</span> and one additional point of <span class="SimpleMath">\(O^{(i)}\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1:=PermList(Concatenation([401],[1..400]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2:=PermList(List([1..400],i->(i*20 mod 401)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">d:=DirectProduct(Group(p1,p2),SymmetricGroup(5));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">h:=Group(GeneratorsOfGroup(d));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StabChain(h);;time;Size(h);</span>
1030
192480
<span class="GAPprompt">gap></span> <span class="GAPinput">h:=Group(GeneratorsOfGroup(d));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StabChain(h,rec(random:=900));;time;Size(h);</span>
570
192480
</pre></div>
<p>When stabilizer chains of a group <span class="SimpleMath">\(G\)</span> are created with <code class="code">random</code> value less than <span class="SimpleMath">\(1000\)</span>, this is noted in the group <span class="SimpleMath">\(G\)</span>, by setting of the record component <code class="code">random</code> in the value of the attribute <code class="func">StabChainOptions</code> (<a href="chap43_mj.html#X790C27B8783EDE68"><span class="RefLink">43.8-2</span></a>) for <span class="SimpleMath">\(G\)</span>. As errors induced by the random methods might propagate, any group or homomorphism created from <span class="SimpleMath">\(G\)</span> inherits a <code class="code">random</code> component in its <code class="func">StabChainOptions</code> (<a href="chap43_mj.html#X790C27B8783EDE68"><span class="RefLink">43.8-2</span></a>) value from the corresponding component for <span class="SimpleMath">\(G\)</span>.</p>
<p>A lot of algorithms dealing with permutation groups use randomized methods; however, if the initial stabilizer chain construction for a group is correct, these further methods will provide guaranteed correct output.</p>
<p><a id="X7C7EA55C80E457FA" name="X7C7EA55C80E457FA"></a></p>
<h4>43.8 <span class="Heading">Construction of Stabilizer Chains</span></h4>
<p><a id="X80B5CF78829495C2" name="X80B5CF78829495C2"></a></p>
<h5>43.8-1 StabChain</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StabChain</code>( <var class="Arg">G</var>[, <var class="Arg">options</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">‣ StabChain</code>( <var class="Arg">G</var>, <var class="Arg">base</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">‣ StabChainOp</code>( <var class="Arg">G</var>, <var class="Arg">options</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">‣ StabChainMutable</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StabChainMutable</code>( <var class="Arg">permhomom</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StabChainImmutable</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>These commands compute a stabilizer chain for the permutation group <var class="Arg">G</var>; additionally, <code class="func">StabChainMutable</code> is also an attribute for the group homomorphism <var class="Arg">permhomom</var> whose source is a permutation group.</p>
<p>(The mathematical background of stabilizer chains is sketched in <a href="chap43_mj.html#X7FA58C3A8283F3BD"><span class="RefLink">43.6</span></a>, more information about the objects representing stabilizer chains in <strong class="pkg">GAP</strong> can be found in <a href="chap43_mj.html#X81D7FCE47AC7F942"><span class="RefLink">43.9</span></a>.)</p>
<p><code class="func">StabChainOp</code> is an operation with two arguments <var class="Arg">G</var> and <var class="Arg">options</var>, the latter being a record which controls some aspects of the computation of a stabilizer chain (see below); <code class="func">StabChainOp</code> returns a <em>mutable</em> stabilizer chain. <code class="func">StabChainMutable</code> is a <em>mutable</em> attribute for groups or homomorphisms, its default method for groups is to call <code class="func">StabChainOp</code> with empty options record. <code class="func">StabChainImmutable</code> is an attribute with <em>immutable</em> values; its default method dispatches to <code class="func">StabChainMutable</code>.</p>
<p><code class="func">StabChain</code> is a function with first argument a permutation group <var class="Arg">G</var>, and optionally a record <var class="Arg">options</var> as second argument. If the value of <code class="func">StabChainImmutable</code> for <var class="Arg">G</var> is already known and if this stabilizer chain matches the requirements of <var class="Arg">options</var>, <code class="func">StabChain</code> simply returns this stored stabilizer chain. Otherwise <code class="func">StabChain</code> calls <code class="func">StabChainOp</code> and returns an immutable copy of the result; additionally, this chain is stored as <code class="func">StabChainImmutable</code> value for <var class="Arg">G</var>. If no <var class="Arg">options</var> argument is given, its components default to the global variable <code class="func">DefaultStabChainOptions</code> (<a href="chap43_mj.html#X87E1292E85A5D31C"><span class="RefLink">43.8-3</span></a>). If <var class="Arg">base</var> is a list of positive integers, the version <code class="code">StabChain( <var class="Arg">G</var>, <var class="Arg">base</var> )</code> defaults to <code class="code">StabChain( <var class="Arg">G</var>, rec( base:= <var class="Arg">base</var> ) )</code>.</p>
<p>If given, <var class="Arg">options</var> is a record whose components specify properties of the desired stabilizer chain or which may help the algorithm. Default values for all of them can be given in the global variable <code class="func">DefaultStabChainOptions</code> (<a href="chap43_mj.html#X87E1292E85A5D31C"><span class="RefLink">43.8-3</span></a>). The following options are supported.</p>
<dl>
<dt><strong class="Mark"><code class="code">base</code> (default an empty list)</strong></dt>
<dd><p>A list of points, through which the resulting stabilizer chain shall run. For the base <span class="SimpleMath">\(B\)</span> of the resulting stabilizer chain <var class="Arg">S</var> this means the following. If the <code class="code">reduced</code> component of <var class="Arg">options</var> is <code class="keyw">true</code> then those points of <code class="code">base</code> with nontrivial basic orbits form the initial segment of <span class="SimpleMath">\(B\)</span>, if the <code class="code">reduced</code> component is <code class="keyw">false</code> then <code class="code">base</code> itself is the initial segment of <span class="SimpleMath">\(B\)</span>. Repeated occurrences of points in <code class="code">base</code> are ignored. If a stabilizer chain for <var class="Arg">G</var> is already known then the stabilizer chain is computed via a base change.</p>
</dd>
<dt><strong class="Mark"><code class="code">knownBase</code> (no default value)</strong></dt>
<dd><p>A list of points which is known to be a base for the group. Such a known base makes it easier to test whether a permutation given as a word in terms of a set of generators is the identity, since it suffices to map the known base with each factor consecutively, rather than multiplying the whole permutations (which would mean to map every point). This speeds up the Schreier-Sims algorithm which is used when a new stabilizer chain is constructed; it will not affect a | |
