|
|
|
|
Quelle chap1.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/mapclass/doc/chap1.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 (MapClass) - Chapter 1: Introduction and Main Functions</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap1" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0.html">Top</ a> < a href="chap1.html">1</a> <a href="chapA.html">A</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap0.html">[Previous Chapter]</a> <a href="chapA.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap1_mj.html">[MathJax on]</a></p>
<p><a id="X7B9EBA44836A7F7D" name="X7B9EBA44836A7F7D"></a></p>
<div class="ChapSects"><a href="chap1.html#X7B9EBA44836A7F7D">1 <span class="Heading">Introduction and Main Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X7929306C7A98029D">1.1 <span class="Heading">Background Material</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X7D47DF997A20A44A">1.2 <span class="Heading">Overview of Main
Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7820883E8607F7AF">1.2-1 AllMCOrbits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X791C18967E0DFC70">1.2-2 AllMCOrbitsCore</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7EFE8AF479347734">1.2-3 GeneratingMCOrbits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8383CA687FFFC2EF">1.2-4 GeneratingMCOrbitsCore</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X84D605BD79533A1E">1.2-5 MappingClassOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7E26117582BDD678">1.2-6 PrepareMinTree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7D9564417E8C1A00">1.2-7 MinimizeTuple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7CA1E3A07A4F6270">1.2-8 EasyMinimizeTuple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X8469F8DC845C902D">1.2-9 IsInOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7930B90F8572763B">1.2-10 FindTupleInOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7975937984C559FC">1.2-11 IsEqualOrbit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X815C513B789565CF">1.2-12 SelectTuple</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7B772B3C8275F5DD">1.2-13 NumberGeneratingTuples</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7D054A867DC96522">1.2-14 TotalNumberTuples</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X855F49457DC386AF">1.2-15 CalculateTuplePartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X86EA79C9873E3141">1.2-16 RestoreOrbitFromFile</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X82F6093885ECD889">1.2-17 SaveOrbitToFile</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X83EB578D85D98DF5">1.3 <span class="Heading">Key Data Structures</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X84FDC7BD82227DA8">1.3-1 <span class="Heading">The Orbit Record</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap1.html#X7CEE3F9180497635">1.3-2 <span class="Heading">The Tuple Table</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X81D1E049865AE89E">1.4 <span class="Heading">A Sample Session</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X7A3C63AC854BCF4C">1.5 <span class="Heading">An Application</span></a>
</span>
</div>
</div>
<h3>1 <span class="Heading">Introduction and Main Functions</span></h3>
<p>This chapter provides an overview of the background material, and provides documentation for the main functions and data structures of the MapClass package.</p>
<p><a id="X7929306C7A98029D" name="X7929306C7A98029D"></a></p>
<h4>1.1 <span class="Heading">Background Material</span></h4>
<p>Let <span class="SimpleMath">G</span> be a finite group, let <span class="SimpleMath">C_1,..., C_r</span> be a collection of conjugacy classes in <span class="SimpleMath">G</span>. Let <span class="SimpleMath">mathcalE = mathcalE(G,g,(C_1, dots, C_r))</span> denote the set of all tuples <span class="SimpleMath">σ = (σ_1,...,σ_2g+r)∈ G^2g+r</span> (for natural numbers <span class="SimpleMath">g</span> and <span class="SimpleMath">r</span>) of elements in <span class="SimpleMath">G</span> satisfying the relation</p>
<p class="pcenter"> \prod_{i=1}^g [\sigma_i,
\sigma_{g+i}] \prod_{i=1}^r \sigma_{2g+i} = 1
</p>
<p>and such that <span class="SimpleMath">σ_2g +k ∈ C_k</span>. If the tuple also satisfies <span class="SimpleMath">⟨ σ_1, ..., σ_2g+r⟩ = G</span> it is said to be <em>generating</em>.</p>
<p>One may associate the elements of the tuple <span class="SimpleMath">σ</span> with the standard generators of the fundamental group of a compact connected surface <span class="SimpleMath">S</span> (genus <span class="SimpleMath">g</span>, <span class="SimpleMath">r</span> punctures). The mapping class group of <span class="SimpleMath">S</span> is naturally isomorphic to <span class="SimpleMath">Out(π_1(S))</span> and so gives rise to an action on the fundamental group of <span class="SimpleMath">S</span> modulo inner automorphisms. This action can be transferred to an action on the set <span class="SimpleMath">mathcalE</span> (up to conjugation in <span class="SimpleMath">G</span>). The <em>mapping class orbits</em> are the orbits of <span class="SimpleMath">mathcalE</span> under this action.</p>
<p>The package can be used to compute the set <span class="SimpleMath">mathcalE(G, g, (C_1,...,C_r))</span> and the corresponding partition into mapping class orbits for a given group <span class="SimpleMath">G</span> and a set of conjugacy classes <span class="SimpleMath">(C_1,...,C_r)</span> (although the programs expect a tuple of class representatives). For an example application see Section <a href="chap1.html#X7A3C63AC854BCF4C"><span class="RefLink">1.5</span></a>. We call the tuple <span class="SimpleMath">(g;C_1,...,C_r)</span> the signature. The package is an extension of the <em>Braid</em> package for <strong class="pkg">GAP</strong>.</p>
<p><a id="X7D47DF997A20A44A" name="X7D47DF997A20A44A"></a></p>
<h4>1.2 <span class="Heading">Overview of Main
Functions</span></h4>
<p>The following are the principal ways for calculating the mapping class orbits for a given signature and group. We require our groups to be permutation groups, and the tuple in question to have length at least two.</p>
<p><a id="X7820883E8607F7AF" name="X7820883E8607F7AF"></a></p>
<h5>1.2-1 AllMCOrbits</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AllMCOrbits</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function calculates the orbits for the given group, genus and tuple. This function is a wrapper for the function <code class="func">AllMCOrbitsCore</code> (<a href="chap1.html#X791C18967E0DFC70"><span class="RefLink">1.2-2</span></a>), and so can make use of GAP's <code class="keyw">OptionsStack</code>. The options are described in more detail in the documentation for <code class="func">AllMCOrbitsCore</code> (<a href="chap1.html#X791C18967E0DFC70"><span class="RefLink">1.2-2</span></a>). We draw attention to two useful options: the <code class="code">OutputStyle</code> and <code class="code">SaveOrbit</code> options. The <code class="code">SaveOrbit</code> option takes values of either <code class="keyw">false</code> - in which case the orbit is not saved to a file - or it accepts a string that is the name of a directory in which the routine saves the orbits. See <code class="func">AllMCOrbitsCore</code> (<a href="chap1.html#X791C18967E0DFC70"><span class="RefLink">1.2-2</span></a>) for more details on the saving process. The <code class="code"> OutputStyle </code> option controls the verbosity of the output of the function. It accepts three possible values:</p>
<ul>
<li><p><code class="code">"silent"</code> -- the routine prints no output except in the case of an Error.</p>
</li>
<li><p><code class="code">"single-line"</code> -- the routine prints output to a single line. An intermediate output style for those who want some output but do not want to see all diagnostic output.</p>
</li>
<li><p><code class="code">"full"</code> -- the routine provides full diagnostic output.</p>
</li>
</ul>
<p><a id="X791C18967E0DFC70" name="X791C18967E0DFC70"></a></p>
<h5>1.2-2 AllMCOrbitsCore</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AllMCOrbitsCore</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">tuple</var>, <var class="Arg">partition</var>, <var class="Arg">constant</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function calculates the orbits for the given group, genus and tuple, with the <span class="SimpleMath">r</span> branch points partitioned as in <var class="Arg">partition</var>. It uses the given <var class="Arg">constant</var> to determine how many of the tuples it want to account for before exiting. This function also make use of GAP's <code class="keyw">OptionsStack</code> if one desires to alter how the algorithm runs. The following options and their defaults are given below.</p>
<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdright">Option Name</td>
<td class="tdcenter">Default Value</td>
</tr>
<tr>
<td class="tdright"><code class="code">MaximumWeight</code></td>
<td class="tdcenter">40</td>
</tr>
<tr>
<td class="tdright"><code class="code">MinimumWeight</code></td>
<td class="tdcenter">20</td>
</tr>
<tr>
<td class="tdright"><code class="code">InitialWeight</code></td>
<td class="tdcenter">20</td>
</tr>
<tr>
<td class="tdright"><code class="code">BumpUp</code></td>
<td class="tdcenter">7</td>
</tr>
<tr>
<td class="tdright"><code class="code">KnockDown</code></td>
<td class="tdcenter">7</td>
</tr>
<tr>
<td class="tdright"><code class="code">InitialNumberOfRandomTuples </code></td>
<td class="tdcenter">20</td>
</tr>
<tr>
<td class="tdright"><code class="code"> SaveOrbit </code></td>
<td class="tdcenter"><code class="keyw">false</code></td>
</tr>
<tr>
<td class="tdright"><code class="code"> OutputStyle </code></td>
<td class="tdcenter"><code class="keyw">"full"</code></td>
</tr>
</table><br />
</div>
<p>When trying to search for orbits it can be the case that the routine struggles to find a small orbit because of the low probability of randomly choosing a tuple in the orbit. To combat this problem the routine does not choose tuples entirely randomly but uses a weighted random selection to increase the probability of selecting tuples appearing in small tuples. To small subgroups of our group we have an associated weight. When a subgroup is generated by a tuple in our orbit frequently then we reduce its weight. Subgroups which do not appear often have their weight increased. The options <code class="code">MaximumWeight</code>, <code class="code">MinimumWeight</code>, <code class="code">InitialWeight</code>,<code class="code">BumpUp</code>, and <code class="code">KnockDown</code>, control this subgroup weighting. Each option takes positive integer values. They play the following roles in the weighting process:</p>
<ul>
<li><p><code class="code">MaximumWeight</code> : The maximum weight that a subgroup can be.</p>
</li>
<li><p><code class="code">MinimumWeight</code> : The minimum weight that a subgroup can be.</p>
</li>
<li><p><code class="code">InitialWeight</code> : The weight that a new subgroup receives when added to to the list of small subgroups.</p>
</li>
<li><p><code class="code">BumpUp</code> : The amount we increase the weight of a subgroup by when it does not appear frequently.</p>
</li>
<li><p><code class="code">KnockDown</code> : The amount we decrease the weight of a subgroup by when it appears too frequently.</p>
</li>
</ul>
<p>The default options were chosen experimentally and so it may be beneficial to tune these values for a specific case.</p>
<p>The option <code class="code">InitialNumberOfRandomTuples</code> decides how many tuples the routine collects before trying to see if they are in some pre-existing orbit.</p>
<p>The option <code class="code">SaveOrbit</code> which is by default <code class="keyw">false</code> can be set to the name of a directory in which you want to save orbits. This option then saves the orbits to files in the folder with "<code class="file">_name</code>". So for example if you wish to save your orbits into the file <code class="file">_example</code> then you would run <code class="code">AllMCOrbits(group, genus, tuple: SaveOrbit:="example");</code>. The orbits are then saved in orbits which are named numerically. Following on from the above example then the first orbit will be saved as "_example/0". The <code class="code"> OutputStyle </code> option controls the verbosity of the output. It accepts three possible values:</p>
<ul>
<li><p><code class="code">"silent"</code> - the routine prints no output except in the case of an Error.</p>
</li>
<li><p><code class="code">"single-line"</code> - the routine output to a single line. An intermediate output style for those who want some output but do not want to see all diagnostic output.</p>
</li>
<li><p><code class="code">"full"</code> - the routine provides full diagnostic output.</p>
</li>
</ul>
<p><a id="X7EFE8AF479347734" name="X7EFE8AF479347734"></a></p>
<h5>1.2-3 GeneratingMCOrbits</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GeneratingMCOrbits</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This calculates the orbits for the given arguments. Unlike the <code class="func">AllMCOrbits</code> (<a href="chap1.html#X7820883E8607F7AF"><span class="RefLink">1.2-1</span></a>) function, <code class="code">GeneratingMCOrbits</code> calculates only those orbits whose tuples generate the whole of our original group.</p>
<p><a id="X8383CA687FFFC2EF" name="X8383CA687FFFC2EF"></a></p>
<h5>1.2-4 GeneratingMCOrbitsCore</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GeneratingMCOrbitsCore</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">tuple</var>, <var class="Arg">partition</var>, <var class="Arg">constant</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This calculates the orbits for the given arguments. Unlike the <code class="func">AllMCOrbits</code> (<a href="chap1.html#X7820883E8607F7AF"><span class="RefLink">1.2-1</span></a>) function, <code class="code">GeneratingMCOrbitsCore</code> calculates only those orbits whose tuples generate the whole of our original group. As with <code class="func">AllMCOrbitsCore</code> (<a href="chap1.html#X791C18967E0DFC70"><span class="RefLink">1.2-2</span></a>), the argument <var class="Arg">partition</var> must be a partition of the conjugacy classes represented in list form. We also have access to the full value of the options stack as in <code class="func">AllMCOrbitsCore</code> (<a href="chap1.html#X791C18967E0DFC70"><span class="RefLink">1.2-2</span></a>).</p>
<p><a id="X84D605BD79533A1E" name="X84D605BD79533A1E"></a></p>
<h5>1.2-5 MappingClassOrbit</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MappingClassOrbit</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">principaltuple</var>, <var class="Arg">partition</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an orbit record for an orbit containing tuple or returns <code class="keyw">fail</code></p>
<p>Calculates the orbit of the <var class="Arg">tuple</var> with respect to the given <var class="Arg">group</var>, <var class="Arg">principaltuple</var> and <var class="Arg">genus</var>.</p>
<p><a id="X7E26117582BDD678" name="X7E26117582BDD678"></a></p>
<h5>1.2-6 PrepareMinTree</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PrepareMinTree</code>( <var class="Arg">principaltuple</var>, <var class="Arg">group</var>, <var class="Arg">ourR</var>, <var class="Arg">genus</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record with two keys <code class="code">MinimizationTree</code> and <code class="code">MinimumSet</code>. If <code class="code">record</code> is the returned record then <code class="code">record.MinimizationTree</code> is the list encoding the tree used to help minimize tuples. The list <code class="code"> record.MinimumSet</code> is a list of minimal elements which is also used to speed up tuple minimization.</p>
<p><a id="X7D9564417E8C1A00" name="X7D9564417E8C1A00"></a></p>
<h5>1.2-7 MinimizeTuple</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MinimizeTuple</code>( <var class="Arg">tuple</var>, <var class="Arg">minimizationTree</var>, <var class="Arg">minimumSet</var>, <var class="Arg">numberOfGenerators</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the minimal tuple in the same orbit of <var class="Arg">tuple</var>.</p>
<p>Take the minimisation data provided by <code class="func">PrepareMinTree</code> (<a href="chap1.html#X7E26117582BDD678"><span class="RefLink">1.2-6</span></a>) and minimizes the given <var class="Arg">tuple</var>.</p>
<p><a id="X7CA1E3A07A4F6270" name="X7CA1E3A07A4F6270"></a></p>
<h5>1.2-8 EasyMinimizeTuple</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; EasyMinimizeTuple</code>( <var class="Arg">group</var>, <var class="Arg">genus</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the minimal tuple in the same orbit as <var class="Arg">tuple</var>.</p>
<p><a id="X8469F8DC845C902D" name="X8469F8DC845C902D"></a></p>
<h5>1.2-9 IsInOrbit</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsInOrbit</code>( <var class="Arg">orbit</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">True</code> if the <var class="Arg">tuple</var> lies in the <var class="Arg">orbit</var>.</p>
<p><a id="X7930B90F8572763B" name="X7930B90F8572763B"></a></p>
<h5>1.2-10 FindTupleInOrbit</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FindTupleInOrbit</code>( <var class="Arg">orbit</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the index of <var class="Arg">tuple</var> in <code class="code">orbit.TupleTable</code> if in the <var class="Arg">orbit</var>. If the tuple is not in <var class="Arg">orbit</var> returns <code class="keyw">fail</code>.</p>
<p><a id="X7975937984C559FC" name="X7975937984C559FC"></a></p>
<h5>1.2-11 IsEqualOrbit</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsEqualOrbit</code>( <var class="Arg">orbit1</var>, <var class="Arg">orbit2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if the two orbits are equal else returns <code class="keyw">fail</code>.</p>
<p><a id="X815C513B789565CF" name="X815C513B789565CF"></a></p>
<h5>1.2-12 SelectTuple</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SelectTuple</code>( <var class="Arg">orbit</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the tuple <code class="code">orbit.TupleTable[index].tuple</code>.</p>
<p><a id="X7B772B3C8275F5DD" name="X7B772B3C8275F5DD"></a></p>
<h5>1.2-13 NumberGeneratingTuples</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; NumberGeneratingTuples</code>( <var class="Arg">group</var>, <var class="Arg">partition</var>, <var class="Arg">tuple</var>, <var class="Arg">genus</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the total number of possible generating tuples for the group and tuple.</p>
<p><a id="X7D054A867DC96522" name="X7D054A867DC96522"></a></p>
<h5>1.2-14 TotalNumberTuples</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; TotalNumberTuples</code>( <var class="Arg">group</var>, <var class="Arg">tuple</var>, <var class="Arg">genus</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the total number of tuples we have to account for.</p>
<p><a id="X855F49457DC386AF" name="X855F49457DC386AF"></a></p>
<h5>1.2-15 CalculateTuplePartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; CalculateTuplePartition</code>( <var class="Arg">group</var>, <var class="Arg">tuple</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A partition of <span class="Math">{1,\ldots, r}</span> where <span class="Math">r</span> is the length of the tuple.</p>
<p>The function returns a partition of <span class="Math">{1,\ldots, r}</span> such that <span class="SimpleMath">i</span> and <span class="SimpleMath">j</span> lie in the same block if and only if the elements <code class="code">tuple[i]</code> and <code class="code">tuple[j]</code> are member of the same conjugacy class. The program currently requires that the elements of the tuple be ordered such that if <code class="code">tuple[i]</code> and <code class="code">tuple[j]</code> are in the same conjugacy class with <span class="SimpleMath">i ≤ j</span> then so is<code class="code">tuple[k]</code> for all <span class="SimpleMath">i ≤ k ≤ j</span>.</p>
<p><a id="X86EA79C9873E3141" name="X86EA79C9873E3141"></a></p>
<h5>1.2-16 RestoreOrbitFromFile</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RestoreOrbitFromFile</code>( <var class="Arg">n</var>, <var class="Arg">name</var>[, <var class="Arg">path</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the n-th orbit record from the project with project <code class="code">"name"</code></p>
<p>By default the function searches the current working directory for the saved project folder and searches inside this for the n-th orbit. If no such orbit exists it returns <code class="keyw">fail</code>. If an optional argument <var class="Arg">path</var> is provided then it searches this path for a folder with the name specified (note that path expects a <code class="code">Directory</code> object). If an orbit exists then it is returned as a record as outlined in the data structure section.</p>
<p><a id="X82F6093885ECD889" name="X82F6093885ECD889"></a></p>
<h5>1.2-17 SaveOrbitToFile</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SaveOrbitToFile</code>( <var class="Arg">orbit</var>, <var class="Arg">n</var>, <var class="Arg">name</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Saves the orbit to filename "<var class="Arg">n</var>" in the directory <code class="code">'_name'</code>. The directory must already exist.</p>
<p><a id="X83EB578D85D98DF5" name="X83EB578D85D98DF5"></a></p>
<h4>1.3 <span class="Heading">Key Data Structures</span></h4>
<p>Many of the above functions require or return key data structures which we aim to document.</p>
<p><a id="X84FDC7BD82227DA8" name="X84FDC7BD82227DA8"></a></p>
<h5>1.3-1 <span class="Heading">The Orbit Record</span></h5>
<p>Many of the functions return or expect an orbit "object". This object is in fact record with the following values:</p>
<ul>
<li><p><code class="code">PrincipalFiniteGroup </code>- the finite group</p>
</li>
<li><p><code class="code">OurG </code>- genus</p>
</li>
<li><p><code class="code">OurR </code>- length of our primary tuple</p>
</li>
<li><p><code class="code">OurN </code>- number of points on which our group acts</p>
</li>
<li><p><code class="code">NumberOfGenerators </code>- 2 <code class="code">OurG</code>+ <code class="code">OurR </code></p>
</li>
<li><p><code class="code">OurFreeGroup </code>- a free group on <code class="code">NumberOfGenerators </code>letters</p>
</li>
<li><p><code class="code">AbsGens </code>- generators for <code class="code">OurFreeGroup</code></p>
</li>
<li><p><code class="code">OurAlpha </code> - generators of <code class="code">OurFreeGroup</code>corresponding to the <span class="SimpleMath">α_i</span> type loops in the fundamental group ( the first <span class="SimpleMath">g</span> elements of <code class="code">AbsGens</code>)</p>
</li>
<li><p><code class="code">OurBeta </code>- elements of <code class="code">OurFreeGroup </code>corresponding to <span class="SimpleMath">β</span> type loops</p>
</li>
<li><p><code class="code">OurGamma </code>- generators of <code class="code">OurFreeGroup </code>corresponding to the loops around branch points</p>
</li>
<li><p><code class="code">TupleTable </code>- a table containing all the tuples in the orbit</p>
</li>
<li><p><code class="code">HashLength</code></p>
</li>
<li><p><code class="code">Hash</code></p>
</li>
<li><p><code class="code">PrimeCode</code></p>
</li>
<li><p><code class="code">OurAction</code></p>
</li>
<li><p><code class="code">ActionOnOrbit</code></p>
</li>
<li><p><code class="code">MinimizationTree</code>- minimization structure</p>
</li>
<li><p><code class="code">MinimumSet</code>- minimizaton structure</p>
</li>
</ul>
<p><a id="X7CEE3F9180497635" name="X7CEE3F9180497635"></a></p>
<h5>1.3-2 <span class="Heading">The Tuple Table</span></h5>
<p>The tuple table is a list. Each element of the list is a record with the names, tuple and next. If <code class="code">orbit</code> is an orbit object then <code class="code">orbit.TupleTable[n].tuple</code> returns the tuple at index <span class="SimpleMath">n</span> of the tuple table.</p>
<p><a id="X81D1E049865AE89E" name="X81D1E049865AE89E"></a></p>
<h4>1.4 <span class="Heading">A Sample Session</span></h4>
<p>We demonstate how one might use the package.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">group:=AlternatingGroup(5);</span>
Alt( [ 1 .. 5 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">tuple:=[ (1,2)(3,4), (1,2)(3,4), (1,2)(3,4) ];</span>
[ (1,2)(3,4), (1,2)(3,4), (1,2)(3,4) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">orbits:=AllMCOrbits(group,1,tuple);;</span>
Total Number of Tuples: 189120
Collecting 20 random tuples... done
Cleaning done; 20 random tuples remaining
Orbit 1:
Length=3072
Generating Tuple =[ (1,2,4,5,3), (1,4,5,2,3), (1,2)(4,5),
(1,4)(2,3), (2,5)(3,4) ]
Generated subgroup size=60
Centralizer size=1
4800 tuples remaining
Cleaning current orbit...
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
Collecting 20 random tuples... done
Cleaning orbit 1
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
Collecting 40 random tuples... done
Cleaning orbit 1
Cleaning a list of 40 tuples
Random Tuples Remaining: 3
Cleaning done; 3 random tuples remaining
Orbit 2:
Length=32
Generating Tuple =[ (1,4)(2,3), (1,2)(3,4), (1,4)(2,3), (1,2)(3,4),
(1,3)(2,4) ]
Generated subgroup size=4
Centralizer size=4
4320 tuples remaining
Cleaning current orbit...
Cleaning a list of 3 tuples
Random Tuples Remaining: 2
Cleaning done; 2 random tuples remaining
Orbit 3:
Length=72
Generating Tuple =[ (1,5,2), (1,3,2), (1,2)(3,5), (1,3)(2,5),
(1,3)(2,5) ]
Generated subgroup size=12
Centralizer size=1
0 tuples remaining
Cleaning current orbit...
Cleaning a list of 2 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
<span class="GAPprompt">gap></span> <span class="GAPinput"># Check we have as many orbits as it says...</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(orbits);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput"># Inspect the first orbit..</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">orb1:=orbits[1];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># How long is orb1?</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(orb1.TupleTable);</span>
3072
<span class="GAPprompt">gap></span> <span class="GAPinput"># Select element 42 ...</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SelectTuple(orb1, 42);</span>
[ (1,3,4), (1,5,3,2,4), (1,5)(2,4), (1,2)(3,5), (2,3)(4,5) ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># Save the orbit to a file...</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SaveOrbitToFile(orb1, 1, "test");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">#If the folder doesn't exist we get an error..</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SaveOrbitToFile(orb1, 1, "foo");</span>
AppendTo: cannot open '_foo/1' for output at
CallFuncList( APPEND_TO, arg );
<span class="GAPprompt">gap></span> <span class="GAPinput">#</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># Now we try find generating orbits </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">group:=SymmetricGroup(5);</span>
Sym( [ 1 .. 5 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput"># And we will save them using the `SaveOrbit` option</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratingMCOrbits(group,1,tuple : SaveOrbit:="example");;</span>
Total Number of Tuples: 607680
Collecting 20 generating tuples .. done
Cleaning done; 20 random tuples remaining
Orbit 1:
Length=5064
Generating Tuple =[ (1,3,2,5), (2,4,3), (1,4)(3,5), (1,3)(2,5),
(1,4)(3,5) ]
Generated subgroup size=120
Saving orbit to file _example/0
Centralizer size=1
0 tuples remaining
Cleaning current orbit...
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
<span class="GAPprompt">gap></span> <span class="GAPinput">generatingorbits:=last;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># How many generating orbits are there?</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(generatingorbits);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput"># Is this orbit equal to the other one we found earlier</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEqualOrbit(orb1, generatingorbits[1]);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput"># We can reload the orbits...</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">orb2:=RestoreOrbitFromFile(0, "example");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(orb2.TupleTable);</span>
5064
</pre></div>
<p><a id="X7A3C63AC854BCF4C" name="X7A3C63AC854BCF4C"></a></p>
<h4>1.5 <span class="Heading">An Application</span></h4>
<p>This section describes an application of the package.</p>
<p>Let <span class="SimpleMath">X</span> be a compact Riemann surface of genus <span class="SimpleMath">g</span> and <span class="SimpleMath">f: X → P^1C</span> be a meromorphic function of degree <span class="SimpleMath">n</span>. Let <span class="SimpleMath">B</span> be the set of branch points for <span class="SimpleMath">f</span> and fix a basepoint <span class="SimpleMath">b_0 ∈ P^1C- B</span>. The fundamental group <span class="SimpleMath">π_1(P^1 C - B, b_0)</span> acts transitively on the fibre <span class="SimpleMath">f^-1(b_0)</span> and this corresponds to a representation</p>
<p class="pcenter">
f^* :\pi_1(\mathbb{P}^1 \mathbb{C} - B, b_0) \rightarrow S_n
</p>
<p>The image of <span class="SimpleMath">f^*</span> is called the <em>monodromy group</em> of <span class="SimpleMath">(X, f)</span>. The fundamental group of the punctured Riemann sphere is generated by the loops that wind around the points in <span class="SimpleMath">B</span>. Label the branch points <span class="SimpleMath">b_1,...,b_r</span> and let <span class="SimpleMath">τ_i</span> be the image under <span class="SimpleMath">f^*</span> of the loop, <span class="SimpleMath">γ_i ∈ π_1(P^1C - B)</span>, that winds once around the point <span class="SimpleMath">b_i∈ B</span>. Therefore,</p>
<p class="pcenter">
\langle \tau_1, ..., \tau_r \rangle = G
</p>
<p>and</p>
<p class="pcenter">
\tau_1 \cdots \tau_r = 1
</p>
<p>Moreover by the Riemann-Hurwitz formula</p>
<p class="pcenter">
2(n+g-1) = \sum_1^r {ind}( \tau_i)
</p>
<p>where the <span class="SimpleMath">ind(τ_i)</span> is the minimal number of factors to express <span class="SimpleMath">τ_i</span> as a product of transpositions. A set <span class="SimpleMath">t_1, ..., t_r</span> of elements of <span class="SimpleMath">S_n</span> satisfying the Riemann-Hurwitz formula, the product-one condition, and generating some transitive subgroup <span class="SimpleMath">G</span> of <span class="SimpleMath">S_n</span> is called a <em>genus </em> <span class="SimpleMath">g</span> <em>generating system </em> for <span class="SimpleMath">G</span>. Therefore to the meromorphic function <span class="SimpleMath">(X, f)</span> there is an associated genus <span class="SimpleMath">g</span> system. In fact the conjugacy classes of the elements <span class="SimpleMath">τ_i</span> are also determined by <span class="SimpleMath">f</span> -- the collection of conjugacy classes is sometimes called the <em> ramification type</em> of <span class="SimpleMath">f</span>. On the other hand for every genus <span class="SimpleMath">g</span> generating system, <span class="SimpleMath">t = (τ_1, ..., τ_n)</span> for <span class="SimpleMath">G</span> there is Riemann surface of genus <span class="SimpleMath">g</span> and a meromorphic function with associated generating system <span class="SimpleMath">t</span> -- this result is known as <em> Riemann's Existence Theorem</em>.</p>
<p>The question we hope to use our package to answer is: For a given finite group <span class="SimpleMath">G</span> how many meromorphic maps with monodromy group <span class="SimpleMath">G</span> are there? It can be shown -- see <a href="chapBib.html#biBVolklein96">[V\t96]</a> for example -- that determining whether two genus <span class="SimpleMath">g</span> coverings are equivalent corresponds to determining whether their associated genus <span class="SimpleMath">g</span> systems are in the same mapping class orbit ( most literature would refer to mapping class orbits as braid orbits in this case - this is because of the equivalence between the mapping class group of a punctured disc and the braid groups <a href="chapBib.html#biBBirman75">[Bir75]</a>).</p>
<p>Thus for a finite group <span class="SimpleMath">G</span> we can answer the above principal question using the following process:</p>
<ul>
<li><p>For a given finite group <span class="SimpleMath">G</span> the work of Breuer <a href="chapBib.html#biBBreuer00">[Bre00]</a> can be used to calculate all possible ramification types.</p>
</li>
<li><p>Pick a tuple, <span class="SimpleMath">C = (c_1,...,c_r)</span>, of representative elements of the conjugacy classes which correspond to a chosen ramification type as calculated in the previous step.</p>
</li>
<li><p>Use the function <code class="code">GeneratingMCOrbits(G, 0, [c1,...,cr])</code> to calculate the number of mapping class orbits. Note that the genus argument is <span class="SimpleMath">0</span> because this is the genus of <span class="SimpleMath">P^1C</span>.</p>
</li>
</ul>
<p>For more information on this process and the underlying theory see <a href="chapBib.html#biBMSV">[MSSV02]</a> and <a href="chapBib.html#biBVolklein96">[V\t96]</a>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap0.html">[Previous Chapter]</a> <a href="chapA.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chapA.html">A</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.25 Sekunden
¤
*© Formatika GbR, Deutschland
|
|
2026-11-01
|
|
|
|
|
Neuigkeiten |
| Aktuelles |
| Motto des Tages |
|
Open Source Software |
|
|
|
Jenseits des Üblichen ....
|
|
Besucherstatistik |
|
|
| Statistik |
| #Sources=1104856 |
| #Domains=417375 |
|
|
