| products/Sources/formale Sprachen/GAP/pkg/rcwa/doc/chap4_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 4: Residue-Class-Wise Affine Monoids</ 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= "chap4" 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="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap4.html">[MathJax off]</a></p>
<p><a id="X81C90F7C7BA25BDF" name="X81C90F7C7BA25BDF"></a></p>
<div class="ChapSects"><a href="chap4_mj.html#X81C90F7C7BA25BDF">4 <span class="Heading">Residue-Class-Wise Affine Monoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X83D42E26849D5580">4.1 <span class="Heading">Constructing residue-class-wise affine monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7B95FCA279E0D6CC">4.1-1 Rcwa</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X8759954F7EB1A658">4.2 <span class="Heading">Computing with residue-class-wise affine monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X87DB896687475084">4.2-1 ShortOrbits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X787848137DF1C245">4.2-2 <span class="Heading">
Ball (for monoid, element and radius or monoid, point, radius and action)
</span></a>
</span>
</div></div>
</div>
<h3>4 <span class="Heading">Residue-Class-Wise Affine Monoids</span></h3>
<p>In this short chapter, we describe how to compute with residue-class-wise affine monoids. <em>Residue-class-wise affine</em> monoids, or <em>rcwa</em> monoids for short, are monoids whose elements are residue-class-wise affine mappings.</p>
<p><a id="X83D42E26849D5580" name="X83D42E26849D5580"></a></p>
<h4>4.1 <span class="Heading">Constructing residue-class-wise affine monoids</span></h4>
<p>As any other monoids in <strong class="pkg">GAP</strong>, residue-class-wise affine monoids can be constructed by <code class="code">Monoid</code> or <code class="code">MonoidByGenerators</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := Monoid(RcwaMapping([[ 0,1,1],[1,1,1]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> RcwaMapping([[-1,3,1],[0,2,1]]));</span>
<rcwa monoid over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(M);</span>
11
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(MultiplicationTable(M));</span>
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ],
[ 2, 8, 5, 11, 8, 3, 10, 5, 2, 8, 5 ],
[ 3, 10, 11, 5, 5, 5, 8, 8, 8, 2, 3 ],
[ 4, 9, 6, 8, 8, 8, 5, 5, 5, 7, 4 ],
[ 5, 8, 5, 8, 8, 8, 5, 5, 5, 8, 5 ],
[ 6, 7, 4, 8, 8, 8, 5, 5, 5, 9, 6 ],
[ 7, 5, 8, 6, 5, 4, 9, 8, 7, 5, 8 ],
[ 8, 5, 8, 5, 5, 5, 8, 8, 8, 5, 8 ],
[ 9, 5, 8, 4, 5, 6, 7, 8, 9, 5, 8 ],
[ 10, 8, 5, 3, 8, 11, 2, 5, 10, 8, 5 ],
[ 11, 2, 3, 5, 5, 5, 8, 8, 8, 10, 11 ] ]
</pre></div>
<p>There are methods for the operations <code class="code">View</code>, <code class="code">Display</code>, <code class="code">Print</code> and <code class="code">String</code> which are applicable to rcwa monoids. All rcwa monoids over a ring <span class="SimpleMath">\(R\)</span> are submonoids of Rcwa(<span class="SimpleMath">\(R\)</span>). The monoid Rcwa(<span class="SimpleMath">\(R\)</span>) itself is not finitely generated, thus cannot be constructed as described above. It is handled as a special case:</p>
<p><a id="X7B95FCA279E0D6CC" name="X7B95FCA279E0D6CC"></a></p>
<h5>4.1-1 Rcwa</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Rcwa</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the monoid Rcwa(<var class="Arg">R</var>) of all residue-class-wise affine mappings of the ring <var class="Arg">R</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RcwaZ := Rcwa(Integers);</span>
Rcwa(Z)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(RcwaZ,M);</span>
true
</pre></div>
<p>In our methods to construct rcwa groups, two kinds of mappings played a crucial role, namely the restriction monomorphisms (cf. <code class="func">Restriction</code> (<a href="chap3_mj.html#X852EF2C079E4D7FF"><span class="RefLink">3.1-6</span></a>)) and the induction epimorphisms (cf. <code class="func">Induction</code> (<a href="chap3_mj.html#X82171D7287CBED95"><span class="RefLink">3.1-7</span></a>)). The restriction monomorphisms extend in a natural way to the monoids Rcwa(<span class="SimpleMath">\(R\)</span>), and the induction epimorphisms have corresponding generalizations, also. Therefore the operations <code class="code">Restriction</code> and <code class="code">Induction</code> can be applied to rcwa monoids as well:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M2 := Restriction(M,2*One(Rcwa(Integers)));</span>
<rcwa monoid over Z with 2 generators, of size 11>
<span class="GAPprompt">gap></span> <span class="GAPinput">Support(M2);</span>
0(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">Action(M2,ResidueClass(1,2));</span>
Trivial rcwa monoid over Z
<span class="GAPprompt">gap></span> <span class="GAPinput">Induction(M2,2*One(Rcwa(Integers))) = M;</span>
true
</pre></div>
<p><a id="X8759954F7EB1A658" name="X8759954F7EB1A658"></a></p>
<h4>4.2 <span class="Heading">Computing with residue-class-wise affine monoids</span></h4>
<p>There is a method for <code class="code">Size</code> which computes the order of an rcwa monoid. Further there is a method for <code class="code">in</code> which checks whether a given rcwa mapping lies in a given rcwa monoid (membership test), and there is a method for <code class="code">IsSubset</code> which checks for a submonoid relation.</p>
<p>There are also methods for <code class="code">Support</code>, <code class="code">Modulus</code>, <code class="code">IsTame</code>, <code class="code">PrimeSet</code>, <code class="code">IsIntegral</code>, <code class="code">IsClassWiseOrderPreserving</code> and <code class="code">IsSignPreserving</code> available for rcwa monoids.</p>
<p>The <em>support</em> of an rcwa monoid is the union of the supports of its elements. The <em>modulus</em> of an rcwa monoid is the lcm of the moduli of its elements in case such an lcm exists and 0 otherwise. An rcwa monoid is called <em>tame</em> if its modulus is nonzero, and <em>wild</em> otherwise. The <em>prime set</em> of an rcwa monoid is the union of the prime sets of its elements. An rcwa monoid is called <em>integral</em>, <em>class-wise order-preserving</em> or <em>sign-preserving</em> if all of its elements are so.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := RcwaMapping([[-1, 1, 1],[ 0,-1, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := RcwaMapping([[ 1,-1, 1],[-1,-2, 1],[-1, 2, 1]]);; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f3 := RcwaMapping([[ 1, 0, 1],[-1, 0, 1]]);; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">N := Monoid(f1,f2,f3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(N);</span>
366
<span class="GAPprompt">gap></span> <span class="GAPinput">List([Monoid(f1,f2),Monoid(f1,f3),Monoid(f2,f3)],Size);</span>
[ 96, 6, 66 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f1*f2*f3 in N;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(N,M);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(N,Monoid(f1*f2,f3*f2));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Support(N);</span>
Integers
<span class="GAPprompt">gap></span> <span class="GAPinput">Modulus(N);</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(N) and IsIntegral(N);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsClassWiseOrderPreserving(N) or IsSignPreserving(N);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected(List(AsList(N),Image)); # The images of the elements of N.</span>
[ [ Integers, 2 ], [ 1(2), 2 ], [ Z \ 1(3), 32 ], [ 0(6), 44 ],
[ 0(6) U 1(6), 4 ], [ Z \ 4(6) U 5(6), 32 ], [ 0(6) U 2(6), 4 ],
[ 0(6) U 5(6), 4 ], [ 1(6), 44 ], [ 1(6) U [ -1 ], 2 ],
[ 1(6) U 3(6), 4 ], [ 1(6) U 5(6), 40 ], [ 2(6), 44 ],
[ 2(6) U 3(6), 4 ], [ 3(6), 44 ], [ 3(6) U 5(6), 4 ], [ 5(6), 44 ],
[ 5(6) U [ 1 ], 2 ], [ [ -5 ], 1 ], [ [ -4 ], 1 ], [ [ -3 ], 1 ],
[ [ -1 ], 1 ], [ [ 0 ], 1 ], [ [ 1 ], 1 ], [ [ 2 ], 1 ], [ [ 3 ], 1 ],
[ [ 5 ], 1 ], [ [ 6 ], 1 ] ]
</pre></div>
<p>Finite forward orbits under the action of an rcwa monoid can be found by the operation <code class="code">ShortOrbits</code>:</p>
<p><a id="X87DB896687475084" name="X87DB896687475084"></a></p>
<h5>4.2-1 ShortOrbits</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ShortOrbits</code>( <var class="Arg">M</var>, <var class="Arg">S</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a list of finite forward orbits of the rcwa monoid <var class="Arg">M</var> of length at most <var class="Arg">maxlng</var> which start at points in the set <var class="Arg">S</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortOrbits(M,[-5..5],20);</span>
[ [ -5, -4, 1, 2, 7, 8 ], [ -3, -2, 1, 2, 5, 6 ], [ -1 .. 4 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(Action(M,last[1]),"\n");</span>
Monoid( [ Transformation( [ 2, 3, 4, 3, 6, 3 ] ),
Transformation( [ 4, 5, 4, 3, 4, 1 ] ) ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">orbs := ShortOrbits(N,[0..10],100);</span>
[ [ -5, -4, -3, -1, 0, 1, 2, 3, 5, 6 ],
[ -11, -10, -9, -7, -6, -5, -4, -3, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
11, 12 ],
[ -17, -16, -15, -13, -12, -11, -10, -9, -7, -6, -5, -4, -3, -1, 0, 1,
2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">quots := List(orbs,orb->Action(N,orb));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(quots,Size);</span>
[ 268, 332, 366 ]
</pre></div>
<p>Balls of given radius around an element of an rcwa monoid can be computed by the operation <code class="code">Ball</code>. This operation can also be used for computing forward orbits or subsets of such under the action of an rcwa monoid:</p>
<p><a id="X787848137DF1C245" name="X787848137DF1C245"></a></p>
<h5>4.2-2 <span class="Heading">
Ball (for monoid, element and radius or monoid, point, radius and action)
</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Ball</code>( <var class="Arg">M</var>, <var class="Arg">f</var>, <var class="Arg">r</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">&#an style='color: green'>8227; Ball</code>( <var class="Arg">M</var>, <var class="Arg">p</var>, <var class="Arg">r</var>, <var class="Arg">action</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the ball of radius <var class="Arg">r</var> around the element <var class="Arg">f</var> in the monoid <var class="Arg">M</var>, respectively the ball of radius <var class="Arg">r</var> around the point <var class="Arg">p</var> under the action <var class="Arg">action</var> of the monoid <var class="Arg">M</var>.</p>
<p>All balls are understood with respect to <code class="code">GeneratorsOfMonoid(<var class="Arg">M</var>)</code>. As membership tests can be expensive, the first-mentioned method does not check whether <var class="Arg">f</var> is indeed an element of <var class="Arg">M</var>. The methods require that point- / element comparisons are cheap. They are not only applicable to rcwa monoids. If the option <var class="Arg">Spheres</var> is set, the ball is split up and returned as a list of spheres.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([0..12],k->Length(Ball(N,One(N),k)));</span>
[ 1, 4, 11, 26, 53, 99, 163, 228, 285, 329, 354, 364, 366 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Ball(N,[0..3],2,OnTuples);</span>
[ [ -3, 3, 3, 3 ], [ -1, -3, 0, 2 ], [ -1, -1, -1, -1 ],
[ -1, -1, 1, -1 ], [ -1, 1, 1, 1 ], [ -1, 3, 0, -4 ], [ 0, -1, 2, -3 ],
[ 0 .. 3 ], [ 1, -1, -1, -1 ], [ 1, 3, 0, 2 ], [ 3, -4, -1, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l := 2*IdentityRcwaMappingOfZ; r := l+1;</span>
Rcwa mapping of Z: n -> 2n
Rcwa mapping of Z: n -> 2n + 1
<span class="GAPprompt">gap></span> <span class="GAPinput">Ball(Monoid(l,r),1,4,OnPoints:Spheres);</span>
[ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ], [ 8, 9, 10, 11, 12, 13, 14, 15 ],
[ 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 ] ]
</pre></div>
<p> </p>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><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>
<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.9 Sekunden
¤
*© Formatika GbR, Deutschland
|
|
