<?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 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" />
</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="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X7FD73FCB8510050E" name="X7FD73FCB8510050E"></a></p>
<div class="ChapSects"><a href="chap2.html#X7FD73FCB8510050E">2. <span class="Heading">Residue-Class-Wise Affine Mappings</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7F0B50947EEA87F8">2.1 <span class="Heading">Basic definitions</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X86BC55648302D643">2.2 <span class="Heading">Entering residue-class-wise affine mappings</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X86B611BD7EED62A1">2.2-1 ClassShift</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7896C5417E3692B4">2.2-2 ClassReflection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8716A75F7DD1C46B">2.2-3 ClassTransposition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X87EB8C1C87F78A17">2.2-4 ClassRotation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7D87A85584BA7E48">2.2-5 <span class="Heading"> RcwaMapping (the general constructor) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7F1A559387D0226E">2.2-6 LocalizedRcwaMapping</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X78E796B8824C4FC8">2.3 <span class="Heading">Basic arithmetic for residue-class-wise affine mappings</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X861C5DE6812425F1">2.4 <span class="Heading">
Attributes and properties of residue-class-wise affine mappings
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7C21406085B69C30">2.4-1 LargestSourcesOfAffineMappings</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7D6D0F2783AD02F4">2.4-2 FixedPointsOfAffinePartialMappings</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7A2E308C860B46E3">2.4-3 Multpk</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7B1E53127D9AE52F">2.4-4 Determinant</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8365EEEB82C946FD">2.4-5 Sign</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X8475F844869DD060">2.5 <span class="Heading">Factoring residue-class-wise affine permutations</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X853885A182EC5104">2.5-1 FactorizationIntoCSCRCT</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X861C74E97AE5DA3B">2.5-2 PrimeSwitch</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X789CB69C7D97B0C4">2.5-3 mKnot</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X8141065381B0942B">2.6 <span class="Heading">
Extracting roots of residue-class-wise affine mappings
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X873692CE78433859">2.6-1 Root</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X8322C6848305EC4C">2.7 <span class="Heading">
Special functions for non-bijective mappings
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7AEFF16E86533633">2.7-1 RightInverse</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X87C5B9CA7E319233">2.7-2 CommonRightInverse</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X808D9EDF7BA27467">2.7-3 ImageDensity</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7A34724386A2E9F3">2.8 <span class="Heading">
On trajectories and cycles of residue-class-wise affine mappings
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.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.html#X7FFD09837E934853">2.8-2 <span class="Heading">
Trajectory (methods for rcwa mappings -- "accumulated coefficients")
</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.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.html#X780841E07CAE7543">2.8-4 TransitionGraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7F03CC4179424AA9">2.8-5 OrbitsModulo</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7F11051E866C197F">2.8-6 FactorizationOnConnectedComponents</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7B6833D67D916EF9">2.8-7 TransitionMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.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.html#X80221A4D81AF7453">2.8-9 Loops</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8773152E81A30123">2.8-10 GluckTaylorInvariant</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X84F6A29280E2F925">2.8-11 LikelyContractionCentre</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X81E0D8E3817B3D16">2.8-12 GuessedDivergence</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X83FA71DD842377F0">2.9 <span class="Heading">The categories and families of rcwa mappings</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7927C13782729CE9">2.9-1 IsRcwaMapping</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X825DD365822934AF">2.9-2 RcwaMappingsFamily</a></span>
</div>
</div>
<h3>2. <span class="Heading">Residue-Class-Wise Affine Mappings</span></h3>
<p>In this chapter we give the basic definitions, and describe 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="X7F0B50947EEA87F8" name="X7F0B50947EEA87F8"></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 f: Z -> Z is called <em>residue-class-wise affine</em>, or for short an <em>rcwa</em> mapping, if there is a positive integer m such that the restrictions of f to the residue classes r(m) in Z/mZ 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 a_r(m), b_r(m), c_r(m) in Z depending on r(m). The smallest possible m is called the <em>modulus</em> of f. It is understood that all fractions are reduced, i.e. that gcd( a_r(m), b_r(m), c_r(m) ) = 1, and that c_r(m) > 0. The lcm of the coefficients a_r(m) is called the <em>multiplier</em> of f, and the lcm of the coefficients c_r(m) is called the <em>divisor</em> of f.</p>
<p>It is easy to see that the residue-class-wise affine mappings of Z form a monoid under composition, and that the residue-class-wise affine permutations of Z form a countable subgroup of Sym(Z). We denote the former by Rcwa(Z), and the latter by RCWA(Z).</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 Z 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 "trivial cases" or "basic building blocks", 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 an obvious way to suitable rings other than Z. In fact, this package provides also some support for residue-class-wise affine groups over semilocalizations of Z and over univariate polynomial rings over finite fields. The former of these rings have been chosen as examples of rings with only finitely prime elements, and the latter 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 Z requires giving the modulus m and the coefficients a_r(m), b_r(m) and c_r(m) for r(m) running over the residue classes (mod m).</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 m coefficient triples <code class="code">coeffs[</code>r+1<code class="code">] = [</code>a_r(m), b_r(m), c_r(m)<code class="code">]</code>, with r running from 0 to m-1.</p>
<p>If some coefficient c_r(m) 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 1 * 0 + 4 = 4 mod m are divisible by 3.</p>
<p>For the general constructor for rcwa mappings, see <code class="func">RcwaMapping</code> (<a href="chap2.html#X7D87A85584BA7E48"><b>2.2-5</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]); # The Collatz mapping.
<rcwa mapping of Z with modulus 2>
gap> [ IsSurjective(T), IsInjective(T) ];
[ true, false ]
gap> SetName(T,"T"); Display(T);
Surjective rcwa mapping of Z with modulus 2
n mod 2 | n^T
------------------------------------+------------------------------------
0 | n/2
1 | (3n + 1)/2
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]); SetName(a,"a");
<rcwa mapping of Z with modulus 3>
gap> IsBijective(a);
true
gap> Display(a); # This is Collatz' permutation:
Bijective rcwa mapping of Z with modulus 3
n mod 3 | n^a
------------------------------------+------------------------------------
0 | 2n/3
1 | (4n - 1)/3
2 | (4n + 1)/3
gap> Support(a);
Z \ [ -1, 0, 1 ]
gap> Cycle(a,44);
[ 44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66 ]
</pre></td></tr></table>
<p>There is computational evidence for the conjecture that any residue-class-wise affine permutation of Z 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.html#X853885A182EC5104"><b>2.5-1</b></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, 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><b>Returns: </b>The class shift nu_r(m).</p>
<p>The <em>class shift</em> nu_r(m) is the rcwa mapping of Z which maps n in r(m) to n + m and which fixes Z \ r(m) pointwise.</p>
<p>In the one-argument form, the argument <var class="Arg">cl</var> stands for the residue class r(m). Enclosing the argument list in list brackets is permitted.</p>
<table class="example">
<tr><td><pre>
gap> Display(ClassShift(5,12));
Tame bijective rcwa mapping of Z with modulus 12, of order infinity
n mod 12 | n^ClassShift(5,12)
------------------------------------+------------------------------------
0 1 2 3 4 6 7 8 9 10 11 | n
5 | n + 12
</pre></td></tr></table>
<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, 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><b>Returns: </b>The class reflection varsigma_r(m).</p>
<p>The <em>class reflection</em> varsigma_r(m) is the rcwa mapping of Z which maps n in r(m) to -n + 2r and which fixes Z \ r(m) pointwise, where it is understood that 0 <= r < m.</p>
<p>In the one-argument form, the argument <var class="Arg">cl</var> stands for the residue class r(m). Enclosing the argument list in list brackets is permitted.</p>
<table class="example">
<tr><td><pre>
gap> Display(ClassReflection(5,9));
Bijective rcwa mapping of Z with modulus 9, of order 2
n mod 9 | n^ClassReflection(5,9)
------------------------------------+------------------------------------
0 1 2 3 4 6 7 8 | n
5 | -n + 10
</pre></td></tr></table>
<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, m1, r2, 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, cl2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The class transposition tau_r_1(m_1),r_2(m_2).</p>
<p>Given two disjoint residue classes r_1(m_1) and r_2(m_2) of the integers, the <em>class transposition</em> tau_r_1(m_1),r_2(m_2) in RCWA(Z) is defined as the involution which interchanges r_1+km_1 and r_2+km_2 for any integer k and which fixes all other points. It is understood that m_1 and m_2 are positive, that 0 <= r_1 < m_1 and that 0 <= r_2 < m_2. For a <em>generalized class transposition</em>, the latter assumptions are not made.</p>
<p>The class transposition tau_r_1(m_1),r_2(m_2) interchanges the residue classes r_1(m_1) and r_2(m_2) 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 r_1, m_1, r_2 and m_2, respectively. In the two-argument form, the arguments <var class="Arg">cl1</var> and <var class="Arg">cl2</var> stand for the residue classes r_1(m_1) and r_2(m_2), respectively. Enclosing the argument list in list brackets is permitted. The residue classes r_1(m_1) and r_2(m_2) are stored as an attribute <code class="code">TransposedClasses</code>.</p>
<p>A class transposition can be written as a product of any given number k 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>
<table class="example">
<tr><td><pre>
gap> Display(ClassTransposition(1,2,8,10));
Bijective rcwa mapping of Z with modulus 10, of order 2
n mod 10 | n^ClassTransposition(1,2,8,10)
------------------------------------+------------------------------------
0 2 4 6 | n
1 3 5 7 9 | 5n + 3
8 | (n - 3)/5
</pre></td></tr></table>
<p>The set of all class transpositions of the ring of integers generates the simple group CT(Z) mentioned in Chapter <a href="chap1.html#X83A8C2927FAE2C23"><b>1.</b></a>. This group has a representation as a <strong class="pkg">GAP</strong> object -- see <code class="func">CT</code> (<a href="chap3.html#X7BD42D8481300E25"><b>3.1-2</b></a>). The set of all generalized class transpositions of Z generates a simple group as well, cf. <a href="chapBib.html#biBKohl06b">[Koh06a]</a>.</p>
<p>Class shifts, class reflections and class transpositions of rings R other than Z are defined in an entirely analogous way -- all one needs to do is to replace Z by R and to read < and <= 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 R to the argument list. Often also a sensible "default ring" (-> <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, m, 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, u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The class rotation rho_r(m),u.</p>
<p>Given a residue class r(m) and a unit u of a suitable ring R, the <em>class rotation</em> rho_r(m),u is the rcwa mapping which maps n in r(m) to un + (1-u)r and which fixes R \ r(m) pointwise. Class rotations generalize class reflections, as we have rho_r(m),-1 = varsigma_r(m).</p>
<p>In the two-argument form, the argument <var class="Arg">cl</var> stands for the residue class r(m). 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>
<table class="example">
<tr><td><pre>
gap> Display(ClassRotation(ResidueClass(Z_pi(2),2,1),1/3));
Tame bijective rcwa mapping of Z_( 2 ) with modulus 2, of order infinity
n mod 2 | n^ClassRotation(1,2,1/3)
------------------------------------+------------------------------------
0 | n
1 | 1/3 n + 2/3
gap> x := Indeterminate(GF(8),1);; SetName(x,"x");
gap> R := PolynomialRing(GF(8),1);;
gap> Display(ClassRotation(1,x,Z(8)*One(R)));
Bijective rcwa mapping of GF(2^3)[x] with modulus x, of order 7
P mod x | P^(ClassRotation(Z(2)^0,x,Z(2^3)))
------------------------+------------------------------------------------
0*Z(2) Z(2^3) |
Z(2^3)^2 Z(2^3)^3 |
Z(2^3)^4 Z(2^3)^5 |
Z(2^3)^6 | P
Z(2)^0 | Z(2^3)*P + Z(2^3)^3
</pre></td></tr></table>
<p>There are properties <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>, which indicate whether a given rcwa mapping belongs to the corresponding series. By default, class shifts, class reflections, class transpositions and class rotations are given descriptive names of the form <code class="code">Class...(...)</code>. They can be given user-defined names upon creation via the option <code class="code">Name</code>. Setting the <code class="code">Name</code> attribute can be avoided by passing the empty string.</p>
<p>In the sequel, a description of the general-purpose constructor for rcwa mappings is given. This might 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="X7D87A85584BA7E48" name="X7D87A85584BA7E48"></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, m, 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, 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, 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, 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, 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, m, 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, 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>
<p><b>Returns: </b>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 coefficient list for an rcwa mapping with modulus m consists of |R/mR| coefficient triples <code class="code">[</code>a_r(m), b_r(m), c_r(m)<code class="code">]</code>. Their ordering is determined by the ordering of the representatives of the residue classes (mod m) in the sorted list returned by <code class="code">AllResidues(<var class="Arg">R</var>, <var class="Arg">m</var>)</code>. In case R = Z this means that the coefficient triple for the residue class 0(m) comes first and is followed by the one for 1(m), the one for 2(m) and so on.</p>
<p>In case 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 taken. 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> = Z or <var class="Arg">R</var> = Z_(pi) 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> = Z 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> = Z, 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> = Z 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> = Z_(pi) with modulus <code class="code">Length(<var class="Arg">coeffs</var>)</code> and coefficients <var class="Arg">coeffs</var> (the set of primes pi 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>a bijective rcwa mapping 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>, or</p>
</dd>
<dt><strong class="Mark">(i)</strong></dt>
<dd><p>a bijective rcwa mapping with "residue class cycles" given by a list <var class="Arg">cycles</var> of lists of pairwise disjoint residue classes which are to be permuted cyclically, each, respectively.</p>
</dd>
</dl>
<p>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>
<table class="example">
<tr><td><pre>
gap> R := PolynomialRing(GF(2),1);; x := X(GF(2),1);; SetName(x,"x");
gap> RcwaMapping(R,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R)); # (a)
<rcwa mapping of GF(2)[x] with modulus x+Z(2)^0>
gap> RcwaMapping(Z_pi(2),[[1/3,0,1]]); # (b)
Rcwa mapping of Z_( 2 ): n -> 1/3 n
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]); # (c)
<rcwa mapping of Z with modulus 3>
gap> RcwaMapping((1,2,3),[1..4]); # (d)
<bijective rcwa mapping of Z with modulus 4, of order 3>
gap> T = RcwaMapping(2,[[1,2],[2,1],[3,5],[4,2]]); # (e)
true
gap> RcwaMapping([2],[[1/3,0,1]]); # (f)
Rcwa mapping of Z_( 2 ): n -> 1/3 n
gap> RcwaMapping(2,x+1,[[1,0,x+One(R)],[x+One(R),0,1]]*One(R)); # (g)
<rcwa mapping of GF(2)[x] with modulus x+Z(2)^0>
gap> a = RcwaMapping(List([[0,3],[1,3],[2,3]],ResidueClass),
> List([[0,2],[1,4],[3,4]],ResidueClass)); # (h)
true
gap> RcwaMapping([List([[0,2],[1,4],[3,8],[7,16]],ResidueClass)]); # (i)
<bijective rcwa mapping of Z with modulus 16, of order 4>
gap> Cycle(last,ResidueClass(0,2));
[ 0(2), 1(4), 3(8), 7(16) ]
</pre></td></tr></table>
<p>Rcwa mappings of Z can be "translated" to rcwa mappings of some semilocalization Z_(pi) of Z:</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, 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, pi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The rcwa mapping of Z_(p) respectively Z_(pi) with the same coefficients as the rcwa mapping <var class="Arg">f</var> of Z.</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 Z 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>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> Cycle(LocalizedRcwaMapping(T,2),131/13);
[ 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></td></tr></table>
<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. The output of the methods for <code class="code">Display</code> and <code class="code">Print</code> describe 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 a method for <code class="code">LaTeX</code>, respectively <code class="code">LaTeXObj</code>. The output of this method 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.html#X853885A182EC5104"><b>2.5-1</b></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 accor\-dingly.</p>
<table class="example">
<tr><td><pre>
gap> Print(LaTeXObj(T));
n \ \longmapsto \
\begin{cases}
n/2 & \text{if} \ n \in 0(2), \\
(3n + 1)/2 & \text{if} \ n \in 1(2).
\end{cases}
</pre></td></tr></table>
<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 the <code class="code">LaTeXObj</code> - method described above 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>. Bijective rcwa mappings 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 -- runtime 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>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; # Collatz' permutation.
gap> List([-4..4],k->Modulus(a^k));
[ 256, 64, 16, 4, 1, 3, 9, 27, 81 ]
gap> IsTame(T) or IsTame(a);
false
gap> IsTame(ClassShift(0,1)) and IsTame(ClassTransposition(0,2,1,2));
true
gap> T^2*a*T*a^-3;
<rcwa mapping of Z with modulus 768>
gap> (ClassShift(1,3)*ClassReflection(2,7))^1000000;
<bijective rcwa mapping of Z with modulus 21>
</pre></td></tr></table>
<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>
<table class="example">
<tr><td><pre>
gap> [ IsInjective(T), IsSurjective(T), IsBijective(a) ];
[ false, true, true ]
gap> Image(RcwaMapping([[2,0,1]]));
0(2)
</pre></td></tr></table>
<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>
<table class="example">
<tr><td><pre>
gap> 15^T;
23
gap> ResidueClass(1,2)^T;
2(3)
gap> List([[0,3],[1,3],[2,3]],ResidueClass)^a;
[ 0(2), 1(4), 3(4) ]
</pre></td></tr></table>
<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>
<table class="example">
<tr><td><pre>
gap> PreImagesElm(T,8);
[ 5, 16 ]
gap> PreImage(T,ResidueClass(Integers,3,2));
Z \ 0(6) U 2(6)
gap> M := [1];; l := [1];;
gap> while Length(M) < 5000 do M := PreImage(T,M); Add(l,Length(M)); od; l;
[ 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></td></tr></table>
<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>. There is also a method for <code class="code">RestrictedPerm</code> for computing the restriction of a bijective rcwa mapping to a union of residue classes which it fixes setwise.</p>
<table class="example">
<tr><td><pre>
gap> List([a,a^2],Support);
[ Z \ [ -1, 0, 1 ], Z \ [ -3, -2, -1, 0, 1, 2, 3 ] ]
gap> RestrictedPerm(ClassShift(0,2)*ClassReflection(1,2),
> ResidueClass(0,2));
<rcwa mapping of Z with modulus 2>
gap> last = ClassShift(0,2);
true
</pre></td></tr></table>
<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>
<table class="example">
<tr><td><pre>
gap> b := ClassShift(0,3) * a;;
gap> [ Image((a + b)), Image((a - b)) ];
[ 2(4), [ -2, 0 ] ]
</pre></td></tr></table>
<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.html#X86BC55648302D643"><b>2.2</b></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 Z, not for all operations applicable methods are available.</p>
<p>As in general a subring relation R_1<R_2 does <em>not</em> give rise to a natural embedding of RCWA(R_1) into RCWA(R_2), there is no coercion between rcwa mappings or rcwa groups over different rings.</p>
<p><a id="X861C5DE6812425F1" name="X861C5DE6812425F1"></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>. An rcwa mapping is called <em>integral</em> if its divisor equals 1. An rcwa mapping is called <em>balanced</em> if its multiplier and its divisor have the same prime divisors. 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 a_r(m) (cf. Section <a href="chap2.html#X7F0B50947EEA87F8"><b>2.1</b></a>) in the numerators of the affine partial mappings are positive. The corresponding property is <code class="code">IsClassWiseOrderPreserving</code>. An rcwa mapping of Z is called <em>sign-preserving</em> if it does not map nonnegative integers to negative integers or vice versa. The corresponding property is <code class="code">IsSignPreserving</code>. All elements of the simple group CT(Z) generated by the set of all class transpositions are sign-preserving.</p>
<table class="example">
<tr><td><pre>
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> IsBijective(u);; Display(u);
Bijective rcwa mapping of Z with modulus 5
n mod 5 | n^f
------------------------------------+------------------------------------
0 | 3n/5
1 | (9n + 1)/5
2 | (3n - 1)/5
3 | (9n - 2)/5
4 | (9n + 4)/5
gap> Multiplier(u);
9
gap> Divisor(u);
5
gap> PrimeSet(u);
[ 3, 5 ]
gap> IsIntegral(u) or IsBalanced(u);
false
gap> IsClassWiseOrderPreserving(u) and IsSignPreserving(u);
true
</pre></td></tr></table>
<p>There are a couple of further attributes and operations related to the affine partial mappings of an rcwa mapping:</p>
<p><a id="X7C21406085B69C30" name="X7C21406085B69C30"></a></p>
<h5>2.4-1 LargestSourcesOfAffineMappings</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LargestSourcesOfAffineMappings</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The coarsest partition of <code class="code">Source(<var class="Arg">f</var>)</code> on whose elements the rcwa mapping <var class="Arg">f</var> is affine.</p>
<table class="example">
<tr><td><pre>
gap> LargestSourcesOfAffineMappings(ClassShift(3,7));
[ Z \ 3(7), 3(7) ]
gap> LargestSourcesOfAffineMappings(ClassReflection(0,1));
[ Integers ]
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> List( [ u, u^-1 ], LargestSourcesOfAffineMappings );
[ [ 0(5), 1(5), 2(5), 3(5), 4(5) ], [ 0(3), 1(3), 2(9), 5(9), 8(9) ] ]
gap> kappa := ClassTransposition(2,4,3,4) * ClassTransposition(4,6,8,12)
> * ClassTransposition(3,4,4,6);
<bijective rcwa mapping of Z with modulus 12>
gap> LargestSourcesOfAffineMappings(kappa);
[ 2(4), 1(4) U 0(12), 3(12) U 7(12), 4(12), 8(12), 11(12) ]
</pre></td></tr></table>
<p><a id="X7D6D0F2783AD02F4" name="X7D6D0F2783AD02F4"></a></p>
<h5>2.4-2 FixedPointsOfAffinePartialMappings</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FixedPointsOfAffinePartialMappings</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A list of the sets of fixed points of the affine partial mappings of the rcwa mapping <var class="Arg">f</var> in the quotient field of its source.</p>
<p>The returned list contains entries for the restrictions of <var class="Arg">f</var> to all residue classes modulo <code class="code">Mod(<var class="Arg">f</var>)</code>. A list entry can either be an empty set, the source of <var class="Arg">f</var> or a set of cardinality 1. The ordering of the entries corresponds to the ordering of the residues in <code class="code">AllResidues(Source(<var class="Arg">f</var>),<var class="Arg">m</var>)</code>.</p>
<table class="example">
<tr><td><pre>
gap> FixedPointsOfAffinePartialMappings(ClassShift(0,2));
[ [ ], Rationals ]
gap> List([1..3],k->FixedPointsOfAffinePartialMappings(T^k));
[ [ [ 0 ], [ -1 ] ], [ [ 0 ], [ 1 ], [ 2 ], [ -1 ] ],
[ [ 0 ], [ -7 ], [ 2/5 ], [ -5 ], [ 4/5 ], [ 1/5 ], [ -10 ], [ -1 ] ] ]
</pre></td></tr></table>
<p><a id="X7A2E308C860B46E3" name="X7A2E308C860B46E3"></a></p>
<h5>2.4-3 Multpk</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Multpk</code>( <var class="Arg">f, p, k</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The union of the residue classes r(m) such that p^k||a_r(m) if k >= 0, and the union of the residue classes r(m) such that p^k||c_r(m) if k <= 0. In this context, m denotes the modulus of <var class="Arg">f</var>, and a_r(m) and c_r(m) denote the coefficients of <var class="Arg">f</var> as introduced in Section <a href="chap2.html#X7F0B50947EEA87F8"><b>2.1</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> [ Multpk(T,2,-1), Multpk(T,3,1) ];
[ Integers, 1(2) ]
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> [ Multpk(u,3,0), Multpk(u,3,1), Multpk(u,3,2), Multpk(u,5,-1) ];
[ [ ], 0(5) U 2(5), Z \ 0(5) U 2(5), Integers ]
</pre></td></tr></table>
<p>There are attributes <code class="code">ClassWiseOrderPreservingOn</code>, <code class="code">ClassWiseConstantOn</code> and <code class="code">ClassWiseOrderReversingOn</code> which store the union of the residue classes (mod <code class="code">Mod(<var class="Arg">f</var>)</code>) on which an rcwa mapping <var class="Arg">f</var> of Z or of a semilocalization thereof is class-wise order-preserving, class-wise constant or class-wise order-reversing, respectively.</p>
<table class="example">
<tr><td><pre>
gap> List([ClassTransposition(1,2,0,4),ClassShift(2,3),
> ClassReflection(2,5)],ClassWiseOrderPreservingOn);
[ Integers, Integers, Z \ 2(5) ]
</pre></td></tr></table>
<p>Finally, there are epimorphisms from the subgroup of RCWA(Z) formed by all class-wise order-preserving elements to (Z,+) and from RCWA(Z) itself to the cyclic group of order 2, respectively:</p>
<p><a id="X7B1E53127D9AE52F" name="X7B1E53127D9AE52F"></a></p>
<h5>2.4-4 Determinant</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Determinant</code>( <var class="Arg">f</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The determinant of the rcwa mapping <var class="Arg">f</var> of Z.</p>
<p>The <em>determinant</em> of an affine mapping n -> (an+b)/c whose source is a residue class r(m) is defined by b/|a|m. This definition is extended additively to determinants of rcwa mappings.</p>
<p>Let f be an rcwa mapping of the integers, and let m denote its modulus. Using the notation f|_r(m): n -> (a_r(m) * n + b_r(m))/c_r(m) for the affine partial mappings, the <em>determinant</em> det(f) of f is given by</p>
<p><center> <img src = "det.png" width = "177" height = "58" alt = "sum_{r(m) in Z/mZ} b_{r(m)}/(|a_{r(m)}| \cdot m)."/> </center></p>
<p>The determinant mapping is an epimorphism from the group of all class-wise order-preserving bijective rcwa mappings of Z to (Z,+), see <a href="chapBib.html#biBKohl05">[Koh05]</a>, Theorem 2.11.9.</p>
<table class="example">
<tr><td><pre>
gap> List([ClassTransposition(0,4,5,12),ClassShift(3,7)],Determinant);
[ 0, 1 ]
gap> Determinant(ClassTransposition(0,4,5,12)*ClassShift(3,7)^100);
100
</pre></td></tr></table>
<p><a id="X8365EEEB82C946FD" name="X8365EEEB82C946FD"></a></p>
<h5>2.4-5 Sign</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Sign</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The sign of the bijective rcwa mapping <var class="Arg">g</var> of Z.</p>
<p>Let sigma be an rcwa permutation of the integers, and let m denote its modulus. Using the notation sigma|_r(m): n -> (a_r(m) * n + b_r(m))/c_r(m) for the affine partial mappings, the <em>sign</em> of sigma is defined by</p>
<p><center> <img src = "sgn.png" width = "284" height = "63" alt = "(-1)^(det(sigma) + sum_{r(m): \ a_{r(m)} < 0} (m - 2r)/m)."/> </center></p>
<p>The sign mapping is an epimorphism from RCWA(Z) to the group Z^x of units of Z, see <a href="chapBib.html#biBKohl05">[Koh05]</a>, Theorem 2.12.8. Therefore the kernel of the sign mapping is a normal subgroup of RCWA(Z) of index 2. The simple group CT(Z) is a subgroup of this kernel.</p>
<table class="example">
<tr><td><pre>
gap> List([ClassTransposition(3,4,2,6),
> ClassShift(0,3),ClassReflection(2,5)],Sign);
[ 1, -1, -1 ]
</pre></td></tr></table>
<p><a id="X8475F844869DD060" name="X8475F844869DD060"></a></p>
<h4>2.5 <span class="Heading">Factoring residue-class-wise affine permutations</span></h4>
<p>Factoring group elements into the members of some "nice" set of generators is often helpful. In this section we describe an operation which attempts to solve this problem for the group RCWA(Z). Elements of finitely generated rcwa groups can be factored into generators "as usual", see <code class="func">PreImagesRepresentative</code> (<a href="chap3.html#X8463E34286344F06"><b>3.2-3</b></a>).</p>
<p><a id="X853885A182EC5104" name="X853885A182EC5104"></a></p>
<h5>2.5-1 FactorizationIntoCSCRCT</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FactorizationIntoCSCRCT</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Factorization</code>( <var class="Arg">g</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A factorization of the bijective rcwa mapping <var class="Arg">g</var> of Z into class shifts, class reflections and class transpositions, provided that such a factorization exists and the method finds it.</p>
<p>The method may return <code class="code">fail</code>, stop with an error message or run into an infinite loop. If it returns a result, this result is always correct.</p>
<p>The problem of obtaining a factorization as described is algorithmically difficult, and this factorization routine is currently perhaps the most sophisticated part of the <strong class="pkg">RCWA</strong> package. Information about the progress of the factorization process can be obtained by setting the info level of the Info class <code class="func">InfoRCWA</code> (<a href="chap7.html#X7BAF5F4986288983"><b>7.3-1</b></a>) to 2.</p>
<p>By default, prime switches (-> <code class="func">PrimeSwitch</code> (<a href="chap2.html#X861C74E97AE5DA3B"><b>2.5-2</b></a>)) are taken as one factor. If the option <var class="Arg">ExpandPrimeSwitches</var> is set, they are each decomposed into the 6 class transpositions given in the definition.</p>
<p>By default, the factoring process begins with splitting off factors from the right. This can be changed by setting the option <var class="Arg">Direction</var> to <code class="code">"from the left"</code>.</p>
<p>By default, a reasonably coarse respected partition of the integral mapping occuring in the final stage of the algorithm is computed. This can be suppressed by setting the option <var class="Arg">ShortenPartition</var> equal to <code class="code">false</code>.</p>
<p>By default, at the end it is checked whether the product of the determined factors indeed equals <var class="Arg">g</var>. This check can be suppressed by setting the option <var class="Arg">NC</var>.</p>
<table class="example">
<tr><td><pre>
gap> Factorization(Comm(ClassShift(0,3)*ClassReflection(1,2),
> ClassShift(0,2)));
[ ClassReflection(2,3), ClassShift(2,6)^-1, ClassTransposition(0,6,2,6),
ClassTransposition(0,6,5,6) ]
</pre></td></tr></table>
<p>For purposes of demonstrating the capabilities of the factorization routine, in Section <a href="chap5.html#X86C2BAE3876985A6"><b>5.1</b></a> Collatz' permutation is factored. Lothar Collatz has investigated this permutation in 1932. Its cycle structure is unknown so far.</p>
<p>The permutations of the following kind play an important role in factoring rcwa permutations of Z into class shifts, class reflections and class transpositions:</p>
<p><a id="X861C74E97AE5DA3B" name="X861C74E97AE5DA3B"></a></p>
<h5>2.5-2 PrimeSwitch</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PrimeSwitch</code>( <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">> PrimeSwitch</code>( <var class="Arg">p, k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>In the one-argument form the <em>prime switch</em> sigma_p := tau_0(8),1(2p) * tau_4(8),-1(2p) * tau_0(4),1(2p) * tau_2(4),-1(2p) * tau_2(2p),1(4p) * tau_4(2p),2p+1(4p), and in the two-argument form the restriction of sigma_p by n -> kn.</p>
<p>For an odd prime p, the prime switch sigma_p is a bijective rcwa mapping of Z with modulus 4p, multiplier p and divisor 2. The key mathematical property of a prime switch is that it is a product of class transpositions, but that its multiplier and its divisor are coprime anyway. Prime switches can be distinguished from other rcwa mappings by their <strong class="pkg">GAP</strong> property <code class="code">IsPrimeSwitch</code>.</p>
<table class="example">
<tr><td><pre>
gap> Display(PrimeSwitch(3));
Wild bijective rcwa mapping of Z with modulus 12
n mod 12 | n^PrimeSwitch(3)
------------------------------------+------------------------------------
0 | n/2
1 7 | n + 1
2 6 10 | (3n + 4)/2
3 9 | n
4 | n - 3
5 8 11 | n - 1
gap> Factorization(PrimeSwitch(3));
[ ClassTransposition(1,6,0,8), ClassTransposition(5,6,4,8),
ClassTransposition(0,4,1,6), ClassTransposition(2,4,5,6),
ClassTransposition(2,6,1,12), ClassTransposition(4,6,7,12) ]
</pre></td></tr></table>
<p>Obtaining a factorization of a bijective rcwa mapping into class shifts, class reflections and class transpositions is particularly difficult if multiplier and divisor are coprime. A prototype of permutations which have this property has been introduced in a different context in <a href="chapBib.html#biBKeller99">[Kel99]</a>:</p>
<p><a id="X789CB69C7D97B0C4" name="X789CB69C7D97B0C4"></a></p>
<h5>2.5-3 mKnot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> mKnot</code>( <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The permutation g_m as introduced in <a href="chapBib.html#biBKeller99">[Kel99]</a>.</p>
<p>The argument <var class="Arg">m</var> must be an odd integer greater than 1.</p>
<table class="example">
<tr><td><pre>
gap> Display(mKnot(5));
Wild bijective rcwa mapping of Z with modulus 5
n mod 5 | n^mKnot(5)
------------------------------------+------------------------------------
0 | 6n/5
1 | (4n + 1)/5
2 | (6n - 2)/5
3 | (4n + 3)/5
4 | (6n - 4)/5
</pre></td></tr></table>
<p>In his article, Timothy P. Keller shows that a permutation of this type cannot have infinitely many cycles of any given finite length.</p>
<p><a id="X8141065381B0942B" name="X8141065381B0942B"></a></p>
<h4>2.6 <span class="Heading">
Extracting roots of residue-class-wise affine mappings
</span></h4>
<p><a id="X873692CE78433859" name="X873692CE78433859"></a></p>
<h5>2.6-1 Root</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Root</code>( <var class="Arg">f, k</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>An rcwa mapping <code class="code">g</code> such that <code class="code">g^<var class="Arg">k</var>=<var class="Arg">f</var></code>, provided that such a mapping exists and that there is a method available which can determine it.</p>
<p>Currently, extracting roots is implemented for rcwa permutations of finite order.</p>
<table class="example">
<tr><td><pre>
gap> Root(ClassTransposition(0,2,1,2),100);
<bijective rcwa mapping of Z with modulus 8>
gap> Display(last);
Bijective rcwa mapping of Z with modulus 8
n mod 8 | n^f
------------------------------------+------------------------------------
0 1 2 3 4 5 | n + 2
6 | n - 5
7 | n - 7
gap> last^100 = ClassTransposition(0,2,1,2);
true
</pre></td></tr></table>
<p><a id="X8322C6848305EC4C" name="X8322C6848305EC4C"></a></p>
<h4>2.7 <span class="Heading">
Special functions for non-bijective mappings
</span></h4>
<p><a id="X7AEFF16E86533633" name="X7AEFF16E86533633"></a></p>
<h5>2.7-1 RightInverse</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RightInverse</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A right inverse of the injective rcwa mapping <var class="Arg">f</var>, i.e. a mapping g such that <var class="Arg">f</var>g = 1.</p>
<table class="example">
<tr><td><pre>
gap> twice := 2*IdentityRcwaMappingOfZ;
Rcwa mapping of Z: n -> 2n
gap> twice * RightInverse(twice);
IdentityMapping( Integers )
</pre></td></tr></table>
<p><a id="X87C5B9CA7E319233" name="X87C5B9CA7E319233"></a></p>
<h5>2.7-2 CommonRightInverse</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CommonRightInverse</code>( <var class="Arg">l, r</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A mapping d such that <var class="Arg">l</var>d = <var class="Arg">r</var>d = 1.</p>
<p>The mappings <var class="Arg">l</var> and <var class="Arg">r</var> must be injective, and their images must form a partition of their source.</p>
<table class="example">
<tr><td><pre>
gap> twice := 2*IdentityRcwaMappingOfZ; twiceplus1 := twice+1;
Rcwa mapping of Z: n -> 2n
Rcwa mapping of Z: n -> 2n + 1
gap> Display(CommonRightInverse(twice,twiceplus1));
Rcwa mapping of Z with modulus 2
n mod 2 | n^f
------------------------------------+------------------------------------
0 | n/2
1 | (n - 1)/2
</pre></td></tr></table>
<p><a id="X808D9EDF7BA27467" name="X808D9EDF7BA27467"></a></p>
<h5>2.7-3 ImageDensity</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageDensity</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The <em>image density</em> of the rcwa mapping <var class="Arg">f</var>.</p>
<p>In the notation introduced in the definition of an rcwa mapping, the <em>image density</em> of an rcwa mapping f is defined by 1/m sum_r(m) in R/mR |R/c_r(m)R|/|R/a_r(m)R|. The image density of an injective rcwa mapping is <= 1, and the image density of a surjective rcwa mapping is >= 1 (this can be seen easily). Thus in particular the image density of a bijective rcwa mapping is 1.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> List( [ T, ClassShift(0,1), RcwaMapping([[2,0,1]]) ], ImageDensity );
[ 4/3, 1, 1/2 ]
</pre></td></tr></table>
<p>Given an rcwa mapping <code class="code">f</code>, the function <code class="code">InjectiveAsMappingFrom</code> returns a set <code class="code">S</code> such that the restriction of <code class="code">f</code> to <code class="code">S</code> is injective, and such that the image of <code class="code">S</code> under <code class="code">f</code> is the entire image of <code class="code">f</code>.</p>
<table class="example">
<tr><td><pre>
gap> InjectiveAsMappingFrom(T);
0(2)
</pre></td></tr></table>
<p><a id="X7A34724386A2E9F3" name="X7A34724386A2E9F3"></a></p>
<h4>2.8 <span class="Heading">
On trajectories and cycles of residue-class-wise affine mappings
</span></h4>
<p><strong class="pkg">RCWA</strong> provides various methods to compute trajectories of rcwa mappings:</p>
<p><a id="X7C72174D7CCB6348" name="X7C72174D7CCB6348"></a></p>
<h5>2.8-1 <span class="Heading"> Trajectory (methods for rcwa mappings) </span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Trajectory</code>( <var class="Arg">f, n, length</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">> Trajectory</code>( <var class="Arg">f, n, length, m</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">> Trajectory</code>( <var class="Arg">f, n, terminal</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">> Trajectory</code>( <var class="Arg">f, n, terminal, m</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The first <var class="Arg">length</var> iterates in the trajectory of the rcwa mapping <var class="Arg">f</var> starting at <var class="Arg">n</var>, respectively the initial part of the trajectory of the rcwa mapping <var class="Arg">f</var> starting at <var class="Arg">n</var> which ends at the first occurence of an iterate in the set <var class="Arg">terminal</var>. If the argument <var class="Arg">m</var> is given, the iterates are reduced (mod <var class="Arg">m</var>).</p>
<p>To save memory when computing long trajectories containing huge iterates, the reduction (mod <var class="Arg">m</var>) is done each time before storing an iterate. In place of the ring element <var class="Arg">n</var>, the methods also accept a finite set of ring elements or a union of residue classes.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> Trajectory(T,27,15); Trajectory(T,27,20,5);
[ 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103 ]
[ 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 0, 3, 0, 0, 3 ]
gap> Trajectory(T,15,[1]); Trajectory(T,15,[1],2);
[ 15, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1 ]
[ 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 ]
gap> Trajectory(T,ResidueClass(Integers,3,0),Integers);
[ 0(3), 0(3) U 5(9), 0(3) U 5(9) U 7(9) U 8(27),
<union of 20 residue classes (mod 27)>,
<union of 73 residue classes (mod 81)>, Z \ 10(81) U 37(81), Integers ]
</pre></td></tr></table>
<p><a id="X7FFD09837E934853" name="X7FFD09837E934853"></a></p>
<h5>2.8-2 <span class="Heading">
Trajectory (methods for rcwa mappings -- "accumulated coefficients")
</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Trajectory</code>( <var class="Arg">f, n, length, whichcoeffs</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">> Trajectory</code>( <var class="Arg">f, n, terminal, whichcoeffs</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>Either the list <code class="code">c</code> of triples of coprime coefficients such that for any <code class="code">k</code> it holds that <code class="code"><var class="Arg">n</var>^(<var class="Arg">f</var>^(k-1)) = (c[k][1]*<var class="Arg">n</var> + c[k][2])/c[k][3]</code> or the last entry of that list, depending on whether <var class="Arg">whichcoeffs</var> is <code class="code">"AllCoeffs"</code> or <code class="code">"LastCoeffs"</code>.</p>
<p>The meanings of the arguments <var class="Arg">length</var> and <var class="Arg">terminal</var> are the same as in the methods for the operation <code class="code">Trajectory</code> described above. In general, computing only the last coefficient triple (<var class="Arg">whichcoeffs</var> = <code class="code">"LastCoeffs"</code>) needs considerably less memory than computing the entire list.</p>
<table class="example">
<tr><td><pre>
gap> Trajectory(T,27,[1],"LastCoeffs");
[ 36472996377170786403, 195820718533800070543, 1180591620717411303424 ]
gap> (last[1]*27+last[2])/last[3];
1
</pre></td></tr></table>
<p>When dealing with problems like the 3n+1-Conjecture or when determining the degree of transitivity of the natural action of an rcwa group on its underlying ring, an important task is to determine the residue classes whose elements get larger or smaller when applying a given rcwa mapping:</p>
<p><a id="X7E0244A386744185" name="X7E0244A386744185"></a></p>
<h5>2.8-3 <span class="Heading"> IncreasingOn & DecreasingOn (for an rcwa mapping) </span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IncreasingOn</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DecreasingOn</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The union of all residue classes r(m) such that |R/a_r(m)R| > |R/c_r(m)R| or |R/a_r(m)R| < |R/c_r(m)R|, respectively, where R denotes the source, m denotes the modulus and a_r(m), b_r(m) and c_r(m) denote the coefficients of <var class="Arg">f</var> as introduced in Section <a href="chap2.html#X7F0B50947EEA87F8"><b>2.1</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> List([1..3],k->IncreasingOn(T^k));
[ 1(2), 3(4), 3(4) U 1(8) U 6(8) ]
gap> List([1..3],k->DecreasingOn(T^k));
[ 0(2), Z \ 3(4), 0(4) U 2(8) U 5(8) ]
gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; # Collatz' permutation
gap> List([-2..2],k->IncreasingOn(a^k));
[ Z \ 1(8) U 7(8), 0(2), [ ], Z \ 0(3), 1(9) U 4(9) U 5(9) U 8(9) ]
</pre></td></tr></table>
<p>We assign certain directed graphs to rcwa mappings, which encode the order in which trajectories may traverse the residue classes modulo some modulus:</p>
<p><a id="X780841E07CAE7543" name="X780841E07CAE7543"></a></p>
<h5>2.8-4 TransitionGraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TransitionGraph</code>( <var class="Arg">f, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The transition graph of the rcwa mapping <var class="Arg">f</var> for modulus <var class="Arg">m</var>.</p>
<p>The <em>transition graph</em> Gamma_f,m of f for modulus m is defined as follows:</p>
<ol>
<li><p>The vertices are the residue classes (mod m).</p>
</li>
<li><p>There is an edge from r_1(m) to r_2(m) if and only if there is some n in r_1(m) such that n^f in r_2(m).</p>
</li>
</ol>
<p>The assignment of the residue classes (mod m) to the vertices of the graph corresponds to the ordering of the residues in <code class="code">AllResidues(Source(<var class="Arg">f</var>),<var class="Arg">m</var>)</code>. The result is returned in the format used by the package <strong class="pkg">GRAPE</strong> <a href="chapBib.html#biBGRAPE">[Soi02]</a>.</p>
<p>There are a couple of operations and attributes which are based on these graphs:</p>
<p><a id="X7F03CC4179424AA9" name="X7F03CC4179424AA9"></a></p>
<h5>2.8-5 OrbitsModulo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OrbitsModulo</code>( <var class="Arg">f, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The partition of <code class="code">AllResidues(Source(<var class="Arg">f</var>),<var class="Arg">m</var>)</code> corresponding to the weakly connected components of the transition graph of the rcwa mapping <var class="Arg">f</var> for modulus <var class="Arg">m</var>.</p>
<table class="example">
<tr><td><pre>
gap> OrbitsModulo(ClassTransposition(0,2,1,4),8);
[ [ 0, 1, 4 ], [ 2, 5, 6 ], [ 3 ], [ 7 ] ]
</pre></td></tr></table>
<p><a id="X7F11051E866C197F" name="X7F11051E866C197F"></a></p>
<h5>2.8-6 FactorizationOnConnectedComponents</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FactorizationOnConnectedComponents</code>( <var class="Arg">f, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The set of restrictions of the rcwa mapping <var class="Arg">f</var> to the weakly connected components of its transition graph Gamma_f,m.</p>
<p>The product of the returned mappings is <var class="Arg">f</var>. They have pairwise disjoint supports, hence any two of them commute.</p>
<table class="example">
<tr><td><pre>
gap> sigma := ClassTransposition(1,4,2,4) * ClassTransposition(1,4,3,4)
> * ClassTransposition(3,9,6,18) * ClassTransposition(1,6,3,9);;
gap> List(FactorizationOnConnectedComponents(sigma,36),Support);
[ 33(36) U 34(36) U 35(36), 9(36) U 10(36) U 11(36),
<union of 23 residue classes (mod 36)> \ [ -6, 3 ] ]
</pre></td></tr></table>
<p><a id="X7B6833D67D916EF9" name="X7B6833D67D916EF9"></a></p>
<h5>2.8-7 TransitionMatrix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TransitionMatrix</code>( <var class="Arg">f, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The transition matrix of the rcwa mapping <var class="Arg">f</var> for modulus <var class="Arg">m</var>.</p>
<p>Let M be this matrix. Then for any two residue classes r_1(m), r_2(m) in R/mR, the entry M_r_1(m),r_2(m) is defined by</p>
<p><center> <img src = "transmat.png" width = "599" height = "47" alt = "(see the PDF version of the manual),"/> </center> where hatm is the product of <var class="Arg">m</var> and the square of the modulus of <var class="Arg">f</var>. The assignment of the residue classes (mod <var class="Arg">m</var>) to the rows and columns of the matrix corresponds to the ordering of the residues in <code class="code">AllResidues(Source(<var class="Arg">f</var>),<var class="Arg">m</var>)</code>.</p>
<p>The transition matrix is a weighted adjacency matrix of the corresponding transition graph <code class="code">TransitionGraph(<var class="Arg">f</var>,<var class="Arg">m</var>)</code>. The sums of the rows of a transition matrix are always equal to 1.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> Display(TransitionMatrix(T^3,3));
[ [ 1/8, 1/4, 5/8 ],
[ 0, 1/4, 3/4 ],
[ 0, 3/8, 5/8 ] ]
</pre></td></tr></table>
<p><a id="X81DBA2D58526BE7E" name="X81DBA2D58526BE7E"></a></p>
<h5>2.8-8 <span class="Heading"> Sources & Sinks (of an rcwa mapping) </span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Sources</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Sinks</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A list of unions of residue classes modulo the modulus m of the rcwa mapping <var class="Arg">f</var>, as described below.</p>
<p>The returned list contains an entry for any strongly connected component of the transition graph of <var class="Arg">f</var> for modulus <code class="code">Mod(<var class="Arg">f</var>)</code> which has only outgoing edges ("source") or which has only ingoing edges ("sink"), respectively. The list entry corresponding to such a component is the union of the vertices belonging to it.</p>
<table class="example">
<tr><td><pre>
gap> g := ClassTransposition(0,2,1,2)*ClassTransposition(0,2,1,4);;
gap> Sources(g); Sinks(g);
[ 0(4) ]
[ 1(4) ]
</pre></td></tr></table>
<p><a id="X80221A4D81AF7453" name="X80221A4D81AF7453"></a></p>
<h5>2.8-9 Loops</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Loops</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>If <var class="Arg">f</var> is bijective, the list of non-isolated vertices of the transition graph of <var class="Arg">f</var> for modulus <code class="code">Mod(<var class="Arg">f</var>)</code> which carry a loop. In general, the list of vertices of that transition graph which carry a loop, but which <var class="Arg">f</var> does not fix setwise.</p>
<table class="example">
<tr><td><pre>
gap> Loops(ClassTransposition(0,2,1,2)*ClassTransposition(0,2,1,4));
[ 0(4), 1(4) ]
</pre></td></tr></table>
<p>There is a nice invariant of trajectories of the Collatz mapping:</p>
<p><a id="X8773152E81A30123" name="X8773152E81A30123"></a></p>
<h5>2.8-10 GluckTaylorInvariant</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GluckTaylorInvariant</code>( <var class="Arg">a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The invariant introduced in <a href="chapBib.html#biBGluckTaylor02">[GT02]</a>. This is (sum_i=1^l a_i * a_i mod l + 1)/(sum_i=1^l a_i^2), where l denotes the length of <var class="Arg">a</var>.</p>
<p>The argument <var class="Arg">a</var> must be a list of integers. In <a href="chapBib.html#biBGluckTaylor02">[GT02]</a> it is shown that if <var class="Arg">a</var> is a trajectory of the `original' Collatz mapping n -> (n/2 if n even, 3n+1 if n odd) starting at an odd integer >= 3 and ending at 1, then the invariant lies in the interval ]9/13,5/7[.</p>
<table class="example">
<tr><td><pre>
gap> C := RcwaMapping([[1,0,2],[3,1,1]]);;
gap> List([3,5..49],n->Float(GluckTaylorInvariant(Trajectory(C,n,[1]))));
[ 0.701053, 0.696721, 0.708528, 0.707684, 0.706635, 0.695636, 0.711769,
0.699714, 0.707409, 0.693833, 0.710432, 0.706294, 0.714242, 0.699935,
0.714242, 0.705383, 0.706591, 0.698198, 0.712222, 0.714242, 0.709048,
0.69612, 0.714241, 0.701076 ]
</pre></td></tr></table>
<p>Quite often one can make certain "educated guesses" on the overall behaviour of the trajectories of a given rcwa mapping. For example it is reasonably straightforward to make the conjecture that all trajectories of the Collatz mapping eventually enter the finite set -136, -91, -82, -68, -61, -55, -41, -37, -34, -25, -17, -10, -7, -5, -1, 0, 1, 2, or that "on average" the next number in a trajectory of the Collatz mapping is smaller than the preceding one by a factor of sqrt3/2. However it is clear that such guesses can be wrong, and that they therefore cannot be used to prove anything. Nevertheless they can sometimes be useful:</p>
<p><a id="X84F6A29280E2F925" name="X84F6A29280E2F925"></a></p>
<h5>2.8-11 LikelyContractionCentre</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LikelyContractionCentre</code>( <var class="Arg">f, maxn, bound</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A list of ring elements (see below).</p>
<p>This operation tries to compute the <em>contraction centre</em> of the rcwa mapping <var class="Arg">f</var>. Assuming its existence this is the unique finite subset S_0 of the source of <var class="Arg">f</var> on which <var class="Arg">f</var> induces a permutation and which intersects nontrivially with any trajectory of <var class="Arg">f</var>. The mapping <var class="Arg">f</var> is assumed to be <em>contracting</em>, i.e. to have such a contraction centre. As in general contraction centres are likely not computable, the methods for this operation are probabilistic and may return wrong results. The argument <var class="Arg">maxn</var> is a bound on the starting value and <var class="Arg">bound</var> is a bound on the elements of the trajectories to be searched. If the limit <var class="Arg">bound</var> is exceeded, an Info message on Info level 3 of <code class="code">InfoRCWA</code> is given.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; # The Collatz mapping.
gap> S0 := LikelyContractionCentre(T,100,1000);
#I Warning: `LikelyContractionCentre' is highly probabilistic.
The returned result can only be regarded as a rough guess.
See ?LikelyContractionCentre for more information.
[ -136, -91, -82, -68, -61, -55, -41, -37, -34, -25, -17, -10, -7, -5,
-1, 0, 1, 2 ]
</pre></td></tr></table>
<p><a id="X81E0D8E3817B3D16" name="X81E0D8E3817B3D16"></a></p>
<h5>2.8-12 GuessedDivergence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuessedDivergence</code>( <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A floating point value which is intended to be a rough guess on how fast the trajectories of the rcwa mapping <var class="Arg">f</var> diverge (return value greater than 1) or converge (return value smaller than 1).</p>
<p>Nothing particular is guaranteed.</p>
<table class="example">
<tr><td><pre>
gap> GuessedDivergence(T);
#I Warning: GuessedDivergence: no particular return value is guaranteed.
0.866025
</pre></td></tr></table>
<p><a id="X83FA71DD842377F0" name="X83FA71DD842377F0"></a></p>
<h4>2.9 <span class="Heading">The categories and families of rcwa mappings</span></h4>
<p><a id="X7927C13782729CE9" name="X7927C13782729CE9"></a></p>
<h5>2.9-1 IsRcwaMapping</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRcwaMapping</code>( <var class="Arg">f</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRcwaMappingOfZ</code>( <var class="Arg">f</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRcwaMappingOfZ_pi</code>( <var class="Arg">f</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRcwaMappingOfGFqx</code>( <var class="Arg">f</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p><b>Returns: </b><code class="code">true</code> if <var class="Arg">f</var> is an rcwa mapping, an rcwa mapping of the ring of integers, an rcwa mapping of a semilocalization of the ring of integers or an rcwa mapping of a polynomial ring in one variable over a finite field, respectively, and <code class="code">false</code> otherwise.</p>
<p>Often the same methods can be used for rcwa mappings of the ring of integers and of its semilocalizations. For this reason there is a category <code class="code">IsRcwaMappingOfZOrZ_pi</code> which is the union of <code class="code">IsRcwaMappingOfZ</code> and <code class="code">IsRcwaMappingOfZ_pi</code>. The internal representation of rcwa mappings is called <code class="code">IsRcwaMappingStandardRep</code>. There are methods available for <code class="code">ExtRepOfObj</code> and <code class="code">ObjByExtRep</code>.</p>
<p><a id="X825DD365822934AF" name="X825DD365822934AF"></a></p>
<h5>2.9-2 RcwaMappingsFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RcwaMappingsFamily</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The family of rcwa mappings of the ring <var class="Arg">R</var>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.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
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2835
