<?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 6: 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" />
</head>
<body>
<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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<p><a id="X79EA0B717B045756" name="X79EA0B717B045756"></a></p>
<div class="ChapSects"><a href="chap6.html#X79EA0B717B045756">6. <span class="Heading">The Algorithms Implemented in RCWA</span></a>
</div>
<h3>6. <span class="Heading">The Algorithms Implemented in RCWA</span></h3>
<p>This chapter lists brief descriptions of many of the algorithms and methods implemented in this package. These descriptions are kept very informal and short, and some of them provide only rudimentary information. They are listed in alphabetical order. The word "trivial" as a description means that essentially nothing is done except of storing or recalling one or several values, and "straightforward" means that no sophisticated algorithm is used. Note that "trivial" and "straightforward" 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 many of the algorithms and methods can be found in <a href="chapBib.html#biBKohl07a">[Koh07b]</a>.</p>
<dl>
<dt><strong class="Mark">
<code class="code">ActionOnRespectedPartition(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>"Straightforward" after having computed a respected partition by <code class="code">RespectedPartition</code>. One only needs to know how to compute images of residue classes under affine mappings.</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>"Straightforward".</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>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">ClassPairs</code>
</strong></dt>
<dd><p>Run over all 4-tuples, and filter by divisibility criteria, size comparisons, ordering of the entries etc.</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>"Trivial".</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>"Trivial".</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>"Trivial".</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>"Trivial".</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>"Trivial".</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#biBKohl06b">[Koh06a]</a>.</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">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>"Trivial".</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">DrawOrbitPicture</code>
</strong></dt>
<dd><p>Compute spheres of radius 1, dots, r 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.</p>
</dd>
<dt><strong class="Mark">
<code class="code">EpimorphismFromFpGroup(<var class="Arg">G</var>,<var class="Arg">r</var>)</code>
</strong></dt>
<dd><p>If the package <strong class="pkg">FR</strong> <a href="chapBib.html#biBFR">[Bar07]</a> is loaded, then use its function <code class="code">FindGroupRelations</code> to find relations. Otherwise proceed as follows: First compute the ball of radius <var class="Arg">r</var> around 1 in the free group whose rank is the number of stored generators of <var class="Arg">G</var>. Then compute the images of the elements of that ball under the natural projection onto the group <var class="Arg">G</var>. Take pairs of elements of the ball whose images coincide, and add their quotients to the set of known relations. For images which have finite order, add the corresponding power relations. Finally, regardless of whether <strong class="pkg">FR</strong> is present or not, simplify the finitely presented group with the determined relations by the operation <code class="code">IsomorphismSimplifiedFpGroup</code> from the <strong class="pkg">GAP</strong> Library, and return the natural epimorphism from it to <var class="Arg">G</var>.</p>
</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">FactorizationIntoCSCRCT(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>This uses a rather sophisticated method which 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 almost similarly easily 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 "blown up" 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>"Straightforward".</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">GuessedDivergence(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Numerical computation of the limit of some series, which seems to converge "often". 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>"Straightforward" 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 <> 0. 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">[EN06]</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 m such that <var class="Arg">g</var> does not leave a partition of Z into unions of residue classes (mod m) 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 runtime 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 Z 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 nontrivially. 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 m and computes orbits (modulo m). If the representatives of the orbits to be compared belong to different orbits (mod m), 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 Z, 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 Z, 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 "preimage" <code class="code">pre</code> and the empty set as "image" <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">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>)</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>
</strong></dt>
<dd><p>Tests whether the first entry of all coefficient triples is positive.</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 "standard representatives" 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>"Trivial".</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 r(m) in <code class="code">RespectedPartition(<var class="Arg">G</var></code> into three residue classes r(3m), r+m(3m), r+2m(3m). 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 G_r (r = 0, dots ,m-1) of the free product on residue classes modulo n_r := |G_r|. 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 bijective rcwa mappings sigma_r which satisfy 0(n_r)^sigma_r = Z \ r(m).</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,C) to RCWA(Z). 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">IsPerfect(<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 Z, 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 c >= 1 be greater than or equal to the maximum of the absolute values of the coefficients b_r(m) of the affine partial mappings of <var class="Arg">f</var>, and check whether the minimum of the image of 0, dots, c under <var class="Arg">f</var> is nonnegative and whether the maximum of the image of -c, dots, -1 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">IsSolvable(<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 "surjective, but not injective means wild" (Theorem A.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>) is the subject of <a href="chapBib.html#biBKohl06a">[Koh06b]</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 r(m) such that the restriction of <code class="code">g</code> to r(m) is given by n -> n + m. Then the cyclic group generated by <code class="code">g</code> acts transitively on r(m). 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 r(m) are found, proceed as follows:</p>
<p>Put S := r(m). Put S := S cup S^g for all generators g of <var class="Arg">G</var>, and repeat this until S remains constant. This may run into an infinite loop.</p>
<p>If it terminates: If S = Z, return <code class="code">true</code>, otherwise return <code class="code">false</code>.</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">[EN06]</a> to collect independent "nice" 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">LaTeXObj(<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">LocalizedRcwaMapping(<var class="Arg">f</var>,<var class="Arg">p</var>)</code>
</strong></dt>
<dd><p>"Trivial".</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 nontrivially with their images under <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">mKnot(<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>"Straightforward", 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>"Trivial".</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">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">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 mathcalP of <var class="Arg">G</var>. Use mathcalP to find a residue class r(m) which is a subset of the orbit to be computed. In general, r(m) will not be one of the residue classes in mathcalP, but a subset of one of them. Put Omega := r(m). Unite the set Omega with its images under all the generators of <var class="Arg">G</var> and their inverses. Repeat that until Omega does not change any more. Return Omega.</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>"Straightforward".</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">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>,
<code class="code">PreImagesRepresentatives(<var class="Arg">phi</var>,<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>As indicated in the documentation of these methods. The underlying idea to successively compute two balls around 1 and <var class="Arg">g</var> until they intersect nontrivially is standard in computational group theory. For rcwa groups it would mean wasting both memory and runtime to actually compute group elements. Thus only images of tuples of points are computed and stored.</p>
</dd>
<dt><strong class="Mark">
<code class="code">PrimeSet(<var class="Arg">f</var>)</code>,
<code class="code">PrimeSet(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">PrimeSwitch(<var class="Arg">p</var>)</code>
</strong></dt>
<dd><p>Multiplication of rcwa mappings as indicated.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Print(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>"Trivial".</p>
</dd>
<dt><strong class="Mark">
<code class="code"><var class="Arg">f</var>*<var class="Arg">g</var></code>
</strong></dt>
<dd><p>Essentially composition of affine mappings. See Lemma 1.3.1, Part (a) in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Projections(<var class="Arg">G</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Use <code class="code">OrbitsModulo</code> to determine the supports of the images of the epimorphisms to be determined, and use <code class="code">RestrictedPerm</code> to compute the images of the generators of <var class="Arg">G</var> under these epimorphisms.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Random(RCWA(Integers))</code>
</strong></dt>
<dd><p>Computes a product of "randomly" chosen class shifts, class reflections and class transpositions. This seems to be suitable for generating reasonably good examples.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RankOfKernelOfActionOnRespectedPartition(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>This performs basically the first part of the computations done by <code class="code">KernelOfActionOnRespectedPartition</code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RCWA(<var class="Arg">R</var>)</code>
</strong></dt>
<dd><p>Attributes and properties are set according to Theorem 2.1.1, Theorem 2.1.2, Corollary 2.1.6 and Theorem 2.12.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RcwaGroupByPermGroup(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Uses <code class="code">RcwaMapping</code>, Part (d).</p>
</dd>
<dt><strong class="Mark">
<code class="code">RcwaMapping</code>
</strong></dt>
<dd><p>(a)-(c): "trivial", (d): <code class="code">n^perm - n</code> for determining the coefficients, (e): "affine mappings by values at two given points", (f) and (g): "trivial", (h) and (i): correspond to Lemma 2.1.4 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RepresentativeAction(<var class="Arg">G</var>,<var class="Arg">src</var>,<var class="Arg">dest</var>,<var class="Arg">act</var>)</code>,
<code class="code">RepresentativeActionPreImage</code>
</strong></dt>
<dd><p>As indicated in the documentation of these methods. The underlying idea to successively compute two balls around <var class="Arg">src</var> and <var class="Arg">dest</var> until they intersect nontrivially is standard in computational group theory. Words standing for products of generators of <var class="Arg">G</var> are stored for any image of <var class="Arg">src</var> or <var class="Arg">dest</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RepresentativeAction(RCWA(Integers),<var class="Arg">P1</var>,<var class="Arg">P2</var>)</code>
</strong></dt>
<dd><p>Arbitrary mapping: see Lemma 2.1.4 in <a href="chapBib.html#biBKohl05">[Koh05]</a>. Tame mapping: see proof of Theorem 2.8.9 in <a href="chapBib.html#biBKohl05">[Koh05]</a>. The former is almost trivial, while the latter is a bit complicated and takes usually also much more time.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RepresentativeAction(RCWA(Integers),<var class="Arg">f</var>,<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>The algorithm used by <code class="code">IsConjugate</code> constructs actually also an element <code class="code">x</code> such that <code class="code"><var class="Arg">f</var>^x = <var class="Arg">g</var></code>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RespectedPartition(<var class="Arg">f</var>)</code>,
<code class="code">RespectedPartition(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>Uses the algorithm described in the proof of Theorem 2.5.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RespectsPartition(<var class="Arg">G</var>,<var class="Arg">P</var>)</code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">RestrictedPerm(<var class="Arg">g</var>,<var class="Arg">S</var></code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">Restriction(<var class="Arg">g</var>,<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Computes the action of <code class="code">RightInverse(<var class="Arg">f</var>) * g * f</code> on the image of <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Restriction(<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">Restriction(<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">RightInverse(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>"Straightforward" if one knows how to compute images of residue classes under affine mappings, and how to compute inverses of affine mappings.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Root(<var class="Arg">f</var>,<var class="Arg">k</var>)</code>
</strong></dt>
<dd><p>If <var class="Arg">f</var> is bijective, class-wise order-preserving and has finite order:</p>
<p>Find a conjugate of <var class="Arg">f</var> which is a product of class transpositions. Slice cycles prod_i=2^l tau_r_1(m_1),r_i(m_i) of <var class="Arg">f</var> a respected partition mathcalP into cycles prod_i=1^l prod_j=0^k-1 tau_r_1(km_1),r_i+jm_i(km_i) of the <var class="Arg">k</var>-fold length on the refined partition which one gets from mathcalP by decomposing any r_i(m_i) in mathcalP into residue classes (mod km_i). Finally conjugate the resulting permutation back.</p>
<p>Other cases seem to be more difficult and are currently not covered.</p>
</dd>
<dt><strong class="Mark">
<code class="code">RotationFactor(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>"Trivial".</p>
</dd>
<dt><strong class="Mark">
<code class="code">SemilocalizedRcwaMapping(<var class="Arg">f</var>,<var class="Arg">pi</var>)</code>
</strong></dt>
<dd><p>"Trivial".</p>
</dd>
<dt><strong class="Mark">
<code class="code">ShortCycles(<var class="Arg">f</var>,<var class="Arg">maxlng</var>)</code>
</strong></dt>
<dd><p>Looks for fixed points of affine partial mappings of powers of <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">ShortOrbits(<var class="Arg">G</var>,<var class="Arg">S</var>,<var class="Arg">maxlng</var>)</code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">Sign(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>Evaluation of the given expression. For the mathematical meaning (epimorphism!), see Theorem 2.12.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Sinks(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Computes the strongly connected components of the transition graph by the function <code class="code">STRONGLY_CONNECTED_COMPONENTS_DIGRAPH</code>, and selects those which are proper subsets of their preimages and proper supersets of their images under <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Size(<var class="Arg">G</var>)</code> (order of an rcwa group)
</strong></dt>
<dd><p>Test whether one of the generators of the group <var class="Arg">G</var> has infinite order. If so, return <code class="code">infinity</code>. Test whether the group <var class="Arg">G</var> is tame. If not, return <code class="code">infinity</code>. Test whether <code class="code">RankOfKernelOfActionOnRespectedPartition(<var class="Arg">G</var>)</code> is nonzero. If so, return <code class="code">infinity</code>. Otherwise if <var class="Arg">G</var> is class-wise order-preserving, return the size of the permutation group induced on the stored respected partition. If <var class="Arg">G</var> is not class-wise order-preserving, return the size of the permutation group induced on the refinement of the stored respected partition which is obtained by splitting each residue class into three residue classes with equal moduli.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Size(<var class="Arg">M</var>)</code> (order of an rcwa monoid)
</strong></dt>
<dd><p>Check whether <var class="Arg">M</var> is in fact an rcwa group. If so, use the method for rcwa groups instead. Check whether one of the generators of <var class="Arg">M</var> is surjective, but not injective. If so, return <code class="code">infinity</code>. Check whether for all generators f of <var class="Arg">M</var>, the image of the union of the loops of f under f is finite. If not, return <code class="code">infinity</code>. Check whether one of the generators of <var class="Arg">M</var> is bijective and has infinite order. If so, return <code class="code">infinity</code>. Check whether one of the generators of <var class="Arg">M</var> is wild. If so, return <code class="code">infinity</code>. Apply the above criteria to the elements of the ball of radius 2 around 1, and return <code class="code">infinity</code> if appropriate. Finally attempt to compute the list of elements of <var class="Arg">M</var>. If this is successful, return the length of the resulting list.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Sources(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>Computes the strongly connected components of the transition graph by the function <code class="code">STRONGLY_CONNECTED_COMPONENTS_DIGRAPH</code>, and selects those which are proper supersets of their preimages and proper subsets of their images under <var class="Arg">f</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">SplittedClassTransposition(<var class="Arg">ct</var>,<var class="Arg">k</var>)</code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">StructureDescription(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>This method uses a combination of techniques to obtain some basic information on the structure of an rcwa group. The returned description reflects the way the group has been built (<code class="code">DirectProduct</code>, <code class="code">WreathProduct</code>, etc.).</p>
</dd>
<dt><strong class="Mark">
<code class="code"><var class="Arg">f</var>+<var class="Arg">g</var></code>
</strong></dt>
<dd><p>Pointwise addition of affine mappings.</p>
</dd>
<dt><strong class="Mark">
<code class="code">Support(<var class="Arg">G</var>)</code>
</strong></dt>
<dd><p>"Straightforward".</p>
</dd>
<dt><strong class="Mark">
<code class="code">Trajectory(<var class="Arg">f</var>,<var class="Arg">n</var>,...)</code>
</strong></dt>
<dd><p>Iterated application of an rcwa mapping. In the methods computing "accumulated coefficients", additionally composition of affine mappings.</p>
</dd>
<dt><strong class="Mark">
<code class="code">TransitionGraph(<var class="Arg">f</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>"Straightforward" -- just check a sufficiently long interval.</p>
</dd>
<dt><strong class="Mark">
<code class="code">TransitionMatrix(<var class="Arg">f</var>,<var class="Arg">m</var>)</code>
</strong></dt>
<dd><p>Evaluation of the given expression.</p>
</dd>
<dt><strong class="Mark">
<code class="code">TransposedClasses(<var class="Arg">g</var>)</code>
</strong></dt>
<dd><p>"Trivial".</p>
</dd>
<dt><strong class="Mark">
<code class="code">View(<var class="Arg">f</var>)</code>
</strong></dt>
<dd><p>"Trivial".</p>
</dd>
<dt><strong class="Mark">
<code class="code">WreathProduct(<var class="Arg">G</var>,<var class="Arg">P</var>)</code>
</strong></dt>
<dd><p>Uses <code class="code">DirectProduct</code> to embed the <code class="code">DegreeAction(<var class="Arg">P</var>)</code>th direct power of <var class="Arg">G</var>, and <code class="code">RcwaMapping</code>, Part (d) to embed the finite permutation group <var class="Arg">P</var>.</p>
</dd>
<dt><strong class="Mark">
<code class="code">WreathProduct(<var class="Arg">G</var>,<var class="Arg">Z</var>)</code>
</strong></dt>
<dd><p>Restricts <var class="Arg">G</var> to the residue class 3(4), and encodes the generator of <var class="Arg">Z</var> as tau_0(2),1(2) * tau_0(2),1(4). It is used that the images of 3(4) under powers of this mapping are pairwise disjoint residue classes.</p>
</dd>
</dl>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
2441
