Quelle chap8.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/rcwa/doc/chap8.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 (RCWA) - Chapter 8: The Algorithms Implemented in RCWA</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="chap8" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="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="chap7.html">[Previous Chapter]</a> <a href="chap9.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap8_mj.html">[MathJax on]</a></p>
<p><a id="X79EA0B717B045756" name="X79EA0B717B045756"></a></p>
<div class="ChapSects"><a href="chap8.html#X79EA0B717B045756">8 <span class="Heading">The Algorithms Implemented in RCWA</span></a>
</div>
<h3>8 <span class="Heading">The Algorithms Implemented in RCWA</span></h3>
<p>This chapter lists brief descriptions of the algorithms and methods implemented in this package. These descriptions are kept very informal and terse, and some of them provide only rudimentary information. They are listed in alphabetical order. The word <q>trivial</q> as a description means that essentially nothing is done except of performing I/O operations, storing or recalling one or several values or doing very basic computations, and <q>straightforward</q> means that no sophisticated algorithm is used. Note that <q>trivial</q> and <q>straightforward</q> are to be read as <em>mathematically</em> trivial respectively straightforward, and that the code of a function or method attributed in this way can still be reasonably long and complicated. Longer and better descriptions of <em>some</em> of the algorithms and methods can be found in <a href="chapBib.html#biBKohl08b">[Koh08]</a>.</p>
<dl>
<dt><strong class="Mark">
<code class="code">ActionOnRespectedPartition(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q> after having computed a respected partition by <code class="code">RespectedPartition</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">AllElementsOfCTZWithGivenModulus(<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>This function first determines a list of all unordered partitions <span class="SimpleMath">mathcalP</span> of ℤ into <var class="Arg">m</var> residue classes. Then for any such partition <span class="SimpleMath">mathcalP</span> it runs a loop over the elements of the symmetric group of degree <var class="Arg">m</var>. For any <span class="SimpleMath">σ ∈ S_m</span> and any partition <span class="SimpleMath">mathcalP</span> it constructs the element of <span class="SimpleMath">CT(Z)</span> with modulus dividing <span class="SimpleMath">m</span> which maps the ordered partition <span class="SimpleMath">{0(m), 1(m), dots, m-1(m)}</span> to the ordered partition obtained from <span class="SimpleMath">mathcalP</span> by permuting the residue classes with <span class="SimpleMath">σ</span>. Finally it discards the elements whose modulus is a proper divisor of <var class="Arg">m</var>, and returns the <q>rest</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Ball(<var class="Arg">G</var>,<var class="Arg">g</var>,<var class="Arg">r</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Ball(<var class="Arg">G</var>,<var class="Arg">p</var>,<var class="Arg">r</var>,<var class="Arg">act</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassPairs(<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Runs a loop over all 4-tuples of nonnegative integers less than <var class="Arg">m</var>, and filters by congruence criteria and ordering of the entries.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassReflection(<var class="Arg">r</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassRotation(<var class="Arg">r</var>,<var class="Arg">m</var>,<var class="Arg">u</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassShift(<var class="Arg">r</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassTransposition(<var class="Arg">r1</var>,<var class="Arg">m1</var>,<var class="Arg">r2</var>,<var class="Arg">m2</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassWiseOrderPreservingOn(<var class="Arg">f</var>)</code>, etc.
</strong></dt>
<dd><p>Forms the union of the residue classes modulo the modulus of <var class="Arg">f</var> in whose corresponding coefficient triple the first entry is positive, zero or negative, respectively.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Coefficients(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">CommonRightInverse(<var class="Arg">l</var>,<var class="Arg">r</var>)</code>
</strong></dt>
<dd><p>See <code class="code">RightInverse</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">CT(<var class="Arg">R</var>)</code>
</strong></dt>
<dd><p>Attributes and properties are set according to <a href="chapBib.html#biBKohl09">[Koh10]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">CycleRepresentativesAndLengths(<var class="Arg">g</var>,<var class="Arg">S</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">CyclesOnFiniteOrbit(<var class="Arg">G</var>,<var class="Arg">g</var>,<var class="Arg">n</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DecreasingOn(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Forms the union of the residue classes which are determined by the coefficients as indicated.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DerivedSubgroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>No genuine method -- <strong class="pkg">GAP</strong> Library methods already work for tame groups.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Determinant(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Evaluation of the given expression. For the mathematical meaning (epimorphism!), see Theorem 2.11.9 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DifferencesList(<var class="Arg">l</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DirectProduct(<var class="Arg">G1</var>,<var class="Arg">G2</var>, ... )</code>
</strong></dt>
<dd><p>Restricts the groups <var class="Arg">G1</var>, <var class="Arg">G2</var>, ... to disjoint residue classes. See <code class="code">Restriction</code> and Corollary 2.3.3 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Display(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DistanceToNextSmallerPointInOrbit(<var class="Arg">G</var>,<var class="Arg">n</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q> -- computes balls of radius <span class="SimpleMath">r</span> about <var class="Arg">n</var> for <span class="SimpleMath">r = 1, 2, dots</span> until a point smaller than <span class="SimpleMath">n</span> is found.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Divisor(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Lcm of coefficients, as indicated.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DrawGrid(<var class="Arg">U</var>,<var class="Arg">range_y</var>,<var class="Arg">range_x</var>,<var class="Arg">filename</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">DrawOrbitPicture</code>
</strong></dt>
<dd><p>Compute spheres of radius <span class="SimpleMath">1, dots, r</span> around the given point(s). Choose the origin either in the lower left corner of the picture (if all points lie in the first quadrant) or in the middle of the picture (if they don't). Mark points of the ball with black pixels in case of a monochrome picture. Choose colors from the given palette depending on the distance from the starting points in case of a colored picture.
</dd>
<dt><strong class="Mark">
<code class="code">EpimorphismFromFpGroup(<var class="Arg">G</var>,<var class="Arg">r</var>)</code>
</strong></dt>
<dd><p>Computes orders of elements in the ball of radius <var class="Arg">r</var> about 1 in <var class="Arg">G</var>, and uses the corresponding relations if they affect the abelian invariants of <var class="Arg">G</var>, <var class="Arg">G', G'', etc..
</dd>
<dt><strong class="Mark">
<code class="code">Exponent(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Check whether <var class="Arg">G</var> is finite. If it is, then use the <strong class="pkg">GAP</strong> Library method, applied to <code class="code">Image(IsomorphismPermGroup(<var class="Arg">G</var>))</code>. Check whether <var class="Arg">G</var> is tame. If yes, return <code class="code">infinity</code>. If not, run a loop over <var class="Arg">G</var> until finding an element of infinite order. Once one is found, return <code class="code">infinity</code>.</p>
<p>The final loop to find a non-torsion element can be left away under the assumption that any finitely generated wild rcwa group has a wild element. It looks likely that this holds, but currently the author does not know a proof.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ExtRepOfObj(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">FactorizationIntoCSCRCT(<var class="Arg">g</var>)</code>,
<code class="code">Factorization(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>The method used here is rather sophisticated, and will likely some time be published elsewhere. At the moment termination is not guaranteed, but in case of termination the result is certain. The strategy is roughly first to make the mapping class-wise order-preserving and balanced, and then to remove all prime factors from multiplier and divisor one after the other in decreasing order by dividing by appropriate class transpositions. The remaining integral mapping can be factored in a similar way as a permutation of a finite set can be factored into transpositions.</p>
</dd>
<dt><strong class="Mark">
<code class="code">FactorizationOnConnectedComponents(<var class="Arg">f</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Calls <strong class="pkg">GRAPE</strong> to get the connected components of the transition graph, and then computes a partition of the suitably <q>blown up</q> coefficient list corresponding to the connected components.</p>
</dd>
<dt><strong class="Mark">
<code class="code">FixedPointsOfAffinePartialMappings(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">FixedResidueClasses(<var class="Arg">g</var>,<var class="Arg">maxmod</var>)</code>,
<code class="code">FixedResidueClasses(<var class="Arg">G</var>,<var class="Arg">maxmod</var>)</code>
</strong></dt>
<dd><p>Runs a loop over all moduli <span class="SimpleMath">m ≤</span> <var class="Arg">maxmod</var> and all residues <span class="SimpleMath">r</span> modulo these moduli, and selects those residue classes <span class="SimpleMath">r(m)</span> which are mapped to itself by <var class="Arg">g</var>, respectively, by all generators of <var class="Arg">G</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">FloatQuotientsList(<var class="Arg">l</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">GluckTaylorInvariant(<var class="Arg">a</var>)</code>
</strong></dt>
<dd><p>Evaluation of the given expression.</p>
</dd>
<dt><strong class="Mark">
<code class="code">GroupByResidueClasses(<var class="Arg">classes</var>)</code>
</strong></dt>
<dd><p>Finds all pairs of residue classes in the list <var class="Arg">classes</var> which are disjoint, forms the corresponding class transpositions and returns the group generated by them.</p>
</dd>
<dt><strong class="Mark">
<code class="code">GuessedDivergence(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Numerical computation of the limit of some series, which seems to converge <q>often</q>. Caution!!!</p>
</dd>
<dt><strong class="Mark">
<code class="code">Image(<var class="Arg">f</var>)</code>, <code class="code">Image(<var class="Arg">f</var>,<var class="Arg">S</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q> if one can compute images of residue classes under affine mappings and unite and intersect residue classes (Chinese Remainder Theorem). See Lemma 1.2.1 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ImageDensity(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Evaluation of the given expression.</p>
</dd>
<dt><strong class="Mark">
<code class="code"><var class="Arg">g</var> in <var class="Arg">G</var></code> (membership test for rcwa groups)
</strong></dt>
<dd><p>Test whether the mapping <var class="Arg">g</var> or its inverse is in the list of generators of <var class="Arg">G</var>. If it is, return <code class="code">true</code>. Test whether its prime set is a subset of the prime set of <var class="Arg">G</var>. If not, return <code class="code">false</code>. Test whether the multiplier or the divisor of <var class="Arg">g</var> has a prime factor which does not divide the multiplier of <var class="Arg">G</var>. If yes, return <code class="code">false</code>. Test if <var class="Arg">G</var> is class-wise order-preserving, and <var class="Arg">g</var> is not. If so, return <code class="code">false</code>. Test if the sign of <var class="Arg">g</var> is -1 and all generators of <var class="Arg">G</var> have sign 1. If yes, return <code class="code">false</code>. Test if <var class="Arg">G</var> is class-wise order-preserving, all generators of <var class="Arg">G</var> have determinant 0 and <var class="Arg">g</var> has determinant <span class="SimpleMath">≠ 0</span>. If yes, return <code class="code">false</code>. Test whether the support of <var class="Arg">g</var> is a subset of the support of <var class="Arg">G</var>. If not, return <code class="code">false</code>. Test whether <var class="Arg">G</var> fixes the nonnegative integers setwise, but <var class="Arg">g</var> does not. If yes, return <code class="code">false</code>.</p>
<p>If <var class="Arg">G</var> is tame, proceed as follows: Test whether the modulus of <var class="Arg">g</var> divides the modulus of <var class="Arg">G</var>. If not, return <code class="code">false</code>. Test whether <var class="Arg">G</var> is finite and <var class="Arg">g</var> has infinite order. If so, return <code class="code">false</code>. Test whether <var class="Arg">g</var> is tame. If not, return <code class="code">false</code>. Compute a respected partition <code class="code">P</code> of <var class="Arg">G</var> and the finite permutation group <code class="code">H</code> induced by <var class="Arg">G</var> on it (see <code class="code">RespectedPartition</code>). Check whether <var class="Arg">g</var> permutes <code class="code">P</code>. If not, return <code class="code">false</code>. Let <code class="code">h</code> be the permutation induced by <var class="Arg">g</var> on <code class="code">P</code>. Check whether <code class="code">h</code> lies in <code class="code">H</code>. If not, return <code class="code">false</code>. Compute an element <code class="code">g1</code> of <var class="Arg">G</var> which acts on <code class="code">P</code> like <var class="Arg">g</var>. For this purpose, factor <var class="Arg">h</var> into generators of <code class="code">H</code> using <code class="code">PreImagesRepresentative</code>, and compute the corresponding product of generators of <var class="Arg">G</var>. Let <code class="code">k := g/g1</code>. The mapping <code class="code">k</code> is always integral. Compute the kernel <code class="code">K</code> of the action of <var class="Arg">G</var> on <code class="code">P</code> using <code class="code">KernelOfActionOnRespectedPartition</code>. Check whether <code class="code">k</code> lies in <code class="code">K</code>. This is done using the package <strong class="pkg">Polycyclic</strong> <a href="chapBib.html#biBPolycyclic">[EHN13]</a>, and uses an isomorphism from a supergroup of <code class="code">K</code> which is isomorphic to the <code class="code">|P|</code>-fold direct product of the infinite dihedral group and which always contains <code class="code">k</code> to a polycyclically presented group. If <code class="code">k</code> lies in <code class="code">K</code>, return <code class="code">true</code>, otherwise return <code class="code">false</code>.</p>
<p>If <var class="Arg">G</var> is not tame, proceed as follows: Look for finite orbits of <var class="Arg">G</var>. If some are found, test whether <var class="Arg">g</var> acts on them, and whether the induced permutations lie in the permutation groups induced by <var class="Arg">G</var>. If for one of the examined orbits one of the latter two questions has a negative answer, then return <code class="code">false</code>. Look for a positive integer <span class="SimpleMath">m</span> such that <var class="Arg">g</var> does not leave a partition of ℤ into unions of residue classes (mod <span class="SimpleMath">m</span>) invariant which is fixed by <var class="Arg">G</var>. If successful, return <code class="code">false</code>. If not, try to factor <var class="Arg">g</var> into generators of <var class="Arg">G</var> using <code class="code">PreImagesRepresentative</code>. If successful, return <code class="code">true</code>. If <var class="Arg">g</var> is in <var class="Arg">G</var>, this terminates after a finite number of steps. Both run time and memory requirements are exponential in the word length. If <var class="Arg">g</var> is not in <var class="Arg">G</var> at this stage, the method runs into an infinite loop.</p>
</dd>
<dt><strong class="Mark">
<code class="code"><var class="Arg">f</var> in <var class="Arg">M</var></code> (membership test for rcwa monoids)
</strong></dt>
<dd><p>Test whether the mapping <var class="Arg">f</var> is in the list of generators of <var class="Arg">G</var>. If it is, return <code class="code">true</code>. Test whether the multiplier of <var class="Arg">f</var> is zero, but all generators of <var class="Arg">M</var> have nonzero multiplier. If yes, return <code class="code">false</code>. Test if neither <var class="Arg">f</var> nor any generator of <var class="Arg">M</var> has multiplier zero. If so, check whether the prime set of <var class="Arg">f</var> is a subset of the prime set of <var class="Arg">M</var>, and whether the set of prime factors of the multiplier of <var class="Arg">f</var> is a subset of the union of the sets of prime factors of the multipliers of the generators of <var class="Arg">M</var>. If one of these is not the case, return <code class="code">false</code>. Check whether the set of prime factors of the divisor of <var class="Arg">f</var> is a subset of the union of the sets of prime factors of the divisors of the generators of <var class="Arg">M</var>. If not, return <code class="code">false</code>. If the underlying ring is ℤ or a semilocalization thereof, then check whether <var class="Arg">f</var> is not class-wise order-preserving, but <var class="Arg">M</var> is. If so, return <code class="code">false</code>.</p>
<p>If <var class="Arg">f</var> is not injective, but all generators of <var class="Arg">M</var> are, then return <code class="code">false</code>. If <var class="Arg">f</var> is not surjective, but all generators of <var class="Arg">M</var> are, then return <code class="code">false</code>. If the support of <var class="Arg">f</var> is not a subset of the support of <var class="Arg">M</var>, then return <code class="code">false</code>. If <var class="Arg">f</var> is not sign-preserving, but <var class="Arg">M</var> is, then return <code class="code">false</code>. Check whether <var class="Arg">M</var> is tame. If so, then return <code class="code">false</code> provided that one of the following three conditions hold: 1. The modulus of <var class="Arg">f</var> does not divide the modulus of <var class="Arg">M</var>. 2. <var class="Arg">f</var> is not tame. 3. <var class="Arg">M</var> is finite, and <var class="Arg">f</var> is bijective and has infinite order. If membership has still not been decided, use <code class="code">ShortOrbits</code> to look for finite orbits of <var class="Arg">M</var>, and check whether <var class="Arg">f</var> fixes all of them setwise. If a finite orbit is found which <var class="Arg">f</var> does not map to itself, then return <code class="code">false</code>.</p>
<p>Finally compute balls of increasing radius around 1 until <var class="Arg">f</var> is found to lie in one of them. If that happens, return <code class="code">true</code>. If <var class="Arg">f</var> is an element of <var class="Arg">M</var>, this will eventually terminate, but if at this stage <var class="Arg">f</var> is not an element of <var class="Arg">M</var>, this will run into an infinite loop.</p>
</dd>
<dt><strong class="Mark">
<code class="code"><var class="Arg">point</var> in <var class="Arg">orbit</var></code> (membership test for orbits)
</strong></dt>
<dd><p>Uses the equality test for orbits: The orbit equality test computes balls of increasing radius around the orbit representatives until they intersect non-trivially. Once they do so, it returns <code class="code">true</code>. If it finds that one or both of the orbits are finite, it makes use of that information, and returns <code class="code">false</code> if appropriate. In between, i.e. after having computed balls to a certain extent depending on the properties of the group, it chooses a suitable modulus <span class="SimpleMath">m</span> and computes orbits (modulo <span class="SimpleMath">m</span>). If the representatives of the orbits to be compared belong to different orbits (mod <span class="SimpleMath">m</span>), it returns <code class="code">false</code>. If this is not the case although the orbits are different, the equality test runs into an infinite loop.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IncreasingOn(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Forms the union of the residue classes which are determined by the coefficients as indicated.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Index(<var class="Arg">G</var>,<var class="Arg">H</var>)</code>
</strong></dt>
<dd><p>In general, i.e. if the underlying ring is not ℤ, proceed as follows: If both groups <var class="Arg">G</var> and <var class="Arg">H</var> are finite, return the quotient of their orders. If <var class="Arg">G</var> is infinite, but <var class="Arg">H</var> is finite, return <code class="code">infinity</code>. Otherwise return the number of right cosets of <var class="Arg">H</var> in <var class="Arg">G</var>, computed by the <strong class="pkg">GAP</strong> Library function <code class="code">RightCosets</code>.</p>
<p>If the underlying ring is ℤ, do additionally the following before attempting to compute the list of right cosets: If the group <var class="Arg">G</var> is class-wise order-preserving, check whether one of its generators has nonzero determinant, and whether all generators of <var class="Arg">H</var> have determinant zero. If so, then return <code class="code">infinity</code>. Check whether <var class="Arg">H</var> is tame, but <var class="Arg">G</var> is not. If so, then return <code class="code">infinity</code>. If <var class="Arg">G</var> is tame, then check whether the rank of the largest free abelian subgroup of the kernel of the action of <var class="Arg">G</var> on a respected partition is higher than the corresponding rank for <var class="Arg">H</var>. For this check, use <code class="code">RankOfKernelOfActionOnRespectedPartition</code>. If it is, then return <code class="code">infinity</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Induction(<var class="Arg">g</var>,<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Computes <code class="code">f * g * RightInverse(<var class="Arg">f</var>)</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Induction(<var class="Arg">G</var>,<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Gets a set of generators by applying <code class="code">Induction(<var class="Arg">g</var>,<var class="Arg">f</var>)</code> to the generators <var class="Arg">g</var> of <var class="Arg">G</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">InjectiveAsMappingFrom(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>The function starts with the entire source of <var class="Arg">f</var> as <q>preimage</q> <code class="code">pre</code> and the empty set as <q>image</q> <code class="code">im</code>. It loops over the residue classes (mod <code class="code">Mod(<var class="Arg">f</var>)</code>). For any such residue class <code class="code">cl</code> the following is done: Firstly, the image of <code class="code">cl</code> under <var class="Arg">f</var> is added to <code class="code">im</code>. Secondly, the intersection of the preimage of the intersection of the image of <code class="code">cl</code> under <var class="Arg">f</var> and <code class="code">im</code> under <var class="Arg">f</var> and <code class="code">cl</code> is subtracted from <code class="code">pre</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IntegralConjugate(<var class="Arg">f</var>)</code>,
<code class="code">IntegralConjugate(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Uses the algorithm described in the proof of Theorem 2.5.14 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IntegralizingConjugator(<var class="Arg">f</var>)</code>,
<code class="code">IntegralizingConjugator(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Uses the algorithm described in the proof of Theorem 2.5.14 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Inverse(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Essentially inversion of affine mappings. See Lemma 1.3.1, Part (b) in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsBalanced(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Checks whether the sets of prime factors of the multiplier and the divisor of <var class="Arg">f</var> are the same.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsBijective(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>, respectively, see <code class="code">IsInjective</code> and <code class="code">IsSurjective</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsClassReflection(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Computes the support of <var class="Arg">g</var>, and compares <var class="Arg">g</var> with the corresponding class reflection.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsClassRotation(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Computes the support of <var class="Arg">g</var>, extracts the possible rotation factor from the coefficients and compares <var class="Arg">g</var> with the corresponding class rotation.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsClassShift(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Computes the support of <var class="Arg">g</var>, and compares <var class="Arg">g</var> with the corresponding class shift.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsClassTransposition(<var class="Arg">g</var>),
IsGeneralizedClassTransposition(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Computes the support of <var class="Arg">g</var>, writes it as a disjoint union of two residue classes and compares <var class="Arg">g</var> with the class transposition which interchanges them.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsClassWiseOrderPreserving(<var class="Arg">f</var>)</code>,
<code class="code">IsClassWiseTranslating(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsConjugate(RCWA(Integers),<var class="Arg">f</var>,<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Test whether <var class="Arg">f</var> and <var class="Arg">g</var> have the same order, and whether either both or none of them is tame. If not, return <code class="code">false</code>.</p>
<p>If the mappings are wild, use <code class="code">ShortCycles</code> to search for finite cycles not belonging to an infinite series, until their numbers for a particular length differ. This may run into an infinite loop. If it terminates, return <code class="code">false</code>.</p>
<p>If the mappings are tame, use the method described in the proof of Theorem 2.5.14 in <a href="chapBib.html#biBKohl05">[Koh05]</a> to construct integral conjugates of <var class="Arg">f</var> and <var class="Arg">g</var>. Then essentially use the algorithm described in the proof of Theorem 2.6.7 in <a href="chapBib.html#biBKohl05">[Koh05]</a> to compute <q>standard representatives</q> of the conjugacy classes which the integral conjugates of <var class="Arg">f</var> and <var class="Arg">g</var> belong to. Finally compare these standard representatives, and return <code class="code">true</code> if they are equal and <code class="code">false</code> if not.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsInjective(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>See <code class="code">Image</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsIntegral(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsNaturalCT(<var class="Arg">G</var>)</code>,
<code class="code">IsNaturalRCWA(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Only checks a set flag.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsomorphismMatrixGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Uses the algorithm described in the proof of Theorem 2.6.3 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsomorphismPermGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>If the group <var class="Arg">G</var> is finite and class-wise order-preserving, use <code class="code">ActionOnRespectedPartition</code>. If <var class="Arg">G</var> is finite, but not class-wise order-preserving, compute the action on the respected partition which is obtained by splitting any residue class <span class="SimpleMath">r(m)</span> in <code class="code">RespectedPartition(<var class="Arg">G</var>)</code> into three residue classes <span class="SimpleMath">r(3m), r+m(3m), r+2m(3m)</span>. If <var class="Arg">G</var> is infinite, there is no isomorphism to a finite permutation group, thus return <code class="code">fail</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsomorphismRcwaGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>The method for finite groups uses <code class="code">RcwaMapping</code>, Part (d).</p>
<p>The method for free products of finite groups uses the Table-Tennis Lemma (which is also known as <em>Ping-Pong Lemma</em>, cf. e.g. Section II.B. in <a href="chapBib.html#biBLaHarpe00">[dlH00]</a>). It uses regular permutation representations of the factors <span class="SimpleMath">G_r</span> (<span class="SimpleMath">r = 0, dots ,m-1</span>) of the free product on residue classes modulo <span class="SimpleMath">n_r := |G_r|</span>. The basic idea is that since point stabilizers in regular permutation groups are trivial, all non-identity elements map any of the permuted residue classes into their complements. To get into a situation where the Table-Tennis Lemma is applicable, the method computes conjugates of the images of the mentioned permutation representations under rcwa permutations <span class="SimpleMath">σ_r</span> which satisfy <span class="SimpleMath">0(n_r)^σ_r = ℤ ∖ r(m)</span>.</p>
<p>The method for free groups uses an adaptation of the construction given on page 27 in <a href="chapBib.html#biBLaHarpe00">[dlH00]</a> from PSL(2,ℂ) to RCWA(ℤ). As an equivalent for the closed discs used there, the method takes the residue classes modulo two times the rank of the free group.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsOne(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsPerfectGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>If the group <var class="Arg">G</var> is trivial, then return <code class="code">true</code>. Otherwise if it is abelian, then return <code class="code">false</code>.</p>
<p>If the underlying ring is ℤ, then do the following: If one of the generators of <var class="Arg">G</var> has sign -1, then return <code class="code">false</code>. If <var class="Arg">G</var> is class-wise order-preserving and one of the generators has nonzero determinant, then return <code class="code">false</code>.</p>
<p>If <var class="Arg">G</var> is wild, and perfectness has not been decided so far, then give up. If <var class="Arg">G</var> is finite, then check the image of <code class="code">IsomorphismPermGroup(<var class="Arg">G</var>)</code> for perfectness, and return <code class="code">true</code> or <code class="code">false</code> accordingly.</p>
<p>If the group <var class="Arg">G</var> is tame and if it acts transitively on its stored respected partition, then return <code class="code">true</code> or <code class="code">false</code> depending on whether the finite permutation group <code class="code">ActionOnRespectedPartition(<var class="Arg">G</var>)</code> is perfect or not. If <var class="Arg">G</var> does not act transitively on its stored respected partition, then give up.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsPrimeSwitch(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Checks whether the multiplier of <var class="Arg">g</var> is an odd prime, and compares <var class="Arg">g</var> with the corresponding prime switch.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsSignPreserving(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>If <var class="Arg">f</var> is not class-wise order-preserving, then return <code class="code">false</code>. Otherwise let <span class="SimpleMath">c ≥ 1</span> be greater than or equal to the maximum of the absolute values of the coefficients <span class="SimpleMath">b_r(m)</span> of the affine partial mappings of <var class="Arg">f</var>, and check whether the minimum of the image of <span class="SimpleMath">{0, dots, c}</span> under <var class="Arg">f</var> is nonnegative and whether the maximum of the image of <span class="SimpleMath">{-c, dots, -1}</span> under <var class="Arg">f</var> is negative. If both is the case, then return <code class="code">true</code>, otherwise return <code class="code">false</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsSolvableGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>If <var class="Arg">G</var> is abelian, then return <code class="code">true</code>. If <var class="Arg">G</var> is tame, then return <code class="code">true</code> or <code class="code">false</code> depending on whether <code class="code">ActionOnRespectedPartition(<var class="Arg">G</var>)</code> is solvable or not. If <var class="Arg">G</var> is wild, then give up.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsSubset(<var class="Arg">G</var>,<var class="Arg">H</var>)</code> (checking for a subgroup relation)
</strong></dt>
<dd><p>Check whether the set of stored generators of <var class="Arg">H</var> is a subset of the set of stored generators of <var class="Arg">G</var>. If so, return <code class="code">true</code>. Check whether the prime set of <var class="Arg">H</var> is a subset of the prime set of <var class="Arg">G</var>. If not, return <code class="code">false</code>. Check whether the support of <var class="Arg">H</var> is a subset of the support of <var class="Arg">G</var>. If not, return <code class="code">false</code>. Check whether <var class="Arg">G</var> is tame, but <var class="Arg">H</var> is wild. If so, return <code class="code">false</code>.</p>
<p>If <var class="Arg">G</var> and <var class="Arg">H</var> are both tame, then proceed as follows: If the multiplier of <var class="Arg">H</var> does not divide the multiplier of <var class="Arg">G</var>, then return <code class="code">false</code>. If <var class="Arg">H</var> does not respect the stored respected partition of <var class="Arg">G</var>, then return <code class="code">false</code>. Check whether the finite permutation group induced by <var class="Arg">H</var> on <code class="code">RespectedPartition(<var class="Arg">G</var>)</code> is a subgroup of <code class="code">ActionOnRespectedPartition(<var class="Arg">G</var>)</code>. If yes, return <code class="code">true</code>. Check whether the order of <var class="Arg">H</var> is greater than the order of <var class="Arg">G</var>. If so, return <code class="code">false</code>.</p>
<p>Finally use the membership test to check whether all generators of <var class="Arg">H</var> lie in <var class="Arg">G</var>, and return <code class="code">true</code> or <code class="code">false</code> accordingly.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsSurjective(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>See <code class="code">Image</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsTame(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Checks whether the modulus of the group is nonzero.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsTame(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Application of the criteria given in Corollary 2.5.10 and 2.5.12 and Theorem A.8 and A.11 in <a href="chapBib.html#biBKohl05">[Koh05]</a>, as well as of the criteria given in <a href="chapBib.html#biBKohl07b">[Koh07a]</a>. The criterion <q>surjective, but not injective means wild</q> (Theorem A.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>) is the subject of <a href="chapBib.html#biBKohl07a">[Koh07b]</a>. The package <strong class="pkg">GRAPE</strong> is needed for the application of the criterion which says that an rcwa permutation is wild if a transition graph has a weakly-connected component which is not strongly-connected (cf. Theorem A.11 in <a href="chapBib.html#biBKohl05">[Koh05]</a>).</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsTransitive(<var class="Arg">G</var>,Integers)</code>
</strong></dt>
<dd><p>Look for finite orbits, using <code class="code">ShortOrbits</code> on a couple of intervals. If a finite orbit is found, return <code class="code">false</code>. Test if <var class="Arg">G</var> is finite. If yes, return <code class="code">false</code>.</p>
<p>Search for an element <code class="code">g</code> and a residue class <span class="SimpleMath">r(m)</span> such that the restriction of <code class="code">g</code> to <span class="SimpleMath">r(m)</span> is given by <span class="SimpleMath">n ↦ n + m</span>. Then the cyclic group generated by <code class="code">g</code> acts transitively on <span class="SimpleMath">r(m)</span>. The element <code class="code">g</code> is searched among the generators of <var class="Arg">G</var>, its powers, its commutators, powers of its commutators and products of few different generators. The search for such an element may run into an infinite loop, as there is no guarantee that the group has a suitable element.</p>
<p>If suitable <code class="code">g</code> and <span class="SimpleMath">r(m)</span> are found, proceed as follows:</p>
<p>Put <span class="SimpleMath">S := r(m)</span>. Put <span class="SimpleMath">S := S ∪ S^g</span> for all generators <span class="SimpleMath">g</span> of <var class="Arg">G</var>, and repeat this until <span class="SimpleMath">S</span> remains constant. This may run into an infinite loop.</p>
<p>If it terminates: If <span class="SimpleMath">S = ℤ</span>, return <code class="code">true</code>, otherwise return <code class="code">false</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsTransitiveOnNonnegativeIntegersInSupport(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Computes balls about 1 with successively increasing radii, and checks whether the union of the sets where the elements of these balls are decreasing or shifting down equals the support of <var class="Arg">G</var>. If a positive answer is found, transitivity on <q>small</q> points (nonnegative integers less than an explicit bound) is verified.</p>
</dd>
<dt><strong class="Mark">
<code class="code">IsZero(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">KernelOfActionOnRespectedPartition(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>First determine the abelian invariants of the kernel <code class="code">K</code>. For this, compute sufficiently many quotients of orders of permutation groups induced by <var class="Arg">G</var> on refinements of the stored respected partition <code class="code">P</code> by the order of the permutation group induced by <var class="Arg">G</var> on <code class="code">P</code> itself. Then use a random walk through the group <var class="Arg">G</var>. Compute powers of elements encountered along the way which fix <code class="code">P</code>. Translate these kernel elements into elements of a polycyclically presented group isomorphic to the <code class="code">|P|</code>-fold direct product of the infinite dihedral group (<code class="code">K</code> certainly embeds into this group). Use <strong class="pkg">Polycyclic</strong> <a href="chapBib.html#biBPolycyclic">[EHN13]</a> to collect independent <q>nice</q> generators of <code class="code">K</code>. Proceed until the permutation groups induced by <code class="code">K</code> on the refined respected partitions all equal the initially stored quotients.</p>
</dd>
<dt><strong class="Mark">
<code class="code">LargestSourcesOfAffineMappings(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Forms unions of residue classes modulo the modulus of the mapping, whose corresponding coefficient triples are equal.</p>
</dd>
<dt><strong class="Mark">
<code class="code">LaTeXStringRcwaMapping(<var class="Arg">f</var>)</code>,
<code class="code">LaTeXAndXDVI(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Collects residue classes those corresponding coefficient triples are equal.</p>
</dd>
<dt><strong class="Mark">
<code class="code">LikelyContractionCentre(<var class="Arg">f</var>,<var class="Arg">maxn</var>,<var class="Arg">bound</var>)</code>
</strong></dt>
<dd><p>Computes trajectories with starting values from a given interval, until a cycle is reached. Aborts if the trajectory exceeds the prescribed bound. Form the union of the detected cycles.</p>
</dd>
<dt><strong class="Mark">
<code class="code">LoadDatabaseOf...()</code>, <code class="code">LoadRCWAExamples()</code>
</strong></dt>
<dd><p><q>Trivial</q>. -- These functions do nothing more than reading in certain files.</p>
</dd>
<dt><strong class="Mark">
<code class="code">LocalizedRcwaMapping(<var class="Arg">f</var>,<var class="Arg">p</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Log2HTML(<var class="Arg">logfilename</var>)</code>
</strong></dt>
<dd><p>Straightforward string operations.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Loops(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Runs over the residue classes modulo the modulus of <var class="Arg">f</var>, and selects those of them which <var class="Arg">f</var> does not map to themselves, but which intersect non-trivially with their images under <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">MaximalShift(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">MergerExtension(<var class="Arg">G</var>,<var class="Arg">points</var>,<var class="Arg">point</var>)</code>
</strong></dt>
<dd><p>As described in <code class="func">MergerExtension</code> (<a href="chap3.html#X8794913B878DD5C4"><span class="RefLink">3.1-4</span></a>).</p>
</dd>
<dt><strong class="Mark">
<code class="code">Mirrored(<var class="Arg">g</var>)</code>, <code class="code">Mirrored(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Conjugates with <span class="SimpleMath">n ↦ -n - 1</span>, as indicated in the definition.</p>
</dd>
<dt><strong class="Mark">
<code class="code">mKnot(<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>, following the definition given in <a href="chapBib.html#biBKeller99">[Kel99]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Modulus(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Searches for a wild element in the group. If unsuccessful, tries to construct a respected partition (see <code class="code">RespectedPartition</code>).</p>
</dd>
<dt><strong class="Mark">
<code class="code">Modulus(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">MovedPoints(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Needs only forming unions of residue classes and determining fixed points of affine mappings.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Multiplier(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Lcm of coefficients, as indicated.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Multpk(<var class="Arg">f</var>,<var class="Arg">p</var>,<var class="Arg">k</var>)</code>
</strong></dt>
<dd><p>Forms the union of the residue classes modulo the modulus of the mapping, which are determined by the given divisibility criteria for the coefficients of the corresponding affine mapping.</p>
</dd>
<dt><strong class="Mark">
<code class="code">NrClassPairs(<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Relatively straightforward. -- Practical for values of <var class="Arg">m</var> ranging up into the hundreds and corresponding counts of $10^9$ and more.</p>
</dd>
<dt><strong class="Mark">
<code class="code">NrConjugacyClassesOfCTZOfOrder(<var class="Arg">ord</var>)</code>,
</strong></dt>
<dd><p>Evaluation of the expression <code class="code">Length(Filtered(Combinations(DivisorsInt(ord)), l -> l <> [] and Lcm(l) = ord))</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">NrConjugacyClassesOfRCWAZOfOrder(<var class="Arg">ord</var>)</code>
</strong></dt>
<dd><p>The class numbers are taken from Corollary 2.7.1 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ObjByExtRep(<var class="Arg">fam</var>,<var class="Arg">l</var>)</code>
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">One(<var class="Arg">f</var>)</code>, <code class="code">One(<var class="Arg">G</var>)</code>,
</strong></dt>
<dd><p><q>Trivial</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Orbit(<var class="Arg">G</var>,<var class="Arg">pnt</var>,<var class="Arg">gens</var>,<var class="Arg">acts</var>,<var class="Arg">act</var>)</code>
</strong></dt>
<dd><p>Check if the orbit has length less than a certain bound. If so, then return it as a list. Otherwise test whether the group <var class="Arg">G</var> is tame or wild.</p>
<p>If <var class="Arg">G</var> is tame, then test whether <var class="Arg">G</var> is finite. If yes, then compute the orbit by the <strong class="pkg">GAP</strong> Library method. Otherwise proceed as follows: Compute a respected partition <span class="SimpleMath">mathcalP</span> of <var class="Arg">G</var>. Use <span class="SimpleMath">mathcalP</span> to find a residue class <span class="SimpleMath">r(m)</span> which is a subset of the orbit to be computed. In general, <span class="SimpleMath">r(m)</span> will not be one of the residue classes in <span class="SimpleMath">mathcalP</span>, but a subset of one of them. Put <span class="SimpleMath">Ω := r(m)</span>. Unite the set <span class="SimpleMath">Ω</span> with its images under all the generators of <var class="Arg">G</var> and their inverses. Repeat that until <span class="SimpleMath">Ω</span> does not change any more. Return <span class="SimpleMath">Ω</span>.</p>
<p>If <var class="Arg">G</var> is wild, then return an orbit object which stores the group <var class="Arg">G</var>, the representative <var class="Arg">rep</var> and the action <var class="Arg">act</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">OrbitsModulo(<var class="Arg">f</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Uses <strong class="pkg">GRAPE</strong> to compute the connected components of the transition graph.</p>
</dd>
<dt><strong class="Mark">
<code class="code">OrbitsModulo(<var class="Arg">G</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p><q>Straightforward</q>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Order(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Test for <code class="code">IsTame</code>. If the mapping is not tame, then return <code class="code">infinity</code>. Otherwise use Corollary 2.5.10 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">PermutationOpNC(<var class="Arg">sigma</var>,<var class="Arg">P</var>,<var class="Arg">act</var>)</code>
</strong></dt>
<dd><p>Several different methods for different types of arguments, which either provide straightforward optimizations via computing with coefficients directly, or just delegate to <code class="code">PermutationOp</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">PreImage(<var class="Arg">f</var>,<var class="Arg">S</var>)</code>
</strong></dt>
<dd><p>See <code class="code">Image</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">PreImagesRepresentative(<var class="Arg">phi</var>,<var class="Arg">g</var>)</code>, | |
