Quelle chap2_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/rcwa/doc/chap2_mj.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< script type= "text/javascript"
src= "https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (RCWA) - Chapter 2: Residue-Class-Wise Affine Mappings</ 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= "chap2" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span><a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X7FD73FCB8510050E" name="X7FD73FCB8510050E"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X7FD73FCB8510050E">2 <span class="Heading">Residue-Class-Wise Affine Mappings</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X78ED07E37FC2BD46">2.1 <span class="Heading">Basic definitions</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X86BC55648302D643">2.2 <span class="Heading">Entering residue-class-wise affine mappings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X86B611BD7EED62A1">2.2-1 ClassShift</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7896C5417E3692B4">2.2-2 ClassReflection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8716A75F7DD1C46B">2.2-3 ClassTransposition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X87EB8C1C87F78A17">2.2-4 ClassRotation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8799551B83644B37">2.2-5 <span class="Heading"> RcwaMapping (the general constructor) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7F1A559387D0226E">2.2-6 LocalizedRcwaMapping</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X78E796B8824C4FC8">2.3 <span class="Heading">Basic arithmetic for residue-class-wise affine mappings</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7C16D22C7BD40FDC">2.4 <span class="Heading">
Attributes and properties of residue-class-wise affine mappings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7C21406085B69C30">2.4-1 LargestSourcesOfAffineMappings</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7D6D0F2783AD02F4">2.4-2 FixedPointsOfAffinePartialMappings</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7A2E308C860B46E3">2.4-3 Multpk</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7B1E53127D9AE52F">2.4-4 Determinant</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8365EEEB82C946FD">2.4-5 Sign</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X8475F844869DD060">2.5 <span class="Heading">Factoring residue-class-wise affine permutations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X829BA0537F2372FF">2.5-1 CTCSCRSplit</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X853885A182EC5104">2.5-2 FactorizationIntoCSCRCT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X861C74E97AE5DA3B">2.5-3 PrimeSwitch</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X789CB69C7D97B0C4">2.5-4 mKnot</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X8141065381B0942B">2.6 <span class="Heading">
Extracting roots of residue-class-wise affine mappings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X873692CE78433859">2.6-1 Root</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X8322C6848305EC4C">2.7 <span class="Heading">
Special functions for non-bijective mappings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7AEFF16E86533633">2.7-1 RightInverse</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X87C5B9CA7E319233">2.7-2 CommonRightInverse</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X808D9EDF7BA27467">2.7-3 ImageDensity</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7A34724386A2E9F3">2.8 <span class="Heading">
On trajectories and cycles of residue-class-wise affine mappings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7C72174D7CCB6348">2.8-1 <span class="Heading"> Trajectory (methods for rcwa mappings) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7FFD09837E934853">2.8-2 <span class="Heading">
Trajectory (methods for rcwa mappings -- <q>accumulated coefficients</q>)
</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7E0244A386744185">2.8-3 <span class="Heading"> IncreasingOn & DecreasingOn (for an rcwa mapping) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X780841E07CAE7543">2.8-4 TransitionGraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7F03CC4179424AA9">2.8-5 OrbitsModulo</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7F11051E866C197F">2.8-6 FactorizationOnConnectedComponents</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7B6833D67D916EF9">2.8-7 TransitionMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X81DBA2D58526BE7E">2.8-8 <span class="Heading"> Sources & Sinks (of an rcwa mapping) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X80221A4D81AF7453">2.8-9 Loops</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8773152E81A30123">2.8-10 GluckTaylorInvariant</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X84F6A29280E2F925">2.8-11 LikelyContractionCentre</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X81E0D8E3817B3D16">2.8-12 GuessedDivergence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X86F0E0D17E6A9663">2.9 <span class="Heading">
Saving memory -- the sparse representation of rcwa mappings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X879451B17AD78B07">2.9-1 SparseRepresentation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X83FA71DD842377F0">2.10 <span class="Heading">The categories and families of rcwa mappings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7927C13782729CE9">2.10-1 IsRcwaMapping</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X825DD365822934AF">2.10-2 RcwaMappingsFamily</a></span>
</div></div>
</div>
<h3>2 <span class="Heading">Residue-Class-Wise Affine Mappings</span></h3>
<p>This chapter contains the basic definitions, and it describes how to enter residue-class-wise affine mappings and how to compute with them.</p>
<p>How to compute with residue-class-wise affine groups is described in detail in the next chapter. The reader is encouraged to look there already after having read the first few pages of this chapter, and to look up definitions as he needs to.</p>
<p><a id="X78ED07E37FC2BD46" name="X78ED07E37FC2BD46"></a></p>
<h4>2.1 <span class="Heading">Basic definitions</span></h4>
<p>Residue-class-wise affine groups, or <em>rcwa</em> groups for short, are permutation groups whose elements are bijective residue-class-wise affine mappings.</p>
<p>A mapping <span class="SimpleMath">\(f: ℤ \rightarrow ℤ\)</span> is called <em>residue-class-wise affine</em>, or for short an <em>rcwa</em> mapping, if there is a positive integer <span class="SimpleMath">\(m\)</span> such that the restrictions of <span class="SimpleMath">\(f\)</span> to the residue classes <span class="SimpleMath">\(r(m) \in ℤ/mℤ\)</span> are all affine, i.e. given by</p>
<p><center> <img src = "rcwamap.png" width = "366" height = "49" alt = "f|_r(m): n |-> (a_r(m) * n + b_r(m)) / c_r(m)" /> </center></p>
<p>for certain coefficients <span class="SimpleMath">\(a_{r(m)}, b_{r(m)}, c_{r(m)} \in ℤ\)</span> depending on <span class="SimpleMath">\(r(m)\)</span>. The smallest possible <span class="SimpleMath">\(m\)</span> is called the <em>modulus</em> of <span class="SimpleMath">\(f\)</span>. It is understood that all fractions are reduced, i.e. that <span class="SimpleMath">\(\gcd( a_{r(m)}, b_{r(m)}, c_{r(m)} ) = 1\)</span>, and that <span class="SimpleMath">\(c_{r(m)} > 0\)</span>. The lcm of the coefficients <span class="SimpleMath">\(a_{r(m)}\)</span> is called the <em>multiplier</em> of <span class="SimpleMath">\(f\)</span>, and the lcm of the coefficients <span class="SimpleMath">\(c_{r(m)}\)</span> is called the <em>divisor</em> of <span class="SimpleMath">\(f\)</span>.</p>
<p>It is easy to see that the residue-class-wise affine mappings of ℤ form a monoid under composition, and that the residue-class-wise affine permutations of ℤ form a countable subgroup of Sym(ℤ). We denote the former by Rcwa(ℤ), and the latter by RCWA(ℤ).</p>
<p>An rcwa mapping is called <em>tame</em> if the set of moduli of its powers is bounded, or equivalently if it permutes a partition of ℤ into finitely many residue classes on all of which it is affine. An rcwa group is called <em>tame</em> if there is a common such partition for all of its elements, or equivalently if the set of moduli of its elements is bounded. Rcwa mappings and -groups which are not tame are called <em>wild</em>. Tame rcwa mappings and -groups are something which one could call the <q>trivial cases</q> or <q>basic building blocks</q>, while wild rcwa groups are the objects of primary interest.</p>
<p>The definitions of residue-class-wise affine mappings and -groups can be generalized in the obvious way to suitable rings other than ℤ. In fact, this package provides also some support for residue-class-wise affine groups over <span class="SimpleMath">\(ℤ^2\)</span>, over semilocalizations of ℤ and over univariate polynomial rings over finite fields. The ring <span class="SimpleMath">\(ℤ^2\)</span> has been chosen as an example of a suitable ring which is not a principal ideal domain, the semilocalizations of ℤ have been chosen as examples of rings with only finitely many prime elements, and the univariate polynomial rings over finite fields have been chosen as examples of rings with nonzero characteristic.</p>
<p><a id="X86BC55648302D643" name="X86BC55648302D643"></a></p>
<h4>2.2 <span class="Heading">Entering residue-class-wise affine mappings</span></h4>
<p>Entering an rcwa mapping of ℤ requires giving the modulus <span class="SimpleMath">\(m\)</span> and the coefficients <span class="SimpleMath">\(a_{r(m)}\)</span>, <span class="SimpleMath">\(b_{r(m)}\)</span> and <span class="SimpleMath">\(c_{r(m)}\)</span> for <span class="SimpleMath">\(r(m)\)</span> running over the residue classes (mod <span class="SimpleMath">\(m\)</span>).</p>
<p>This can be done easiest by <code class="code">RcwaMapping( <var class="Arg">coeffs</var> )</code>, where <var class="Arg">coeffs</var> is a list of <span class="SimpleMath">\(m\)</span> coefficient triples <code class="code">coeffs[</code><span class="SimpleMath">\(r+1\)</span><code class="code">] = [</code><span class="SimpleMath">\(a_{r(m)}\)</span>, <span class="SimpleMath">\(b_{r(m)}\)</span>, <span class="SimpleMath">\(c_{r(m)}\)</span><code class="code">]</code>, with <span class="SimpleMath">\(r\)</span> running from 0 to <span class="SimpleMath">\(m-1\)</span>.</p>
<p>If some coefficient <span class="SimpleMath">\(c_{r(m)}\)</span> is zero or if images of some integers under the mapping to be defined would not be integers, an error message is printed and a break loop is entered. For example, the coefficient triple <code class="code">[1,4,3]</code> is not allowed at the first position. The reason for this is that not all integers congruent to <span class="SimpleMath">\(1 \cdot 0 + 4 = 4\)</span> mod <span class="SimpleMath">\(m\)</span> are divisible by 3.</p>
<p>For the general constructor for rcwa mappings, see <code class="func">RcwaMapping</code> (<a href="chap2_mj.html#X8799551B83644B37"><span class="RefLink">2.2-5</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := RcwaMapping([[1,0,2],[3,1,2]]); # The Collatz mapping.</span>
<rcwa mapping of Z with modulus 2>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ IsSurjective(T), IsInjective(T) ];</span>
[ true, false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(T);</span>
Surjective rcwa mapping of Z with modulus 2
/
| n/2 if n in 0(2)
n |-> < (3n+1)/2 if n in 1(2)
|
\
<span class="GAPprompt">gap></span> <span class="GAPinput">a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);</span>
<rcwa mapping of Z with modulus 3>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBijective(a);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(a); # This is Collatz' permutation:</span>
Rcwa permutation of Z with modulus 3
/
| 2n/3 if n in 0(3)
n |-> < (4n-1)/3 if n in 1(3)
| (4n+1)/3 if n in 2(3)
\
<span class="GAPprompt">gap></span> <span class="GAPinput">Support(a);</span>
Z \ [ -1, 0, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cycle(a,44);</span>
[ 44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66 ]
</pre></div>
<p>There is computational evidence for the conjecture that any residue-class-wise affine permutation of ℤ can be factored into members of the following three series of permutations of particularly simple structure (cf. <code class="func">FactorizationIntoCSCRCT</code> (<a href="chap2_mj.html#X853885A182EC5104"><span class="RefLink">2.5-2</span></a>)):</p>
<p><a id="X86B611BD7EED62A1" name="X86B611BD7EED62A1"></a></p>
<h5>2.2-1 ClassShift</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassShift</code>( <var class="Arg">r</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassShift</code>( <var class="Arg">cl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the class shift <span class="SimpleMath">\(\nu_{r(m)}\)</span>.</p>
<p>The <em>class shift</em> <span class="SimpleMath">\(\nu_{r(m)}\)</span> is the rcwa mapping of ℤ which maps <span class="SimpleMath">\(n \in r(m)\)</span> to <span class="SimpleMath">\(n + m\)</span> and which fixes <span class="SimpleMath">\(ℤ \setminus r(m)\)</span> pointwise.</p>
<p>In the one-argument form, the argument <var class="Arg">cl</var> stands for the residue class <span class="SimpleMath">\(r(m)\)</span>. Enclosing the argument list in list brackets is permitted.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(ClassShift(5,12));</span>
Tame rcwa permutation of Z with modulus 12, of order infinity
/
| n+12 if n in 5(12)
n |-> < n if n in Z \ 5(12)
|
\
</pre></div>
<p><a id="X7896C5417E3692B4" name="X7896C5417E3692B4"></a></p>
<h5>2.2-2 ClassReflection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassReflection</code>( <var class="Arg">r</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassReflection</code>( <var class="Arg">cl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the class reflection <span class="SimpleMath">\(\varsigma_{r(m)}\)</span>.</p>
<p>The <em>class reflection</em> <span class="SimpleMath">\(\varsigma_{r(m)}\)</span> is the rcwa mapping of ℤ which maps <span class="SimpleMath">\(n \in r(m)\)</span> to <span class="SimpleMath">\(-n + 2r\)</span> and which fixes <span class="SimpleMath">\(ℤ \setminus r(m)\)</span> pointwise, where it is understood that <span class="SimpleMath">\(0 \leq r < m\)</span>.</p>
<p>In the one-argument form, the argument <var class="Arg">cl</var> stands for the residue class <span class="SimpleMath">\(r(m)\)</span>. Enclosing the argument list in list brackets is permitted.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(ClassReflection(5,9));</span>
Rcwa permutation of Z with modulus 9, of order 2
/
| -n+10 if n in 5(9)
n |-> < n if n in Z \ 5(9)
|
\
</pre></div>
<p><a id="X8716A75F7DD1C46B" name="X8716A75F7DD1C46B"></a></p>
<h5>2.2-3 ClassTransposition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassTransposition</code>( <var class="Arg">r1</var>, <var class="Arg">m1</var>, <var class="Arg">r2</var>, <var class="Arg">m2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassTransposition</code>( <var class="Arg">cl1</var>, <var class="Arg">cl2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the class transposition <span class="SimpleMath">\(\tau_{r_1(m_1),r_2(m_2)}\)</span>.</p>
<p>Given two disjoint residue classes <span class="SimpleMath">\(r_1(m_1)\)</span> and <span class="SimpleMath">\(r_2(m_2)\)</span> of the integers, the <em>class transposition</em> <span class="SimpleMath">\(\tau_{r_1(m_1),r_2(m_2)}\)</span> <span class="SimpleMath">\(\in\)</span> RCWA(ℤ) is defined as the involution which interchanges <span class="SimpleMath">\(r_1+km_1\)</span> and <span class="SimpleMath">\(r_2+km_2\)</span> for any integer <span class="SimpleMath">\(k\)</span> and which fixes all other points. It is understood that <span class="SimpleMath">\(m_1\)</span> and <span class="SimpleMath">\(m_2\)</span> are positive, that <span class="SimpleMath">\(0 \leq r_1 < m_1\)</span> and that <span class="SimpleMath">\(0 \leq r_2 < m_2\)</span>. For a <em>generalized class transposition</em>, the latter assumptions are not made.</p>
<p>The class transposition <span class="SimpleMath">\(\tau_{r_1(m_1),r_2(m_2)}\)</span> interchanges the residue classes <span class="SimpleMath">\(r_1(m_1)\)</span> and <span class="SimpleMath">\(r_2(m_2)\)</span> and fixes the complement of their union pointwise.</p>
<p>In the four-argument form, the arguments <var class="Arg">r1</var>, <var class="Arg">m1</var>, <var class="Arg">r2</var> and <var class="Arg">m2</var> stand for <span class="SimpleMath">\(r_1\)</span>, <span class="SimpleMath">\(m_1\)</span>, <span class="SimpleMath">\(r_2\)</span> and <span class="SimpleMath">\(m_2\)</span>, respectively. In the two-argument form, the arguments <var class="Arg">cl1</var> and <var class="Arg">cl2</var> stand for the residue classes <span class="SimpleMath">\(r_1(m_1)\)</span> and <span class="SimpleMath">\(r_2(m_2)\)</span>, respectively. Enclosing the argument list in list brackets is permitted. The residue classes <span class="SimpleMath">\(r_1(m_1)\)</span> and <span class="SimpleMath">\(r_2(m_2)\)</span> are stored as an attribute <code class="code">TransposedClasses</code>.</p>
<p>A list of all class transpositions interchanging residue classes with moduli less than or equal to a given bound <var class="Arg">m</var> can be obtained by <code class="code">List(ClassPairs([<var class="Arg">P</var>],<var class="Arg">m</var>),ClassTransposition)</code>, where the function <code class="code">ClassPairs</code> returns a list of all 4-tuples <span class="SimpleMath">\((r_1,m_1,r_2,m_2)\)</span> of integers corresponding to the unordered pairs of disjoint residue classes <span class="SimpleMath">\(r_1(m_1)\)</span> and <span class="SimpleMath">\(r_2(m_2)\)</span> with <span class="SimpleMath">\(m_1\)</span> and <span class="SimpleMath">\(m_2\)</span> less than or equal to the specified bound. If a list of primes is given as optional argument <var class="Arg">P</var>, then the returned list contains only those 4-tuples where all prime factors of <span class="SimpleMath">\(m_1\)</span> and <span class="SimpleMath">\(m_2\)</span> lie in <var class="Arg">P</var>. If the option <code class="code">divisors</code> is set, the returned list contains only the 4-tuples where <span class="SimpleMath">\(m_1\)</span> and <span class="SimpleMath">\(m_2\)</span> divide <var class="Arg">m</var>.</p>
<p>The function <code class="code">NrClassPairs(<var class="Arg">m</var>)</code> returns the length of the list <code class="code">ClassPairs(<var class="Arg">m</var>)</code>, where the result is computed much faster and without actually generating the list of tuples. Given a class transposition <var class="Arg">ct</var>, the corresponding 4-tuple can be obtained by <code class="code">ExtRepOfObj(<var class="Arg">ct</var>)</code></p>
<p>A class transposition can be written as a product of any given number <span class="SimpleMath">\(k\)</span> of class transpositions. Such a decomposition can be obtained by <code class="code">SplittedClassTransposition(<var class="Arg">ct</var>,<var class="Arg">k</var>)</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(ClassTransposition(1,2,8,10):CycleNotation:=false);</span>
Rcwa permutation of Z with modulus 10, of order 2
/
| 5n+3 if n in 1(2)
n |-> < (n-3)/5 if n in 8(10)
| n if n in 0(2) \ 8(10)
\
<span class="GAPprompt">gap></span> <span class="GAPinput">List(ClassPairs(4),ClassTransposition);</span>
[ ( 0(2), 1(2) ), ( 0(2), 1(4) ), ( 0(2), 3(4) ), ( 0(3), 1(3) ),
( 0(3), 2(3) ), ( 0(4), 1(4) ), ( 0(4), 2(4) ), ( 0(4), 3(4) ),
( 1(2), 0(4) ), ( 1(2), 2(4) ), ( 1(3), 2(3) ), ( 1(4), 2(4) ),
( 1(4), 3(4) ), ( 2(4), 3(4) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NrClassPairs(100);</span>
3528138
<span class="GAPprompt">gap></span> <span class="GAPinput">SplittedClassTransposition(ClassTransposition(0,2,1,4),3);</span>
[ ( 0(6), 1(12) ), ( 2(6), 5(12) ), ( 4(6), 9(12) ) ]
</pre></div>
<p>The set of all class transpositions of the ring of integers generates the simple group CT(ℤ) mentioned in Chapter <a href="chap1_mj.html#X83A8C2927FAE2C23"><span class="RefLink">1</span></a>. This group has a representation as a <strong class="pkg">GAP</strong> object -- see <code class="func">CT</code> (<a href="chap3_mj.html#X7BD42D8481300E25"><span class="RefLink">3.1-9</span></a>). The set of all generalized class transpositions of ℤ generates a simple group as well, cf. <a href="chapBib_mj.html#biBKohl09">[Koh10]</a>.</p>
<p>Class shifts, class reflections and class transpositions of rings <span class="SimpleMath">\(R\)</span> other than ℤ are defined in an entirely analogous way -- all one needs to do is to replace ℤ by <span class="SimpleMath">\(R\)</span> and to read <span class="SimpleMath">\(<\)</span> and <span class="SimpleMath">\(\leq\)</span> in the sense of the ordering used by <strong class="pkg">GAP</strong>. They can also be entered basically as described above -- just prepend the desired ring <span class="SimpleMath">\(R\)</span> to the argument list. Often also a sensible <q>default ring</q> (<span class="SimpleMath">\(\rightarrow\)</span> <code class="code">DefaultRing</code> in the <strong class="pkg">GAP</strong> Reference Manual) is chosen if that optional first argument is omitted.</p>
<p>On rings which have more than two units, there is another basic series of rcwa permutations which generalizes class reflections:</p>
<p><a id="X87EB8C1C87F78A17" name="X87EB8C1C87F78A17"></a></p>
<h5>2.2-4 ClassRotation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassRotation</code>( <var class="Arg">r</var>, <var class="Arg">m</var>, <var class="Arg">u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassRotation</code>( <var class="Arg">cl</var>, <var class="Arg">u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the class rotation <span class="SimpleMath">\(\rho_{r(m),u}\)</span>.</p>
<p>Given a residue class <span class="SimpleMath">\(r(m)\)</span> and a unit <span class="SimpleMath">\(u\)</span> of a suitable ring <span class="SimpleMath">\(R\)</span>, the <em>class rotation</em> <span class="SimpleMath">\(\rho_{r(m),u}\)</span> is the rcwa mapping which maps <span class="SimpleMath">\(n \in r(m)\)</span> to <span class="SimpleMath">\(un + (1-u)r\)</span> and which fixes <span class="SimpleMath">\(R \setminus r(m)\)</span> pointwise. Class rotations generalize class reflections, as we have <span class="SimpleMath">\(\rho_{r(m),-1} = \varsigma_{r(m)}\)</span>.</p>
<p>In the two-argument form, the argument <var class="Arg">cl</var> stands for the residue class <span class="SimpleMath">\(r(m)\)</span>. Enclosing the argument list in list brackets is permitted. The argument <var class="Arg">u</var> is stored as an attribute <code class="code">RotationFactor</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(ClassRotation(ResidueClass(Z_pi(2),2,1),1/3));</span>
Tame rcwa permutation of Z_( 2 ) with modulus 2, of order infinity
/
| 1/3 n + 2/3 if n in 1(2)
n |-> < n if n in 0(2)
|
\
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(GF(8),1);; SetName(x,"x");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := PolynomialRing(GF(8),1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cr := ClassRotation(1,x,Z(8)*One(R)); Support(cr);</span>
ClassRotation( 1(x), Z(2^3) )
1(x) \ [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(cr);</span>
Rcwa permutation of GF(2^3)[x] with modulus x, of order 7
/
| Z(2^3)*P + Z(2^3)^3 if P in 1(x)
P |-> < P otherwise
|
\
</pre></div>
<p><code class="code">IsClassShift</code>, <code class="code">IsClassReflection</code>, <code class="code">IsClassRotation</code>, <code class="code">IsClassTransposition</code> and <code class="code">IsGeneralizedClassTransposition</code> are properties which indicate whether a given rcwa mapping belongs to the corresponding series.</p>
<p>In the sequel we describe the general-purpose constructor for rcwa mappings. The constructor may look a bit technical on a first glance, but knowing all possible ways of entering an rcwa mapping is by no means necessary for understanding this manual or for using this package.</p>
<p><a id="X8799551B83644B37" name="X8799551B83644B37"></a></p>
<h5>2.2-5 <span class="Heading"> RcwaMapping (the general constructor) </span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">R</var>, <var class="Arg">m</var>, <var class="Arg">coeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">R</var>, <var class="Arg">coeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">coeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">perm</var>, <var class="Arg">range</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">m</var>, <var class="Arg">values</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">pi</var>, <var class="Arg">coeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">q</var>, <var class="Arg">m</var>, <var class="Arg">coeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">P1</var>, <var class="Arg">P2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">cycles</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RcwaMapping</code>( <var class="Arg">expression</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an rcwa mapping.</p>
<p>In all cases the argument <var class="Arg">R</var> is the underlying ring, <var class="Arg">m</var> is the modulus and <var class="Arg">coeffs</var> is the coefficient list. A <em>coefficient list</em> for an rcwa mapping with modulus <span class="SimpleMath">\(m\)</span> consists of <span class="SimpleMath">\(|R/mR|\)</span> coefficient triples <code class="code">[</code><span class="SimpleMath">\(a_{r(m)}\)</span>, <span class="SimpleMath">\(b_{r(m)}\)</span>, <span class="SimpleMath">\(c_{r(m)}\)</span><code class="code">]</code>. Their ordering is determined by the ordering of the representatives of the residue classes (mod <span class="SimpleMath">\(m\)</span>) in the sorted list returned by <code class="code">AllResidues(<var class="Arg">R</var>, <var class="Arg">m</var>)</code>. In case <span class="SimpleMath">\(R = ℤ\)</span> this means that the coefficient triple for the residue class <span class="SimpleMath">\(0(m)\)</span> comes first and is followed by the one for <span class="SimpleMath">\(1(m)\)</span>, the one for <span class="SimpleMath">\(2(m)\)</span> and so on.</p>
<p>If one or several of the arguments <var class="Arg">R</var>, <var class="Arg">m</var> and <var class="Arg">coeffs</var> are omitted or replaced by other arguments, the former are either derived from the latter or default values are chosen. The meaning of the other arguments is defined in the detailed description of the particular methods given in the sequel. The above methods return the rcwa mapping</p>
<dl>
<dt><strong class="Mark">(a)</strong></dt>
<dd><p>of <var class="Arg">R</var> with modulus <var class="Arg">m</var> and coefficients <var class="Arg">coeffs</var>,</p>
</dd>
<dt><strong class="Mark">(b)</strong></dt>
<dd><p>of <var class="Arg">R</var> = ℤ or <var class="Arg">R</var> = <span class="SimpleMath">\(ℤ_{(\pi)}\)</span> with modulus <code class="code">Length(<var class="Arg">coeffs</var>)</code> and coefficients <var class="Arg">coeffs</var>,</p>
</dd>
<dt><strong class="Mark">(c)</strong></dt>
<dd><p>of <var class="Arg">R</var> = ℤ with modulus <code class="code">Length(<var class="Arg">coeffs</var>)</code> and coefficients <var class="Arg">coeffs</var>,</p>
</dd>
<dt><strong class="Mark">(d)</strong></dt>
<dd><p>of <var class="Arg">R</var> = ℤ, permuting any set <code class="code"><var class="Arg">range</var>+k*Length(<var class="Arg">range</var>)</code> like <var class="Arg">perm</var> permutes <var class="Arg">range</var>,</p>
</dd>
<dt><strong class="Mark">(e)</strong></dt>
<dd><p>of <var class="Arg">R</var> = ℤ with modulus <var class="Arg">m</var> and values given by a list <var class="Arg">val</var> of 2 pairs <code class="code">[</code>preimage<code class="code">, </code>image<code class="code">]</code> per residue class (mod <var class="Arg">m</var>),</p>
</dd>
<dt><strong class="Mark">(f)</strong></dt>
<dd><p>of <var class="Arg">R</var> = <span class="SimpleMath">\(ℤ_{(\pi)}\)</span> with modulus <code class="code">Length(<var class="Arg">coeffs</var>)</code> and coefficients <var class="Arg">coeffs</var> (the set of primes <span class="SimpleMath">\(\pi\)</span> which denotes the underlying ring is passed as argument <var class="Arg">pi</var>),</p>
</dd>
<dt><strong class="Mark">(g)</strong></dt>
<dd><p>of <var class="Arg">R</var> = GF(<var class="Arg">q</var>)[<var class="Arg">x</var>] with modulus <var class="Arg">m</var> and coefficients <var class="Arg">coeffs</var>,</p>
</dd>
<dt><strong class="Mark">(h)</strong></dt>
<dd><p>an rcwa permutation which induces a bijection between the partitions <var class="Arg">P1</var> and <var class="Arg">P2</var> of <var class="Arg">R</var> into residue classes and which is affine on the elements of <var class="Arg">P1</var>,</p>
</dd>
<dt><strong class="Mark">(i)</strong></dt>
<dd><p>an rcwa permutation with <q>residue class cycles</q> given by a list <var class="Arg">cycles</var> of lists of pairwise disjoint residue classes, each of which it permutes cyclically, or</p>
</dd>
<dt><strong class="Mark">(j)</strong></dt>
<dd><p>the rcwa permutation of ℤ given by the arithmetical expression <var class="Arg">expression</var> -- a string consisting of class transpositions (e.g. <code class="code">"(0(2),1(4))"</code>) or cycles permuting residue classes (e.g. <code class="code">"(0(2),1(8),3(4),5(8))"</code>), class shifts (e.g. <code class="code">"cs(4(6))"</code>, class reflections (e.g. <code class="code">"cr(3(4))"</code>), arithmetical operators (<code class="code">"*"</code>, <code class="code">"/"</code> and <code class="code">"^"</code>) and brackets (<code class="code">"("</code>, <code class="code">")"</code>),</p>
</dd>
</dl>
<p>respectively. The methods for the operation <code class="code">RcwaMapping</code> perform a number of argument checks, which can be skipped by using <code class="code">RcwaMappingNC</code> instead.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := PolynomialRing(GF(2),1);; x := X(GF(2),1);; SetName(x,"x");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping(R,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R)); # (a)</span>
<rcwa mapping of GF(2)[x] with modulus x+1>
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping(Z_pi(2),[[1/3,0,1]]); # (b)</span>
Rcwa mapping of Z_( 2 ): n -> 1/3 n
<span class="GAPprompt">gap></span> <span class="GAPinput">a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]); # (c)</span>
<rcwa mapping of Z with modulus 3>
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping((1,2,3),[1..4]); # (d)</span>
( 1(4), 2(4), 3(4) )
<span class="GAPprompt">gap></span> <span class="GAPinput">T = RcwaMapping(2,[[1,2],[2,1],[3,5],[4,2]]); # (e)</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping([2],[[1/3,0,1]]); # (f)</span>
Rcwa mapping of Z_( 2 ): n -> 1/3 n
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping(2,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R)); # (g)</span>
<rcwa mapping of GF(2)[x] with modulus x+1>
<span class="GAPprompt">gap></span> <span class="GAPinput">a = RcwaMapping(List([[0,3],[1,3],[2,3]],ResidueClass),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> List([[0,2],[1,4],[3,4]],ResidueClass)); # (h)</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaMapping([List([[0,2],[1,4],[3,8],[7,16]],ResidueClass)]); # (i)</span>
( 0(2), 1(4), 3(8), 7(16) )
<span class="GAPprompt">gap></span> <span class="GAPinput">Cycle(last,ResidueClass(0,2));</span>
[ 0(2), 1(4), 3(8), 7(16) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">g := RcwaMapping("((0(4),1(6))*cr(0(6)))^2/cs(2(8))"); # (j)</span>
<rcwa permutation of Z with modulus 72>
<span class="GAPprompt">gap></span> <span class="GAPinput">g = (ClassTransposition(0,4,1,6) * ClassReflection(0,6))^2/</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ClassShift(2,8);</span>
true
</pre></div>
<p>Rcwa mappings of ℤ can be <q>translated</q> to rcwa mappings of some semilocalization <span class="SimpleMath">\(ℤ_{(\pi)}\)</span> of ℤ:</p>
<p><a id="X7F1A559387D0226E" name="X7F1A559387D0226E"></a></p>
<h5>2.2-6 LocalizedRcwaMapping</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LocalizedRcwaMapping</code>( <var class="Arg">f</var>, <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemilocalizedRcwaMapping</code>( <var class="Arg">f</var>, <var class="Arg">pi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the rcwa mapping of <span class="SimpleMath">\(ℤ_{(p)}\)</span> respectively <span class="SimpleMath">\(ℤ_{(\pi)}\)</span> with the same coefficients as the rcwa mapping <var class="Arg">f</var> of ℤ.</p>
<p>The argument <var class="Arg">p</var> or <var class="Arg">pi</var> must be a prime or a set of primes, respectively. The argument <var class="Arg">f</var> must be an rcwa mapping of ℤ whose modulus is a power of <var class="Arg">p</var>, or whose modulus has only prime divisors which lie in <var class="Arg">pi</var>, respectively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Cycle(LocalizedRcwaMapping(T,2),131/13);</span>
[ 131/13, 203/13, 311/13, 473/13, 716/13, 358/13, 179/13, 275/13,
419/13, 635/13, 959/13, 1445/13, 2174/13, 1087/13, 1637/13, 2462/13,
1231/13, 1853/13, 2786/13, 1393/13, 2096/13, 1048/13, 524/13, 262/13 ]
</pre></div>
<p>Rcwa mappings can be <code class="code">View</code>ed, <code class="code">Display</code>ed, <code class="code">Print</code>ed and written to a <code class="code">String</code>. The output of the <code class="code">View</code> method is kept reasonably short. In most cases it does not describe an rcwa mapping completely. In these cases the output is enclosed in brackets. There are options <code class="code">CycleNotation</code>, <code class="code">AsClassMapping</code>, <code class="code">PrintNotation</code> and <code class="code">AbridgedNotation</code> to take influence on how certain rcwa mappings are shown. These options can either be not set, set to <code class="code">true</code> or set to <code class="code">false</code>. If the option <code class="code">CycleNotation</code> is set, it is tried harder to write down an rcwa permutation of ℤ of finite order as a product of disjoint residue class cycles, if this is possible. If the option <code class="code">AsClassMapping</code> is set, <code class="code">Display</code> shows which residue classes are mapped to which by the affine partial mappings, and marks any loops. The option <code class="code">PrintNotation</code> influences the output in favour of <strong class="pkg">GAP</strong> - readability, and the option <code class="code">AbridgedNotation</code> can be used to abridge longer names like <code class="code">ClassShift</code>, <code class="code">ClassReflection</code> etc.. By default, the output of the methods for <code class="code">Display</code> and <code class="code">Print</code> describes an rcwa mapping in full. The <code class="code">Print</code>ed representation of an rcwa mapping is <strong class="pkg">GAP</strong> - readable if and only if the <code class="code">Print</code>ed representation of the elements of the underlying ring is so.</p>
<p>There is also an operation <code class="code">LaTeXStringRcwaMapping</code>, which takes as argument an rcwa mapping and returns a corresponding LaTeX string. The output makes use of the LaTeX macro package <strong class="pkg">amsmath</strong>. If the option <var class="Arg">Factorization</var> is set and the argument is bijective, a factorization into class shifts, class reflections, class transpositions and prime switches is printed (cf. <code class="func">FactorizationIntoCSCRCT</code> (<a href="chap2_mj.html#X853885A182EC5104"><span class="RefLink">2.5-2</span></a>)). For rcwa mappings with modulus greater than 1, an indentation by <var class="Arg">Indentation</var> characters can be obtained by setting this option value accordingly.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(LaTeXStringRcwaMapping(T));</span>
n \ \mapsto \
\begin{cases}
n/2 & \text{if} \ n \in 0(2), \\
(3n+1)/2 & \text{if} \ n \in 1(2).
\end{cases}
</pre></div>
<p>There is an operation <code class="code">LaTeXAndXDVI</code> which displays an rcwa mapping in an <strong class="pkg">xdvi</strong> window. This works as follows: The string returned by <code class="code">LaTeXStringRcwaMapping</code> is inserted into a LaTeX template file. This file is LaTeX'ed, and the result is shown with <strong class="pkg">xdvi</strong>. Calling <code class="code">Display</code> with option <var class="Arg">xdvi</var> has the same effect. The operation <code class="code">LaTeXAndXDVI</code> is only available on UNIX systems, and requires suitable installations of LaTeX and <strong class="pkg">xdvi</strong>.</p>
<p><a id="X78E796B8824C4FC8" name="X78E796B8824C4FC8"></a></p>
<h4>2.3 <span class="Heading">Basic arithmetic for residue-class-wise affine mappings</span></h4>
<p>Testing rcwa mappings for equality requires only comparing their coefficient lists, hence is cheap. Rcwa mappings can be multiplied, thus there is a method for <code class="code">*</code>. Rcwa permutations can also be inverted, thus there is a method for <code class="code">Inverse</code>. The latter method is usually accessed by raising a mapping to a power with negative exponent. Multiplying, inverting and computing powers of tame rcwa mappings is cheap. Computing powers of wild mappings is usually expensive -- run time and memory requirements normally grow approximately exponentially with the exponent. How expensive multiplying a couple of wild mappings is, varies very much. In any case, the amount of memory required for storing an rcwa mapping is proportional to its modulus. Whether a given mapping is tame or wild can be determined by the operation <code class="code">IsTame</code>. There is a method for <code class="code">Order</code>, which can not only compute a finite order, but which can also detect infinite order.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; # Collatz' permutation.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([-4..4],k->Modulus(a^k));</span>
[ 256, 64, 16, 4, 1, 3, 9, 27, 81 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(T) or IsTame(a);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(ClassShift(0,1)) and IsTame(ClassTransposition(0,2,1,2));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">T^2*a*T*a^-3;</span>
<rcwa mapping of Z with modulus 768>
<span class="GAPprompt">gap></span> <span class="GAPinput">(ClassShift(1,3)*ClassReflection(2,7))^1000000;</span>
<rcwa permutation of Z with modulus 21>
</pre></div>
<p>There are methods installed for <code class="code">IsInjective</code>, <code class="code">IsSurjective</code>, <code class="code">IsBijective</code> and <code class="code">Image</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ IsInjective(T), IsSurjective(T), IsBijective(a) ];</span>
[ false, true, true ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Image(RcwaMapping([[2,0,1]]));</span>
0(2)
</pre></div>
<p>Images of elements, of finite sets of elements and of unions of finitely many residue classes of the source of an rcwa mapping can be computed with <code class="code">^</code>, the same symbol as used for exponentiation and conjugation. The same works for partitions of the source into a finite number of residue classes.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">15^T;</span>
23
<span class="GAPprompt">gap></span> <span class="GAPinput">ResidueClass(1,2)^T;</span>
2(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">List([[0,3],[1,3],[2,3]],ResidueClass)^a;</span>
[ 0(2), 1(4), 3(4) ]
</pre></div>
<p>For computing preimages of elements under rcwa mappings, there are methods for <code class="code">PreImageElm</code> and <code class="code">PreImagesElm</code>. The preimage of a finite set of ring elements or of a union of finitely many residue classes under an rcwa mapping can be computed by <code class="code">PreImage</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PreImagesElm(T,8);</span>
[ 5, 16 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PreImage(T,ResidueClass(Integers,3,2));</span>
Z \ 0(6) U 2(6)
<span class="GAPprompt">gap></span> <span class="GAPinput">M := [1];; l := [1];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">while Length(M) < 5000 do M := PreImage(T,M); Add(l,Length(M)); od; l;</span>
[ 1, 1, 2, 2, 4, 5, 8, 10, 14, 18, 26, 36, 50, 67, 89, 117, 157, 208,
277, 367, 488, 649, 869, 1154, 1534, 2039, 2721, 3629, 4843, 6458 ]
</pre></div>
<p>There is a method for the operation <code class="code">Support</code> for computing the support of an rcwa mapping. A synonym for <code class="code">Support</code> is <code class="code">MovedPoints</code>. The natural density of the support of an rcwa mapping of ℤ can be computed efficiently with the operation <code class="code">DensityOfSupport</code>. Likewise, the natural density of the set of fixed points of an rcwa mapping of ℤ can be computed efficiently with the operation <code class="code">DensityOfSetOfFixedPoints</code>. There is also a method for <code class="code">RestrictedPerm</code> for computing the restriction of an rcwa permutation to a union of residue classes which it fixes setwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([a,a^2],Support);</span>
[ Z \ [ -1, 0, 1 ], Z \ [ -3, -2, -1, 0, 1, 2, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RestrictedPerm(ClassShift(0,2)*ClassReflection(1,2),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ResidueClass(0,2));</span>
<rcwa mapping of Z with modulus 2>
<span class="GAPprompt">gap></span> <span class="GAPinput">last = ClassShift(0,2);</span>
true
</pre></div>
<p>Rcwa mappings can be added and subtracted pointwise. However, please note that the set of rcwa mappings of a ring does not form a ring under <code class="code">+</code> and <code class="code">*</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := ClassShift(0,3) * a;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ Image((a + b)), Image((a - b)) ];</span>
[ 2(4), [ -2, 0 ] ]
</pre></div>
<p>There are operations <code class="code">Modulus</code> (abbreviated <code class="code">Mod</code>) and <code class="code">Coefficients</code> for retrieving the modulus and the coefficient list of an rcwa mapping. The meaning of the return values is as described in Section <a href="chap2_mj.html#X86BC55648302D643"><span class="RefLink">2.2</span></a>.</p>
<p>General documentation for most operations mentioned in this section can be found in the <strong class="pkg">GAP</strong> reference manual. For rcwa mappings of rings other than ℤ, not for all operations applicable methods are available.</p>
<p>As in general a subring relation <span class="SimpleMath">\(R_1<R_2\)</span> does <em>not</em> give rise to a natural embedding of RCWA(<span class="SimpleMath">\(R_1\)</span>) into RCWA(<span class="SimpleMath">\(R_2\)</span>), there is no coercion between rcwa mappings or rcwa groups over different rings.</p>
<p><a id="X7C16D22C7BD40FDC" name="X7C16D22C7BD40FDC"></a></p>
<h4>2.4 <span class="Heading">
Attributes and properties of residue-class-wise affine mappings
</span></h4>
<p>A number of basic attributes and properties of an rcwa mapping are derived immediately from the coefficients of its affine partial mappings. This holds for example for the multiplier and the divisor. These two values are stored as attributes <code class="code">Multiplier</code> and <code class="code">Divisor</code>, or for short <code class="code">Mult</code> and <code class="code">Div</code>. The <em>prime set</em> of an rcwa mapping is the set of prime divisors of the product of its modulus and its multiplier. It is stored as an attribute <code class="code">PrimeSet</code>. The <em>maximal shift</em> of an rcwa mapping of ℤ is the maximum of the absolute values of its coefficients <span class="SimpleMath">\(b_{r(m)}\)</span> in the notation introduced in Section <a href="chap2_mj.html#X78ED07E37FC2BD46"><span class="RefLink">2.1</span></a>. It is stored as an attribute <code class="code">MaximalShift</code>. An rcwa mapping is called <em>class-wise translating</em> if all of its affine partial mappings are translations, it is called <em>integral</em> if its divisor equals 1, and it is called <em>balanced</em> if its multiplier and its divisor have the same prime divisors. A class-wise translating mapping has the property <code class="code">IsClassWiseTranslating</code>, an integral mapping has the property <code class="code">IsIntegral</code> and a balanced mapping has the property <code class="code">IsBalanced</code>. An rcwa mapping of the ring of integers or of one of its semilocalizations is called <em>class-wise order-preserving</em> if and only if all coefficients < | |
