Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/rcwa/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 22.8.2025 mit Größe 118 kB image not shown  

Quelle  chap3.html

  Sprache: HTML 		 

 products/Sources/formale Sprachen/GAP/pkg/rcwa/doc/chap3.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (RCWA) - Chapter 3: Residue-Class-Wise Affine Groups</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="chap3"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap2.html">[Previous Chapter]</a>    <a href="chap4.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X874A3BB684F0639A" name="X874A3BB684F0639A"></a></p>
<div class="ChapSects"><a href="chap3.html#X874A3BB684F0639A">3 <span class="Heading">Residue-Class-Wise Affine Groups</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X81242A6586A604A3">3.1 <span class="Heading">Constructing residue-class-wise affine groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7EB8A301790290C7">3.1-1 IsomorphismRcwaGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X79CAE48981C11FE8">3.1-2 DirectProduct</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80D13D2A7AD73C2C">3.1-3 <span class="Heading">
    WreathProduct
    (for an rcwa group over Z, with a permutation group or (ℤ,+))
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8794913B878DD5C4">3.1-4 MergerExtension</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8143AB647801F438">3.1-5 GroupByResidueClasses</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X852EF2C079E4D7FF">3.1-6 <span class="Heading">
    Restriction (of an rcwa mapping or -group, by an injective rcwa mapping)
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X82171D7287CBED95">3.1-7 <span class="Heading">
    Induction (of an rcwa mapping or -group, by an injective rcwa mapping)
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X79450C1C8756FEB3">3.1-8 RCWA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7BD42D8481300E25">3.1-9 CT</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X80C042BE82EE0F9A">3.2 <span class="Heading">
  Basic routines for investigating residue-class-wise affine groups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X864A7E3E87F366A8">3.2-1 StructureDescription</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X83527DA37C5CB2C7">3.2-2 EpimorphismFromFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8463E34286344F06">3.2-3 PreImagesRepresentative</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X8151BE577FFDCE87">3.3 <span class="Heading">
  The natural action of an rcwa group on the underlying ring
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7C046BE97EE53692">3.3-1 <span class="Heading"> Orbit (for an rcwa group and either a point or a set) </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7B7A3AF97D195E33">3.3-2 GrowthFunctionOfOrbit</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7D9DFAC97F9F0891">3.3-3 DrawOrbitPicture</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X78F145197F63A25D">3.3-4 <span class="Heading">
    ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations)
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80D18D0778A96C16">3.3-5 <span class="Heading">
    ShortResidueClassOrbits & ShortResidueClassCycles
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80C080287A355EFF">3.3-6 ComputeCycleLength</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7F76B04E86C77B94">3.3-7 CycleRepresentativesAndLengths</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8777A62286597D53">3.3-8 FixedResidueClasses</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8735855587CC029F">3.3-9 <span class="Heading">
    Ball (for group, element and radius or group, point, radius and action)
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X87A3462C82FD376E">3.3-10 RepresentativeAction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8587246A7F890849">3.3-11 ProjectionsToInvariantUnionsOfResidueClasses</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X866843D08213067E">3.3-12 RepresentativeAction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X82DBAF35788FA239">3.3-13 CollatzLikeMappingByOrbitTree</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X781CBEFA7F39B58D">3.4 <span class="Heading">
  Special attributes of tame residue-class-wise affine groups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7F523A6B87825AB8">3.4-1 <span class="Heading">
    RespectedPartition (of a tame rcwa group or -permutation)
  </span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X831ADC1584DE6113">3.4-2 <span class="Heading">
    ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
  </span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X81941A247942FB99">3.5 <span class="Heading">Generating pseudo-random elements of RCWA(R) and CT(R)</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X86327F6C83D09798">3.6 <span class="Heading">The categories of residue-class-wise affine groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X84AFBB997B694A3D">3.6-1 IsRcwaGroup</a></span>
</div></div>
</div>

<h3>3 <span class="Heading">Residue-Class-Wise Affine Groups</span></h3>

<p>In this chapter, we describe how to construct residue-class-wise affine groups and how to compute with them.</p>

<p><a id="X81242A6586A604A3" name="X81242A6586A604A3"></a></p>

<h4>3.1 <span class="Heading">Constructing residue-class-wise affine groups</span></h4>

<p>As any other groups in <strong class="pkg">GAP</strong>, residue-class-wise affine (rcwa-) groups can be constructed by <code class="code">Group</code>, <code class="code">GroupByGenerators</code> or <code class="code">GroupWithGenerators</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5));</span>
<rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(G); Size(G); IsSolvable(G); IsPerfect(G);</span>
true
infinity
false
false

</pre></div>

<p>An rcwa group isomorphic to a given group can be obtained by taking the image of a faithful rcwa representation:</p>

<p><a id="X7EB8A301790290C7" name="X7EB8A301790290C7"></a></p>

<h5>3.1-1 IsomorphismRcwaGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismRcwaGroup</code>( <var class="Arg">G</var>, <var class="Arg">R</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">‣ IsomorphismRcwaGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a monomorphism from the group <var class="Arg">G</var> to RCWA(<var class="Arg">R</var>) or to RCWA(ℤ), respectively.</p>

<p>The best-supported case is <var class="Arg">R</var> = ℤ. Currently there are methods available for finite groups, for free products of finite groups and for free groups. The method for free products of finite groups uses the Table-Tennis Lemma (cf. e.g. Section II.B. in <a href="chapBib.html#biBLaHarpe00">[dlH00]</a>), and the method for free groups uses an adaptation of the construction given on page 27 in <a href="chapBib.html#biBLaHarpe00">[dlH00]</a> from PSL(2,ℂ) to RCWA(ℤ).</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeProduct(Group((1,2)(3,4),(1,3)(2,4)),Group((1,2,3)),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    SymmetricGroup(3));</span>
<fp group on the generators [ f1, f2, f3, f4, f5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismRcwaGroup(F);</span>
[ f1, f2, f3, f4, f5 ] -> [ <rcwa permutation of Z with modulus 12>,
  <rcwa permutation of Z with modulus 24>,
  <rcwa permutation of Z with modulus 12>,
  <rcwa permutation of Z with modulus 72>,
  <rcwa permutation of Z with modulus 36> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismRcwaGroup(FreeGroup(2));</span>
[ f1, f2 ] -> [ <wild rcwa permutation of Z with modulus 8>,
  <wild rcwa permutation of Z with modulus 8> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">F2 := Image(last);</span>
<wild rcwa group over Z with 2 generators>

</pre></div>

<p>Further, new rcwa groups can be constructed from given ones by taking direct products and by taking wreath products with finite groups or with the infinite cyclic group:</p>

<p><a id="X79CAE48981C11FE8" name="X79CAE48981C11FE8"></a></p>

<h5>3.1-2 DirectProduct</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DirectProduct</code>( <var class="Arg">G1</var>, <var class="Arg">G2</var>, <var class="Arg">...</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an rcwa group isomorphic to the direct product of the rcwa groups over ℤ given as arguments.</p>

<p>There is certainly no unique or canonical way to embed a direct product of rcwa groups into RCWA(ℤ). This method chooses to embed the groups <var class="Arg">G1</var>, <var class="Arg">G2</var>, <var class="Arg">G3</var> ... via restrictions by <span class="SimpleMath">n ↦ mn</span>, <span class="SimpleMath">n ↦ mn+1</span>, <span class="SimpleMath">n ↦ mn+2</span> ... (<span class="SimpleMath">→</span> <code class="func">Restriction</code> (<a href="chap3.html#X852EF2C079E4D7FF"><span class="RefLink">3.1-6</span></a>)), where <span class="SimpleMath">m</span> denotes the number of groups given as arguments.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">F2xF2 := DirectProduct(F2,F2);</span>
<wild rcwa group over Z with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Image(Projection(F2xF2,1)) = F2;</span>
true

</pre></div>

<p><a id="X80D13D2A7AD73C2C" name="X80D13D2A7AD73C2C"></a></p>

<h5>3.1-3 <span class="Heading">
    WreathProduct
    (for an rcwa group over Z, with a permutation group or (ℤ,+))
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WreathProduct</code>( <var class="Arg">G</var>, <var class="Arg">P</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">‣ WreathProduct</code>( <var class="Arg">G</var>, <var class="Arg">Z</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an rcwa group isomorphic to the wreath product of the rcwa group <var class="Arg">G</var> over ℤ with the finite permutation group <var class="Arg">P</var> or with the infinite cyclic group <var class="Arg">Z</var>, respectively.</p>

<p>The first-mentioned method embeds the <code class="code">NrMovedPoints(<var class="Arg">P</var>)</code>th direct power of <var class="Arg">G</var> using the method for <code class="code">DirectProduct</code>, and lets the permutation group <var class="Arg">P</var> act naturally on the set of residue classes modulo <code class="code">NrMovedPoints(<var class="Arg">P</var>)</code>. The second-mentioned method restricts (<span class="SimpleMath">→</span> <code class="func">Restriction</code> (<a href="chap3.html#X852EF2C079E4D7FF"><span class="RefLink">3.1-6</span></a>)) the group <var class="Arg">G</var> to the residue class 3(4), and maps the generator of the infinite cyclic group <var class="Arg">Z</var> to <code class="code">ClassTransposition(0,2,1,2) * ClassTransposition(0,2,1,4)</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">F2wrA5 := WreathProduct(F2,AlternatingGroup(5));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Embedding(F2wrA5,1);</span>
[ <wild rcwa permutation of Z with modulus 8>,
  <wild rcwa permutation of Z with modulus 8> ] ->
[ <wild rcwa permutation of Z with modulus 40>,
  <wild rcwa permutation of Z with modulus 40> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Embedding(F2wrA5,2);</span>
[ (1,2,3,4,5), (3,4,5) ] -> [ ( 0(5), 1(5), 2(5), 3(5), 4(5) ), 
  ( 2(5), 3(5), 4(5) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1)));</span>
<wild rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Embedding(ZwrZ,1);</span>
[ ClassShift( Z ) ] ->
[ <tame rcwa permutation of Z with modulus 4, of order infinity> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Embedding(ZwrZ,2);</span>
[ ClassShift( Z ) ] -> [ <wild rcwa permutation of Z with modulus 4> ]

</pre></div>

<p>Also, rcwa groups can be obtained as particular extensions of finite permutation groups:</p>

<p><a id="X8794913B878DD5C4" name="X8794913B878DD5C4"></a></p>

<h5>3.1-4 MergerExtension</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MergerExtension</code>( <var class="Arg">G</var>, <var class="Arg">points</var>, <var class="Arg">point</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: roughly spoken, an extension of <var class="Arg">G</var> by an involution which <q>merges</q> <var class="Arg">points</var> into <var class="Arg">point</var>.</p>

<p>The arguments of this operation are a finite permutation group <var class="Arg">G</var>, a set <var class="Arg">points</var> of points moved by <var class="Arg">G</var> and a single point <var class="Arg">point</var> moved by <var class="Arg">G</var> which is not in <var class="Arg">points</var>.</p>

<p>Let <span class="SimpleMath">n</span> be the largest moved point of <var class="Arg">G</var>, and let <span class="SimpleMath">H</span> be the tame subgroup of CT(ℤ) which respects the partition <span class="SimpleMath">mathcalP</span> of ℤ into the residue classes (mod <span class="SimpleMath">n</span>), and which acts on <span class="SimpleMath">mathcalP</span> as <var class="Arg">G</var> acts on <span class="SimpleMath">{1, dots, n}</span>. Further assume that <var class="Arg">points</var> = <span class="SimpleMath">{p_1, dots, p_k}</span> and <var class="Arg">point</var> = <span class="SimpleMath">p</span>, and put <span class="SimpleMath">r_i := p_i-1, i = 1, dots, k</span> and <span class="SimpleMath">r := p-1</span>. Now let <span class="SimpleMath">σ</span> be the product of the class transpositions <span class="SimpleMath">τ_r_i(n),r+(i-1)n(kn), i = 1, dots, k</span>. The group returned by this operation is the extension of <span class="SimpleMath">H</span> by the involution <span class="SimpleMath">σ</span>. -- On first reading, this may look a little complicated, but really the code of the method is only about half as long as this description.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput"># First example -- a group isomorphic to PSL(2,Z):</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := MergerExtension(Group((1,2,3)),[1,2],3);</span>
<rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(G); </span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(G);</span>
[ ( 0(3), 1(3), 2(3) ), ( 0(3), 2(6) ) ( 1(3), 5(6) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">B := Ball(G,One(G),6:Spheres);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(B,Length);</span>
[ 1, 3, 4, 6, 8, 12, 16 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">#</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># Second example -- a group isomorphic to Thompson's group V:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := MergerExtension(Group((1,2,3,4),(1,2)),[1,2],3);</span>
<rcwa group over Z with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(G);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(G);</span>
[ ( 0(4), 1(4), 2(4), 3(4) ), ( 0(4), 1(4) ),
  ( 0(4), 2(8) ) ( 1(4), 6(8) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">B := Ball(G,One(G),6:Spheres);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(B,Length);</span>
[ 1, 4, 11, 28, 69, 170, 413 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G = Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                  ClassTransposition));</span>
true

</pre></div>

<p>It is also possible to build an rcwa group from a list of residue classes:</p>

<p><a id="X8143AB647801F438" name="X8143AB647801F438"></a></p>

<h5>3.1-5 GroupByResidueClasses</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GroupByResidueClasses</code>( <var class="Arg">classes</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the group which is generated by all class transpositions which interchange disjoint residue classes in <var class="Arg">classes</var>.</p>

<p>The argument <var class="Arg">classes</var> must be a list of residue classes.</p>

<p>If the residue classes in <var class="Arg">classes</var> are pairwise disjoint, then the returned group is the symmetric group on <var class="Arg">classes</var>. If any two residue classes in <var class="Arg">classes</var> intersect non-trivially, then the returned group is trivial. In many other cases, the returned group is infinite.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := GroupByResidueClasses(List([[0,2],[0,4],[1,4],[2,4],[3,4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                   ResidueClass));</span>
<rcwa group over Z with 8 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                   ClassTransposition)); # Thompson's group V</span>
<(0(2),1(2)),(1(2),2(4)),(0(2),1(4)),(1(4),2(4))>
<span class="GAPprompt">gap></span> <span class="GAPinput">G = H;</span>
true

</pre></div>

<p>Various ways to construct rcwa groups are based on certain monomorphisms from the group RCWA(<span class="SimpleMath">R</span>) into itself. Examples are the constructions of direct products and wreath products described above. The support of the image of such a monomorphism is the image of a given injective rcwa mapping. For this reason, these monomorphisms are called <em>restriction monomorphisms</em>. The following operation computes images of rcwa mappings and -groups under these embeddings of RCWA(<span class="SimpleMath">R</span>) into itself:</p>

<p><a id="X852EF2C079E4D7FF" name="X852EF2C079E4D7FF"></a></p>

<h5>3.1-6 <span class="Heading">
    Restriction (of an rcwa mapping or -group, by an injective rcwa mapping)
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Restriction</code>( <var class="Arg">g</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Restriction</code>( <var class="Arg">G</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the restriction of the rcwa mapping <var class="Arg">g</var> (respectively the rcwa group <var class="Arg">G</var>) by the injective rcwa mapping <var class="Arg">f</var>.</p>

<p>By definition, the <em>restriction</em> <span class="SimpleMath">g_f</span> of an rcwa mapping <var class="Arg">g</var> by an injective rcwa mapping <var class="Arg">f</var> is the unique rcwa mapping which satisfies the equation <span class="SimpleMath">f ⋅ g_f = g ⋅ f</span> and which fixes the complement of the image of <var class="Arg">f</var> pointwise. If <var class="Arg">f</var> is bijective, the restriction of <var class="Arg">g</var> by <var class="Arg">f</var> is just the conjugate of <var class="Arg">g</var> under <var class="Arg">f</var>.</p>

<p>The <em>restriction</em> of an rcwa group <var class="Arg">G</var> by an injective rcwa mapping <var class="Arg">f</var> is defined as the group whose elements are the restrictions of the elements of <var class="Arg">G</var> by <var class="Arg">f</var>. The restriction of <var class="Arg">G</var> by <var class="Arg">f</var> acts on the image of <var class="Arg">f</var> and fixes its complement pointwise.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F2tilde := Restriction(F2,RcwaMapping([[5,3,1]]));</span>
<wild rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Support(F2tilde);</span>
3(5)

</pre></div>

<p><a id="X82171D7287CBED95" name="X82171D7287CBED95"></a></p>

<h5>3.1-7 <span class="Heading">
    Induction (of an rcwa mapping or -group, by an injective rcwa mapping)
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Induction</code>( <var class="Arg">g</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Induction</code>( <var class="Arg">G</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the induction of the rcwa mapping <var class="Arg">g</var> (respectively the rcwa group <var class="Arg">G</var>) by the injective rcwa mapping <var class="Arg">f</var>.</p>

<p><em>Induction</em> is the right inverse of restriction, i.e. it is <code class="code">Induction(Restriction(<var class="Arg">g</var>,<var class="Arg">f</var>),<var class="Arg">f</var>) = <var class="Arg">g</var></code> and <code class="code">Induction(Restriction(<var class="Arg">G</var>,<var class="Arg">f</var>),<var class="Arg">f</var>) = <var class="Arg">G</var></code>. The mapping <var class="Arg">g</var> respectively the group <var class="Arg">G</var> must not move points outside the image of <var class="Arg">f</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">Induction(F2tilde,RcwaMapping([[5,3,1]])) = F2;</span>
true

</pre></div>

<p>Once having constructed an rcwa group, it is sometimes possible to obtain a smaller generating set by the operation <code class="code">SmallGeneratingSet</code>.</p>

<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 groups.</p>

<p>Basic attributes of an rcwa group which are derived from the coefficients of its elements are <code class="code">Modulus</code>, <code class="code">Multiplier</code>, <code class="code">Divisor</code> and <code class="code">PrimeSet</code>. The <em>modulus</em> of an rcwa group is the lcm of the moduli of its elements if such an lcm exists, i.e. if the group is tame, and 0 otherwise. The <em>multiplier</em> respectively <em>divisor</em> of an rcwa group is the lcm of the multipliers respectively divisors of its elements in case such an lcm exists and <span class="SimpleMath">∞</span> otherwise. The <em>prime set</em> of an rcwa group is the union of the prime sets of its elements. There are shorthands <code class="code">Mod</code>, <code class="code">Mult</code> and <code class="code">Div</code> defined for <code class="code">Modulus</code>, <code class="code">Multiplier</code> and <code class="code">Divisor</code>, respectively. An rcwa group is called <em>class-wise translating</em>, <em>integral</em> or <em>class-wise order-preserving</em> if all of its elements are so. There are corresponding methods available for <code class="code">IsClassWiseTranslating</code>, <code class="code">IsIntegral</code> and <code class="code">IsClassWiseOrderPreserving</code>. There is a property <code class="code">IsSignPreserving</code>, which indicates whether a given rcwa group over ℤ acts on the set of nonnegative integers. The latter holds for any subgroup of CT(ℤ) (cf. below).</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,6),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassReflection(2,4));</span>
<rcwa group over Z with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([Modulus,Multiplier,Divisor,PrimeSet,IsClassWiseTranslating,</span>
<span class="GAPprompt">></span> <span class="GAPinput">         IsIntegral,IsClassWiseOrderPreserving,IsSignPreserving],f->f(G));</span>
[ 24, 2, 2, [ 2, 3 ], false, false, false, false ]

</pre></div>

<p>All rcwa groups over a ring <span class="SimpleMath">R</span> are subgroups of RCWA(<span class="SimpleMath">R</span>). The group 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="X79450C1C8756FEB3" name="X79450C1C8756FEB3"></a></p>

<h5>3.1-8 RCWA</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RCWA</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the group RCWA(<var class="Arg">R</var>) of all residue-class-wise affine permutations of the ring <var class="Arg">R</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">RCWA_Z := RCWA(Integers);</span>
RCWA(Z)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(RCWA_Z,G);</span>
true

</pre></div>

<p>Examples of rcwa permutations can be obtained via <code class="code">Random(RCWA(<var class="Arg">R</var>))</code>, see Section <a href="chap3.html#X81941A247942FB99"><span class="RefLink">3.5</span></a>. The number of conjugacy classes of RCWA(ℤ) of elements of given order is known, cf. Corollary 2.7.1 (b) in <a href="chapBib.html#biBKohl05">[Koh05]</a>. It can be determined by the function <code class="code">NrConjugacyClassesOfRCWAZOfOrder</code>:</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">List([2,105],NrConjugacyClassesOfRCWAZOfOrder);</span>
[ infinity, 218 ]

</pre></div>

<p>We denote the group which is generated by all class transpositions of the ring <span class="SimpleMath">R</span> by CT(<span class="SimpleMath">R</span>). This group is handled as a special case as well:</p>

<p><a id="X7BD42D8481300E25" name="X7BD42D8481300E25"></a></p>

<h5>3.1-9 CT</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CT</code>( <var class="Arg">R</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">‣ CT</code>( <var class="Arg">P</var>, <var class="Arg">Integers</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the group CT(<var class="Arg">R</var>) which is generated by all class transpositions of the ring <var class="Arg">R</var>, respectively, the group CT(<var class="Arg">P</var>,ℤ) which is generated by all class transpositions of ℤ which interchange residue classes whose moduli have only prime factors in the finite set <var class="Arg">P</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">CT_Z := CT(Integers);</span>
CT(Z)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSimpleGroup(CT_Z); # One of a number of stored attributes/properties.</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">V := CT([2],Integers);</span>
CT_[ 2 ](Z)
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(V);</span>
[ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 0(2), 1(4) ), ( 1(4), 2(4) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G := CT([2,3],Integers); </span>
CT_[ 2, 3 ](Z)
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(G);</span>
[ ( 0(2), 1(2) ), ( 0(3), 1(3) ), ( 1(3), 2(3) ), ( 0(2), 1(4) ), 
  ( 0(2), 5(6) ), ( 0(3), 1(6) ) ]

</pre></div>

<p>The group CT(ℤ) has an outer automorphism which is given by conjugation with <span class="SimpleMath">n ↦ -n - 1</span>. This automorphism can be applied to an rcwa mapping of ℤ or to an rcwa group over ℤ by the operation <code class="code">Mirrored</code>. The group <code class="code">Mirrored(</code><var class="Arg">G</var><code class="code">)</code> acts on the nonnegative integers as <var class="Arg">G</var> acts on the negative integers, and vice versa.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">ct := ClassTransposition(0,2,1,6);</span>
( 0(2), 1(6) )
<span class="GAPprompt">gap></span> <span class="GAPinput">Mirrored(ct);</span>
( 1(2), 4(6) )
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,2,1,2],[0,3,2,3],[2,4,1,6]],ClassTransposition));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortOrbits(G,[-100..100],100);</span>
[ [ 0 .. 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortOrbits(Mirrored(G),[-100..100],100);</span>
[ [ -6 .. -1 ] ]

</pre></div>

<p>Under the hypothesis that CT(ℤ) is the setwise stabilizer of <span class="SimpleMath">ℕ_0</span> in RCWA(ℤ), the elements of CT(ℤ) with modulus dividing a given positive integer <span class="SimpleMath">m</span> are parametrized by the ordered partitions of ℤ into <span class="SimpleMath">m</span> residue classes. The list of these elements for given <span class="SimpleMath">m</span> can be obtained by the function <code class="code">AllElementsOfCTZWithGivenModulus</code>, and the numbers of such elements for <span class="SimpleMath">m ≤ 24</span> are stored in the list <code class="code">NrElementsOfCTZWithGivenModulus</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">NrElementsOfCTZWithGivenModulus{[1..8]};</span>
[ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680 ]

</pre></div>

<p>The number of conjugacy classes of CT(ℤ) of elements of given order is also known under the hypothesis that CT(ℤ) is the setwise stabilizer of <span class="SimpleMath">ℕ_0</span> in RCWA(ℤ). It can be determined by the function <code class="code">NrConjugacyClassesOfCTZOfOrder</code>.</p>

<p><a id="X80C042BE82EE0F9A" name="X80C042BE82EE0F9A"></a></p>

<h4>3.2 <span class="Heading">
  Basic routines for investigating residue-class-wise affine groups
</span></h4>

<p>In the previous section we have seen how to construct rcwa groups. The purpose of this section is to describe how to obtain information on the structure of an rcwa group and on its action on the underlying ring. The easiest way to get a little (but really only <em>a very little</em>!) information on the group structure is a dedicated method for the operation <code class="code">StructureDescription</code>:</p>

<p><a id="X864A7E3E87F366A8" name="X864A7E3E87F366A8"></a></p>

<h5>3.2-1 StructureDescription</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StructureDescription</code>( <var class="Arg">G</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a string which sometimes gives a little glimpse of the structure of the rcwa group <var class="Arg">G</var>.</p>

<p>The attribute <code class="code">StructureDescription</code> for finite groups is documented in the <strong class="pkg">GAP</strong> Reference Manual. Therefore we describe here only issues which are specific to infinite groups, and in particular to rcwa groups.</p>

<p>Wreath products are denoted by <code class="code">wr</code>, and free products are denoted by <code class="code">*</code>. The infinite cyclic group (ℤ,+) is denoted by <code class="code">Z</code>, the infinite dihedral group is denoted by <code class="code">D0</code> and free groups of rank <span class="SimpleMath">2,3,4,dots</span> are denoted by <code class="code">F2</code>, <code class="code">F3</code>, <code class="code">F4</code>, <span class="SimpleMath">dots</span>. While for finite groups the symbol <code class="code">.</code> is used to denote a non-split extension, for rcwa groups in general it stands for an extension which may be split or not. For wild groups in most cases it happens that there is a large section on which no structural information can be obtained. Such sections of the group with unknown structure are denoted by <code class="code"><unknown></code>. In general, the structure of a section denoted by <code class="code"><unknown></code> can be very complicated and very difficult to exhibit.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G);</span>
"(Z x Z x Z x Z x Z x Z x Z) . (C2 x S7)"
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassShift(2,4),ClassReflection(1,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G:short);</span>
"Z^2.((S3xS3):2)"
<span class="GAPprompt">gap></span> <span class="GAPinput">F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(3),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                                   CyclicGroup(2))));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := DirectProduct(PSL2Z,F2);</span>
<wild rcwa group over Z with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G);</span>
"(C3 * C2) x F2"
<span class="GAPprompt">gap></span> <span class="GAPinput">G := WreathProduct(G,CyclicGroup(IsRcwaGroupOverZ,infinity));</span>
<wild rcwa group over Z with 5 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G);</span>
"((C3 * C2) x F2) wr Z"
<span class="GAPprompt">gap></span> <span class="GAPinput">Collatz := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(Collatz,ClassShift(0,1));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G:short);</span>
"<unknown>.Z"

</pre></div>

<p>The extent to which the structure of an rcwa group can be exhibited automatically is severely limited. In general, one can find out much more about the structure of a given rcwa group in an interactive session using the functionality described in the rest of this section and elsewhere in this manual.</p>

<p>The order of an rcwa group can be computed by the operation <code class="code">Size</code>. An rcwa group is finite if and only if it is tame and its action on a suitably chosen respected partition (see <code class="func">RespectedPartition</code> (<a href="chap3.html#X7F523A6B87825AB8"><span class="RefLink">3.4-1</span></a>)) is faithful. Hence the problem of computing the order of an rcwa group reduces to the problem of deciding whether it is tame, the problem of deciding whether it acts faithfully on a respected partition and the problem of computing the order of the finite permutation group induced on the respected partition.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,3),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassReflection(0,5));</span>
<rcwa group over Z with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(G);</span>
46080

</pre></div>

<p>For a finite rcwa group, an isomorphism to a permutation group can be computed by <code class="code">IsomorphismPermGroup</code>:</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,3,1,3));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismPermGroup(G);</span>
[ ( 0(2), 1(2) ), ( 0(3), 1(3) ) ] -> [ (1,2)(3,4)(5,6), (1,2)(4,5) ]

</pre></div>

<p>In general the membership problem for rcwa groups is algorithmically unsolvable, see Corollary 4.5 in <a href="chapBib.html#biBKohl09">[Koh10]</a>. A consequence of this is that a membership test <q><code class="code">g in G</code></q> may run into an infinite loop if the rcwa permutation <code class="code">g</code> is not an element of the rcwa group <code class="code">G</code>. For tame rcwa groups however membership can always be decided. For wild rcwa groups, membership can very often be decided quite quick as well, but -- as said -- not always. Anyway, if <code class="code">g</code> is contained in <code class="code">G</code>, the membership test will eventually always return <code class="code">true</code>, provided that there are sufficient computing resources available (memory etc.).</p>

<p>On Info level 2 of <code class="code">InfoRCWA</code> the membership test provides information on reasons why the given rcwa permutation is an element of the given rcwa group or not.</p>

<p>The membership test <q><code class="code">g in G</code></q> recognizes an option <code class="code">OrbitLengthBound</code>. If this option is set, it returns <code class="code">false</code> once it has computed balls of size exceeding <code class="code">OrbitLengthBound</code> about 1 and <code class="code">g</code> in <code class="code">G</code>, and these balls are still disjoint. Note however that due to the algorithmic unsolvability of the membership problem, <strong class="pkg">RCWA</strong> has no means to check the correctness of such bound in a given case. So the correct use of this option has to remain within the full responsibility of the user.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassShift(0,3),ClassTransposition(0,3,2,6));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"> ClassShift(2,6)^7 * ClassTransposition(0,3,2,6)</span>
<span class="GAPprompt">></span> <span class="GAPinput">  * ClassShift(0,3)^-3 in G;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ClassShift(0,1) in G;</span>
false

</pre></div>

<p>The conjugacy problem for rcwa groups is difficult, and <strong class="pkg">RCWA</strong> provides only methods to solve it in some reasonably easy cases.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">IsConjugate(RCWA(Integers),</span>
<span class="GAPprompt">></span> <span class="GAPinput">               ClassTransposition(0,2,1,4),ClassShift(0,1));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsConjugate(CT(Integers),ClassTransposition(0,2,1,6),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            ClassTransposition(1,4,0,8));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := RepresentativeAction(CT(Integers),ClassTransposition(0,2,1,6),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                          ClassTransposition(1,4,0,8));</span>
<rcwa permutation of Z with modulus 48>
<span class="GAPprompt">gap></span> <span class="GAPinput">ClassTransposition(0,2,1,6)^g = ClassTransposition(1,4,0,8);</span>
true

</pre></div>

<p>There is a property <code class="code">IsTame</code> which indicates whether an rcwa group is tame or not:</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,4),ClassShift(1,3));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := Group(ClassTransposition(0,2,1,6),ClassShift(1,3));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(H);</span>
false

</pre></div>

<p>For tame rcwa groups, there are methods for <code class="code">IsSolvableGroup</code> and <code class="code">IsPerfectGroup</code> available, and usually derived subgroups and subgroup indices can be computed as well. Linear representations of tame groups over the rationals can be determined by the operation <code class="code">IsomorphismMatrixGroup</code>. Testing a wild group for solvability or perfectness is currently not always feasible, and wild groups have in general no faithful finite-dimensional linear representations. There is a method for <code class="code">Exponent</code> available, which works basically for any rcwa group.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,4),ClassShift(1,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPerfect(G);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSolvable(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D1 := DerivedSubgroup(G);; D2 := DerivedSubgroup(D1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAbelian(D2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(G,D1); Index(D1,D2);</span>
infinity
9
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(G); StructureDescription(D1);</span>
"(Z x Z x Z) . S3"
"(Z x Z) . C3"
<span class="GAPprompt">gap></span> <span class="GAPinput">Q := D1/D2;</span>
Group([ (), (1,2,4)(3,5,7)(6,8,9), (1,3,6)(2,5,8)(4,7,9) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(Q); </span>
"C3 x C3"
<span class="GAPprompt">gap></span> <span class="GAPinput">Exponent(G);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismMatrixGroup(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(Image(phi,ClassTransposition(0,2,1,4)));</span>
[ [     0,     0,   1/2,  -1/2,     0,     0 ], 
  [     0,     0,     0,     1,     0,     0 ], 
  [     2,     1,     0,     0,     0,     0 ], 
  [     0,     1,     0,     0,     0,     0 ], 
  [     0,     0,     0,     0,     1,     0 ], 
  [     0,     0,     0,     0,     0,     1 ] ]

</pre></div>

<p>When investigating a group, a basic task is to find relations among the generators:</p>

<p><a id="X83527DA37C5CB2C7" name="X83527DA37C5CB2C7"></a></p>

<h5>3.2-2 EpimorphismFromFpGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismFromFpGroup</code>( <var class="Arg">G</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">‣ EpimorphismFromFpGroup</code>( <var class="Arg">G</var>, <var class="Arg">r</var>, <var class="Arg">maxparts</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an epimorphism from a finitely presented group to the rcwa group <var class="Arg">G</var>.</p>

<p>The argument <var class="Arg">r</var> is the <q>search radius</q>, i.e. the radius of the ball around 1 which is scanned for relations. In general, the larger <var class="Arg">r</var> is chosen the smaller the kernel of the returned epimorphism is. If the group <var class="Arg">G</var> has finite presentations, the kernel will in principle get trivial provided that <var class="Arg">r</var> is chosen large enough. If the optional argument <var class="Arg">maxparts</var> is given, it limits the search space to elements with at most <var class="Arg">maxparts</var> affine parts.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">a := ClassTransposition(2,4,3,4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := ClassTransposition(4,6,8,12);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">c := ClassTransposition(3,4,4,6);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := SparseRep(Group(a,b,c));</span>
<(2(4),3(4)),(4(6),8(12)),(3(4),4(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := EpimorphismFromFpGroup(G,6);</span>
#I  there are 3 generators and 12 relators of total length 330
#I  there are 3 generators and 11 relators of total length 312
[ a, b, c ] -> [ ( 2(4), 3(4) ), ( 4(6), 8(12) ), ( 3(4), 4(6) ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RelatorsOfFpGroup(Source(phi));</span>
[ a^2, b^2, c^2, (b*c)^3, (a*b)^6, (a*b*c*b)^3, (a*c*b*c)^3, 
  (a*b*a*c)^12, ((a*b)^2*a*c)^12, (a*b*(a*c)^2)^12, (a*b*c*a*c*b)^12 ]

</pre></div>

<p>A related very common task is to factor group elements into generators:</p>

<p><a id="X8463E34286344F06" name="X8463E34286344F06"></a></p>

<h5>3.2-3 PreImagesRepresentative</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PreImagesRepresentative</code>( <var class="Arg">phi</var>, <var class="Arg">g</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a representative of the set of preimages of <var class="Arg">g</var> under the epimorphism <var class="Arg">phi</var> from a free group to an rcwa group.</p>

<p>The epimorphism <var class="Arg">phi</var> must map the generators of the free group to the generators of the rcwa group one-by-one.</p>

<p>This method can be used for factoring elements of rcwa groups into generators. The implementation is based on <code class="code">RepresentativeActionPreImage</code>, see <code class="func">RepresentativeAction</code> (<a href="chap3.html#X87A3462C82FD376E"><span class="RefLink">3.3-10</span></a>).</p>

<p>Quite frequently, computing several preimages is not harder than computing just one, i.e. often several preimages are found simultaneously. The operation <code class="code">PreImagesRepresentatives</code> takes care of this. It takes the same arguments as <code class="code">PreImagesRepresentative</code> and returns a list of preimages. If multiple preimages are found, their quotients give rise to nontrivial relations among the generators of the image of <var class="Arg">phi</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := ClassShift(0,1);; SetName(b,"b");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(a,b);; # G = <<Collatz permutation>, n -> n + 1></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := EpimorphismFromFreeGroup(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Comm(a^2*b^4,a*b^3); # a sample element to be factored</span>
<rcwa permutation of Z with modulus 8>
<span class="GAPprompt">gap></span> <span class="GAPinput">PreImagesRepresentative(phi,g); # -> a factorization of g</span>
b^-3*(b^-1*a^-1)^2*b^3*a*b^-1*a*b^3
<span class="GAPprompt">gap></span> <span class="GAPinput">g = b^-4*a^-1*b^-1*a^-1*b^3*a*b^-1*a*b^3; # check</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Comm(a*b,Comm(a,b^3));</span>
<rcwa permutation of Z with modulus 8>
<span class="GAPprompt">gap></span> <span class="GAPinput">pre := PreImagesRepresentatives(phi,g);</span>
[ (b^-1*a^-1)^2*b^2*(b*a)^2*b^-2, b^-1*(a^-1*b)^2*b^2*(a*b^-1)^2*b^-1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">rel := pre[1]/pre[2]; # -> a nontrivial relation</span>
(b^-1*a^-1)^2*b^3*a*b^2*a^-1*b^-2*(b^-1*a)^2*b
<span class="GAPprompt">gap></span> <span class="GAPinput">rel^phi;</span>
IdentityMapping( Integers )

</pre></div>

<p><a id="X8151BE577FFDCE87" name="X8151BE577FFDCE87"></a></p>

<h4>3.3 <span class="Heading">
  The natural action of an rcwa group on the underlying ring
</span></h4>

<p>Knowing a natural permutation representation of a group usually helps significantly in computing in it and in obtaining results on its structure. This holds particularly for the natural action of an rcwa group on its underlying ring. In this section we describe <strong class="pkg">RCWA</strong>'s functionality related to this action.</p>

<p>The support, i.e. the set of moved points, of an rcwa group can be determined by <code class="code">Support</code> or <code class="code">MovedPoints</code> (these are synonyms). Testing for transitivity on the underlying ring or on a union of residue classes thereof is often feasible:</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitive(G,Integers);</span>
true

</pre></div>

<p>Groups generated by class transpositions of the integers act on the set of nonnegative integers. There is a property <code class="code">IsTransitiveOnNonnegativeIntegersInSupport(<var class="Arg">G</var>)</code> which indicates whether such group acts transitively on the set of nonnegative integers in its support. Since such transitivity test is a computationally hard problem, methods may fail. If <code class="code">IsTransitiveOnNonnegativeIntegersInSupport</code> returns <code class="code">true</code>, an attribute <code class="code">TransitivityCertificate</code> is set; this is a record containing components <code class="code">phi</code>, <code class="code">words</code>, <code class="code">classes</code>, <code class="code">smallpointbound</code>, <code class="code">status</code> and <code class="code">complete</code> as follows:</p>


<dl>
<dt><strong class="Mark"><code class="code">phi</code></strong></dt>
<dd><p>is an epimorphism from a free group to <var class="Arg">G</var> which maps generators to generators.</p>

</dd>
<dt><strong class="Mark"><code class="code">words</code>, <code class="code">classes</code></strong></dt>
<dd><p>two lists. -- <code class="code">words[i]</code> is a preimage under <code class="code">phi</code> of an element of <var class="Arg">G</var> which maps all sufficiently large positive integers in the residue classes <code class="code">classes[i]</code> to smaller nonnegative integers.</p>

</dd>
<dt><strong class="Mark"><code class="code">smallpointbound</code></strong></dt>
<dd><p>in addition to finding a list of group elements <span class="SimpleMath">g_i</span> such that for any large enough integer <span class="SimpleMath">n</span> in the support of <var class="Arg">G</var> there is some <span class="SimpleMath">g_i</span> such that <span class="SimpleMath">n^g_i < n</span>, for verifying transitivity it was necessary to check that all integers less than or equal to <code class="code">smallpointbound</code> in the support of <var class="Arg">G</var> lie in the same orbit.</p>

</dd>
<dt><strong class="Mark"><code class="code">status</code></strong></dt>
<dd><p>the string <code class="code">"transitive"</code> in case all checks have been completed successfully.</p>

</dd>
<dt><strong class="Mark"><code class="code">complete</code></strong></dt>
<dd><p><code class="code">true</code> in case all checks have been completed successfully.</p>

</dd>
</dl>
<p>Parts of this information for possibly intransitive groups can be obtained by the operation <code class="code">TryToComputeTransitivityCertificate(<var class="Arg">G</var>,<var class="Arg">searchlimit</var>)</code>, where <var class="Arg">searchlimit</var> is the maximum radius about a point within which smaller points are searched and taken into consideration. This operation interprets an option <code class="code">abortdensity</code> -- if set, the operation returns the data computed so far once the density of the set of positive integers in the support of <var class="Arg">G</var> for which no group element is found which maps them to smaller integers reaches or drops below <code class="code">abortdensity</code>. A simplified certificate can be obtained via <code class="code">SimplifiedCertificate(<var class="Arg">cert</var>)</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,2,1,2],[0,3,2,3],[1,2,2,4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                   ClassTransposition));</span>
<(0(2),1(2)),(0(3),2(3)),(1(2),2(4))>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveOnNonnegativeIntegersInSupport(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">TransitivityCertificate(G);</span>
rec( 
  classes := [ [ 1(2) ], [ 2(6) ], [ 6(12), 10(12) ], [ 0(12) ], 
      [ 4(12) ] ], complete := true, 
  phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) 
     ], smallpointbound := 4, status := "transitive", 
  words := [ a, b, c, b*c, a*b ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">SimplifiedCertificate(last);</span>
rec( classes := [ [ 1(2) ], [ 2(4) ], [ 4(12) ], [ 0(12), 8(12) ] ], 
  complete := true, 
  phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) 
     ], smallpointbound := 4, status := "transitive", 
  words := [ a, c, a*b, b*c ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                   ClassTransposition));              # '3n+1 group'</span>
<(0(2),1(2)),(1(2),2(4)),(1(4),2(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">cert := TryToComputeTransitivityCertificate(G,10);</span>
rec(
  classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], 
      [ 0(24), 16(24) ] ], complete := false, 
  phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) 
     ], remaining := [ 12(48), 28(48), 52(96), 84(96) ], 
  smallpointbound := 42, status := "unclear", 
  words := [ a, b, (a*c)^2*b*a*b, c, a*c*b ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">Union(Flat(cert.classes));</span>
<union of 90 residue classes (mod 96) (6 classes)>
<span class="GAPprompt">gap></span> <span class="GAPinput">Difference(Integers,Union(Flat(cert.classes)));</span>
12(48) U 28(48) U 52(96) U 84(96)
<span class="GAPprompt">gap></span> <span class="GAPinput">cert := TryToComputeTransitivityCertificate(G,20); # try larger bound</span>
rec(
  classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], 
      [ 0(24), 16(24) ], [ 12(768), 268(768) ], [ 28(768), 540(768) ] ], 
  complete := false, 
  phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) 
     ], 
  remaining := [ 52(96), 84(96), 60(192), 108(192), 124(192), 172(192), 
      76(384), 204(384), 220(384), 348(384), 156(768), 396(768), 
      412(768), 652(768) ], smallpointbound := 1074, status := "unclear", 
  words := [ a, b, (a*c)^2*b*a*b, c, a*c*b, (a*c)^3*b*c*b*a*b, 
      (a*c)^4*b*a*b*a*b ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">Difference(Integers,Union(Flat(cert.classes)));</span>
<union of 44 residue classes (mod 768) (14 classes)>
<span class="GAPprompt">gap></span> <span class="GAPinput">Intersection([0..100],last);</span>
[ 52, 60, 76, 84 ]

</pre></div>

<p>Let <var class="Arg">G</var> be a subgroup of CT(ℤ). Then, a set which has nontrivial intersection with every orbit of <var class="Arg">G</var> on <span class="SimpleMath">ℕ_0</span> can be determined by the operation <code class="code">SupersetOfOrbitRepresentatives(<var class="Arg">G</var>,<var class="Arg">maxsaddle</var>,<var class="Arg">maxprog</var>)</code>. This operation returns a record with the following components:</p>


<dl>
<dt><strong class="Mark"><code class="code">R</code></strong></dt>
<dd><p>A set which -- possibly among other numbers -- contains the smallest representatives of all the orbits of <var class="Arg">G</var> on the nonnegative integers. The parameters <var class="Arg">maxsaddle</var> and <var class="Arg">maxprog</var> can be used to control the size of this set. In general, larger values may make the set smaller.</p>

</dd>
<dt><strong class="Mark"><code class="code">D</code></strong></dt>
<dd><p>A list of residue class unions whose union is a (not necessarily proper) superset the complement of <code class="code">R</code> in ℤ. The intersection of <code class="code">R</code> and the union of the sets in <code class="code">D</code> is always finite.</p>

</dd>
<dt><strong class="Mark"><code class="code">g</code></strong></dt>
<dd><p>A list of elements of <var class="Arg">G</var> such that <code class="code">n^g[i] < n</code> for all sufficiently large <code class="code">n</code> in <code class="code">D[i]</code>, for <code class="code">i = 1, ... , Length(g) = Length(D)</code>.</p>

</dd>
<dt><strong class="Mark"><code class="code">phi</code></strong></dt>
<dd><p>An epimorphism from a free group <code class="code">F</code> of rank the number of generators of <var class="Arg">G</var> to <var class="Arg">G</var> which maps generators to generators.</p>

</dd>
<dt><strong class="Mark"><code class="code">w</code></strong></dt>
<dd><p>A list of words <code class="code">w[i]</code> in <code class="code">F</code> such that <code class="code">w[i]^phi = g[i]</code>, for <code class="code">i = 1, ... , Length(w) = Length(g)</code>.</p>

</dd>
</dl>

<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(1,3,2,3),ClassTransposition(3,4,4,6),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassTransposition(2,4,1,6));</span>
<(1(3),2(3)),(3(4),4(6)),(2(4),1(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := SupersetOfOrbitRepresentatives(G,4,6);</span>
rec( D := [ 2(3), 4(6), 1(6) ], R := 0(3) U [ 1 ], 
  g := 
    [ ( 1(3), 2(3) ), <rcwa permutation of Z with modulus 12 and 
        5 affine parts>, <rcwa permutation of Z with modulus 12 and 
        5 affine parts> ], 
  pi := [ a, b, c ] -> [ ( 1(3), 2(3) ), ( 3(4), 4(6) ), ( 2(4), 1(6) ) ], 
  w := [ a, b, c ] )

</pre></div>

<p>Further, there are methods to compute orbits under the action of an rcwa group:</p>

<p><a id="X7C046BE97EE53692" name="X7C046BE97EE53692"></a></p>

<h5>3.3-1 <span class="Heading"> Orbit (for an rcwa group and either a point or a set) </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Orbit</code>( <var class="Arg">G</var>, <var class="Arg">point</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">‣ Orbit</code>( <var class="Arg">G</var>, <var class="Arg">set</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: the orbit of the point <var class="Arg">point</var> respectively the set <var class="Arg">set</var> under the natural action of the rcwa group <var class="Arg">G</var> on its underlying ring.</p>

<p>The second argument can either be an element or a subset of the underlying ring of the rcwa group <var class="Arg">G</var>. Since orbits under the action of rcwa groups can be finite or infinite, and since infinite orbits are not necessarily residue class unions, the orbit may either be returned in the form of a list, in the form of a residue class union or in the form of an orbit object. It is possible to loop over orbits returned as orbit objects, they can be compared and there is a membership test for them. However note that equality and membership for such orbits cannot always be decided.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassShift(0,2),ClassTransposition(0,3,1,3));</span>
<rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Orbit(G,0);</span>
Z \ 5(6)
<span class="GAPprompt">gap></span> <span class="GAPinput">Orbit(G,5);</span>
[ 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Orbit(G,ResidueClass(0,2));</span>
[ 0(2), 1(6) U 2(6) U 3(6), 1(3) U 3(6), 0(3) U 1(6), 0(3) U 4(6), 
  1(3) U 0(6), 0(3) U 2(6), 0(6) U 1(6) U 2(6), 2(6) U 3(6) U 4(6), 
  1(3) U 2(6) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(Orbit(G,ResidueClass(0,4)));</span>
80
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,2,1,4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassReflection(0,3));</span>
<rcwa group over Z with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">orb := Orbit(G,2);</span>
<orbit of 2 under <wild rcwa group over Z with 3 generators>>
<span class="GAPprompt">gap></span> <span class="GAPinput">1015808 in orb;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">First(orb,n->ForAll([n,n+2,n+6,n+8,n+30,n+32,n+36,n+38],IsPrime));</span>
-19

</pre></div>

<p><a id="X7B7A3AF97D195E33" name="X7B7A3AF97D195E33"></a></p>

<h5>3.3-2 GrowthFunctionOfOrbit</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrowthFunctionOfOrbit</code>( <var class="Arg">G</var>, <var class="Arg">n</var>, <var class="Arg">r_max</var>, <var class="Arg">size_max</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrowthFunctionOfOrbit</code>( <var class="Arg">orb</var>, <var class="Arg">r_max</var>, <var class="Arg">size_max</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a list whose (<span class="SimpleMath">r+1</span>)-th entry is the size of the sphere of radius <span class="SimpleMath">r</span> about <var class="Arg">n</var> under the action of the group <var class="Arg">G</var>, where the argument <var class="Arg">r_max</var> is the largest possible radius to be considered, and the computation stops once the sphere size exceeds <var class="Arg">size_max</var>.</p>

<p>An option <code class="code">"small"</code> is interpreted -- see example below. In place of the group <var class="Arg">G</var> and the point <var class="Arg">n</var>, one can pass as first argument also an rcwa group orbit object <var class="Arg">orb</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,4,1,4],[0,3,5,6],[0,4,5,6]],ClassTransposition));</span>
<(0(4),1(4)),(0(3),5(6)),(0(4),5(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">GrowthFunctionOfOrbit(G,18,100,20);</span>
[ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 5, 6, 8, 6, 5, 
  5, 4, 3, 3, 4, 4, 4, 3, 3, 5, 4, 5, 6, 5, 2, 3, 3, 2, 3, 3, 4, 5, 4, 
  4, 4, 6, 5, 5, 3, 4, 2, 3, 4, 4, 2, 3, 4, 4, 2, 3, 3, 4, 3, 5, 3, 5, 
  4, 5, 6, 5, 3, 4, 5, 6, 5, 4, 3, 5, 4, 5, 5, 4, 4, 5, 5, 3, 4, 5, 3, 
  3, 4, 5, 4, 2, 3, 4, 4, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">last = GrowthFunctionOfOrbit(Orbit(G,18),100,20);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">GrowthFunctionOfOrbit(G,18,20,20:small:=[0..100]);</span>
rec( smallpoints := [ 18, 24, 25, 27, 30, 32, 33, 36, 37, 39, 40, 41, 
      42, 44, 45, 48, 49, 51, 52, 53, 56, 57, 59, 60, 61, 64, 65, 66, 
      68, 69, 71, 75, 76, 77, 80, 81, 83, 88, 89, 92, 93, 95, 100 ], 
  spheresizes := [ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 
      5, 6, 8 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],ClassTransposition));</span>
<(0(2),1(2)),(1(2),2(4)),(1(4),2(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">GrowthFunctionOfOrbit(G,0,100,10000);</span>
[ 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 7, 6, 7, 9, 12, 14, 19, 21, 28, 
  29, 37, 42, 55, 57, 72, 78, 99, 113, 148, 164, 215, 226, 288, 344, 
  462, 478, 612, 686, 894, 985, 1284, 1416, 1847, 2018, 2620, 2902, 
  3786, 4167, 5432, 5958, 7749, 8568, 11178 ]

</pre></div>

<p>Given an rcwa group <var class="Arg">G</var> over ℤ and an integer <var class="Arg">n</var>, <code class="code">DistanceToNextSmallerPointInOrbit(</code><var class="Arg">G</var><code class="code">,</code><var class="Arg">n</var><code class="code">)</code> computes the smallest number <span class="SimpleMath">d</span> such that there is a product <span class="SimpleMath">g</span> of <span class="SimpleMath">d</span> generators or inverses of generators of <var class="Arg">G</var> which maps <var class="Arg">n</var> to an integer with absolute value less than |<var class="Arg">n</var>|, provided that the orbit of <var class="Arg">n</var> contains such integer. <strong class="pkg">RCWA</strong> provides a function to draw pictures of orbits of rcwa groups on <span class="SimpleMath">ℤ^2</span>. The pictures are written to files in bitmap- (bmp-) format. The author has successfully tested this feature both under Linux and under Windows, and the generated pictures can be processed further with many common graphics programs:</p>

<p><a id="X7D9DFAC97F9F0891" name="X7D9DFAC97F9F0891"></a></p>

<h5>3.3-3 DrawOrbitPicture</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DrawOrbitPicture</code>( <var class="Arg">G</var>, <var class="Arg">p0</var>, <var class="Arg">bound</var>, <var class="Arg">h</var>, <var class="Arg">w</var>, <var class="Arg">colored</var>, <var class="Arg">palette</var>, <var class="Arg">filename</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: nothing.</p>

<p>Draws a picture of the orbit(s) of the point(s) <var class="Arg">p0</var> under the action of the group <var class="Arg">G</var> on <span class="SimpleMath">ℤ^2</span>. The argument <var class="Arg">p0</var> is either one point or a list of points. The argument <var class="Arg">bound</var> denotes the bound to which the ball about <var class="Arg">p0</var> is to be computed, in terms of absolute values of coordinates. The size of the generated picture is <var class="Arg">h</var> x <var class="Arg">w</var> pixels. The argument <var class="Arg">colored</var> is a boolean which indicates whether a 24-bit true color picture or a monochrome picture should be generated. In the former case, <var class="Arg">palette</var> must be a list of triples of integers in the range <span class="SimpleMath">0, dots, 255</span>, denoting the RGB values of the colors to be used. In the latter case, <var class="Arg">palette</var> is not used, and any value can be passed. The picture is written in bitmap- (bmp-) format to a file named <var class="Arg">filename</var>. This is done using the utility function <code class="code">SaveAsBitmapPicture</code> from <strong class="pkg">ResClasses</strong>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                                   CyclicGroup(3))));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DrawOrbitPicture(PSL2Z,[0,1],2000,512,512,false,fail,"example1.bmp");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DrawOrbitPicture(PSL2Z,Combinations([1..4],2),2000,512,512,true,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [[255,0,0],[0,255,0],[0,0,255]],"example2.bmp");</span>

</pre></div>

<p>The pictures drawn in the examples are shown on <strong class="pkg">RCWA</strong>'s webpage.</p>

<p>Finite orbits give rise to finite quotients of a group, and finite cycles can help to check for conjugacy. Therefore it is important to be able to determine them:</p>

<p><a id="X78F145197F63A25D" name="X78F145197F63A25D"></a></p>

<h5>3.3-4 <span class="Heading">
    ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations)
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortOrbits</code>( <var class="Arg">G</var>, <var class="Arg">S</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortOrbits</code>( <var class="Arg">G</var>, <var class="Arg">S</var>, <var class="Arg">maxlng</var>, <var class="Arg">maxn</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortCycles</code>( <var class="Arg">g</var>, <var class="Arg">S</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortCycles</code>( <var class="Arg">g</var>, <var class="Arg">S</var>, <var class="Arg">maxlng</var>, <var class="Arg">maxn</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortCycles</code>( <var class="Arg">g</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: in the first form a list of all orbits of the rcwa group <var class="Arg">G</var> of length at most <var class="Arg">maxlng</var> which intersect non-trivially with the set <var class="Arg">S</var>. In the second form a list of all orbits of the rcwa group <var class="Arg">G</var> of length at most <var class="Arg">maxlng</var> which intersect non-trivially with the set <var class="Arg">S</var> and which, in terms of euclidean norm, do not exceed <var class="Arg">maxn</var>. In the third form a list of all cycles of the rcwa permutation <var class="Arg">g</var> of length at most <var class="Arg">maxlng</var> which intersect non-trivially with the set <var class="Arg">S</var>. In the fourth form a list of all cycles of the rcwa permutation <var class="Arg">g</var> of length at most <var class="Arg">maxlng</var> which intersect non-trivially with the set <var class="Arg">S</var> and which, in terms of euclidean norm, do not exceed <var class="Arg">maxn</var>. In the fifth form a list of all cycles of the rcwa permutation <var class="Arg">g</var> of length at most <var class="Arg">maxlng</var> which do not correspond to cycles consisting of residue classes.</p>

<p>The operation <code class="func">ShortOrbits</code> recognizes an option <var class="Arg">finite</var>. If this option is set, it is assumed that all orbits are finite, in order to speed up the computation. If furthermore <var class="Arg">maxlng</var> is negative, a list of <em>all</em> orbits which intersect non-trivially with <var class="Arg">S</var> is returned.</p>

<p>There is an operation <code class="code">CyclesOnFiniteOrbit(</code><var class="Arg">G</var><code class="code">,</code><var class="Arg">g</var><code class="code">,</code><var class="Arg">n</var><code class="code">)</code> which returns a list of all cycles of the rcwa permutation <var class="Arg">g</var> on the orbit of the point <var class="Arg">n</var> under the action of the rcwa group <var class="Arg">G</var>. Here <var class="Arg">g</var> is assumed to be an element of <var class="Arg">G</var>, and the orbit of <var class="Arg">n</var> is assumed to be finite.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(1,4,2,4)*ClassTransposition(1,4,3,4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassTransposition(3,9,6,18)*ClassTransposition(1,6,3,9));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(ShortOrbits(G,[-15..15],100),</span>
<span class="GAPprompt">></span> <span class="GAPinput">        orb->StructureDescription(Action(G,orb)));</span>
[ "A15", "A4", "1", "1", "C3", "1", "(C2 x C2 x C2) : (C7 : C3)", "1", 
  "1", "C3", "A19" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortCycles(mKnot(7),[1..100],20);</span>
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7, 8 ], [ 9, 10 ], 
  [ 11, 12 ], [ 13, 14, 16, 18, 20, 22, 19, 17, 15 ], [ 21, 24 ], 
  [ 23, 26 ], [ 25, 28, 32, 36, 31, 27, 30, 34, 38, 33, 29 ], 
  [ 35, 40 ], [ 37, 42, 48, 54, 47, 41, 46, 52, 45, 39, 44, 50, 43 ], 
  [ 77, 88, 100, 114, 130, 148, 127, 109, 124, 107, 122, 105, 120, 103, 
      89 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,2,1,2],[0,5,4,5],[1,4,0,6]],ClassTransposition));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CyclesOnFiniteOrbit(G,G.1*G.2,0);</span>
[ [ 0, 1, 4, 9, 8, 5 ], [ 6, 7 ], [ 10, 11, 14, 19, 18, 15 ], [ 12, 13 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List(CyclesOnFiniteOrbit(G,G.1*G.2*G.3*G.1*G.3*G.2,32),Length);</span>
[ 3148, 3148 ]

</pre></div>

<p><a id="X80D18D0778A96C16" name="X80D18D0778A96C16"></a></p>

<h5>3.3-5 <span class="Heading">
    ShortResidueClassOrbits & ShortResidueClassCycles
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortResidueClassOrbits</code>( <var class="Arg">G</var>, <var class="Arg">modulusbound</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortResidueClassCycles</code>( <var class="Arg">g</var>, <var class="Arg">modulusbound</var>, <var class="Arg">maxlng</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ResidueClassCyclesThroughResidueClass</code>( <var class="Arg">g</var>, <var class="Arg">cl</var>, <var class="Arg">modulusbound</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: in the first form a list of all orbits of residue classes under the action of the rcwa group <var class="Arg">G</var> which contain a residue class <span class="SimpleMath">r(m)</span> such that <span class="SimpleMath">m</span> divides <var class="Arg">modulusbound</var> and which are not longer than <var class="Arg">maxlng</var>. In the second form a list of all cycles of residue classes of the rcwa permutation <var class="Arg">g</var> which contain a residue class <span class="SimpleMath">r(m)</span> such that <span class="SimpleMath">m</span> divides <var class="Arg">modulusbound</var> and which are not longer than <var class="Arg">maxlng</var>. In the third form a list of all cycles of residue classes of the rcwa permutation <var class="Arg">g</var> which contain a residue class <span class="SimpleMath">r(m)</span> which is a subset of the residue class <var class="Arg">cl</var> on which <var class="Arg">g</var> is affine and whose modulus <span class="SimpleMath">m</span> divides <var class="Arg">modulusbound</var>.</p>

<p>We are only talking about a <em>cycle</em> of residue classes of an rcwa permutation <span class="SimpleMath">g</span> if the restrictions of <span class="SimpleMath">g</span> to all contained residue classes are affine. Similarly we are only talking about an <em>orbit</em> of residue classes under the action of an rcwa group <span class="SimpleMath">G</span> if the restrictions of all elements of <span class="SimpleMath">G</span> to all residue classes in the orbit are affine.</p>

<p>The returned lists may contain additional cycles, resp., orbits, which do not contain a residue class <span class="SimpleMath">r(m)</span> such that <span class="SimpleMath">m</span> divides <var class="Arg">modulusbound</var>, but which happen to be found without additional efforts.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6);</span>
<rcwa permutation of Z with modulus 12>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortResidueClassCycles(g,Mod(g)^2,20);</span>
[ [ 2(12), 3(12) ], [ 10(12), 11(12) ], [ 4(24), 5(24), 7(36), 6(36) ], 
  [ 20(24), 21(24), 31(36), 30(36) ], 
  [ 8(48), 9(48), 13(72), 19(108), 18(108), 12(72) ], 
  [ 40(48), 41(48), 61(72), 91(108), 90(108), 60(72) ], 
  [ 16(96), 17(96), 25(144), 37(216), 55(324), 54(324), 36(216), 24(144) 
     ], 
  [ 80(96), 81(96), 121(144), 181(216), 271(324), 270(324), 180(216), 
      120(144) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ResidueClassCyclesThroughResidueClass(g,ResidueClass(1,4),2^2*12);</span>
[ [ 5(24), 7(36), 6(36), 4(24) ], [ 21(24), 31(36), 30(36), 20(24) ], 
  [ 9(48), 13(72), 19(108), 18(108), 12(72), 8(48) ], 
  [ 41(48), 61(72), 91(108), 90(108), 60(72), 40(48) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected(List(ResidueClassCyclesThroughResidueClass(g,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                  ResidueClass(1,4),2^6*12),Length));</span>
[ [ 4, 2 ], [ 6, 4 ], [ 8, 6 ], [ 10, 8 ], [ 12, 4 ], [ 14, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List(ResidueClassCyclesThroughResidueClass(g,</span>
<span class="GAPprompt">></span> <span class="GAPinput">        ResidueClass(1,4),2^4*12),cyc->cyc[1]);</span>
[ 5(24), 21(24), 9(48), 41(48), 13(72), 61(72), 17(96), 81(96), 25(144), 
  121(144), 33(192), 161(192) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(Difference(ResidueClass(1,4),Union(last)));</span>
1(36) U 49(144) U 97(144) U 65(192) U 129(192)
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[0,6,5,6],[1,4,4,6],[2,4,3,6]],ClassTransposition));</span>
<(0(6),5(6)),(1(4),4(6)),(2(4),3(6))>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortResidueClassOrbits(G,48,10);</span>
[ [ 7(12) ], [ 8(12) ], [ 1(24), 4(36) ], [ 2(24), 3(36) ], 
  [ 12(24), 17(24), 28(36) ], [ 18(24), 23(24), 27(36) ], 
  [ 37(48), 58(72), 87(108) ], [ 38(48), 57(72), 88(108) ], 
  [ 0(48), 5(48), 10(72), 15(108) ], [ 6(48), 11(48), 9(72), 16(108) ] ]

</pre></div>

<p><a id="X80C080287A355EFF" name="X80C080287A355EFF"></a></p>

<h5>3.3-6 ComputeCycleLength</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComputeCycleLength</code>( <var class="Arg">g</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record containing the length, the largest point and the position of the largest point of the cycle of the rcwa permutation <var class="Arg">g</var> which contains the point <var class="Arg">n</var>, provided that this cycle is finite.</p>

<p>If the cycle is infinite, the function will run into an infinite loop unless the option <code class="code">"abortat"</code> is set to the maximum number of iterates to be tried before aborting. Iterates are not stored, to save memory. The function interprets an option <code class="code">"notify"</code>, which defaults to 10000; every <q>notify</q> iterations, the number of binary digits of the latest iterate is printed. This output can be suppressed by the option <code class="code">quiet</code>. The function also interprets an option <code class="code">"small"</code>, which may be set to a range within which small points are recorded and returned in a component <code class="code">smallpoints</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     ClassTransposition));</span>
<rcwa permutation of Z with modulus 180>
<span class="GAPprompt">gap></span> <span class="GAPinput">ComputeCycleLength(g,20:small:=[0..1000]);</span>
n = 20: after 10000 steps, the iterate has 1919 binary digits.
n = 20: after 20000 steps, the iterate has 2908 binary digits.
n = 20: after 30000 steps, the iterate has 1531 binary digits.
n = 20: after 40000 steps, the iterate has 708 binary digits.
rec( aborted := false, g := <rcwa permutation of Z with modulus 180>, 
  length := 45961, 
  maximum := 180479928411509527091314790144929480041473309862957394384783\
0525935437431021442346166422201250935268553945158085769924448388724679753\
5271669245363980744610119632280105994423399614803956244808653465492205657\
8650363041608376587943180444494842094693691286183613056599672737336761093\
3101035841077322874883200384115281051837032147150147712534199292886436789\
7520389780289517825203780151058517520194926468391308525704499649905091899\
9667529835495635671154681958992898010506577172313321500572646883756736685\
0158653917532084531267455434808219032998691038943070902228427549279555530\
6429870190316109419051531138721361826083376315737131067799731181096142797\
4868525347003646887454985757711743327946232372385342293662007684758208408\
8635715976464060647431260835037213863991037813998261883899050447111540742\
5857187943077255493709629738212709349458790098815926920248565399938335540\
8092502449690267365120996852, maxpos := 19825, n := 20, 
  smallpoints := [ 20, 23, 66, 99, 294, 295, 298, 441, 447, 882, 890, 
      893 ] )

</pre></div>

<p><a id="X7F76B04E86C77B94" name="X7F76B04E86C77B94"></a></p>

<h5>3.3-7 CycleRepresentativesAndLengths</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CycleRepresentativesAndLengths</code>( <var class="Arg">g</var>, <var class="Arg">S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list of pairs (cycle representative, length of cycle) for all cycles of the rcwa permutation <var class="Arg">g</var> which have a nontrivial intersection with the set <var class="Arg">S</var>, where fixed points are omitted.</p>

<p>The rcwa permutation <var class="Arg">g</var> is assumed to have only finite cycles. If <var class="Arg">g</var> has an infinite cycle which intersects non-trivially with <var class="Arg">S</var>, this may cause an infinite loop unless a cycle length limit is set via the option <code class="code">abortat</code>. The output can be suppressed by the option <code class="code">quiet</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CycleRepresentativesAndLengths(g,[0..50]);</span>
[ [ 2, 2 ], [ 4, 4 ], [ 8, 6 ], [ 10, 2 ], [ 14, 2 ], [ 16, 8 ], 
  [ 20, 4 ], [ 22, 2 ], [ 26, 2 ], [ 28, 4 ], [ 32, 10 ], [ 34, 2 ], 
  [ 38, 2 ], [ 40, 6 ], [ 44, 4 ], [ 46, 2 ], [ 50, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     ClassTransposition));</span>
<rcwa permutation of Z with modulus 180>
<span class="GAPprompt">gap></span> <span class="GAPinput">CycleRepresentativesAndLengths(g,[0..100]:abortat:=100000);</span>
n = 20: after 10000 steps, the iterate has 1919 binary digits.
n = 20: after 20000 steps, the iterate has 2908 binary digits.
n = 20: after 30000 steps, the iterate has 1531 binary digits.
n = 20: after 40000 steps, the iterate has 708 binary digits.
n = 79: after 10000 steps, the iterate has 1679 binary digits.
n = 100: after 10000 steps, the iterate has 712 binary digits.
n = 100: after 20000 steps, the iterate has 2507 binary digits.
n = 100: after 30000 steps, the iterate has 3311 binary digits.
n = 100: after 40000 steps, the iterate has 3168 binary digits.
n = 100: after 50000 steps, the iterate has 3947 binary digits.
n = 100: after 60000 steps, the iterate has 4793 binary digits.
n = 100: after 70000 steps, the iterate has 5325 binary digits.
n = 100: after 80000 steps, the iterate has 6408 binary digits.
n = 100: after 90000 steps, the iterate has 7265 binary digits.
n = 100: after 100000 steps, the iterate has 7918 binary digits.
[ [ 0, 7 ], [ 5, 3 ], [ 7, 7159 ], [ 11, 9 ], [ 19, 342 ],
  [ 20, 45961 ], [ 25, 3 ], [ 26, 21 ], [ 29, 2 ], [ 31, 3941 ],
  [ 34, 19 ], [ 37, 7 ], [ 40, 5 ], [ 41, 7 ], [ 46, 3 ], [ 49, 2 ],
  [ 59, 564 ], [ 61, 577 ], [ 65, 3 ], [ 67, 23 ], [ 71, 41 ],
  [ 79, 16984 ], [ 80, 5 ], [ 85, 3 ], [ 86, 3 ], [ 89, 2 ], [ 91, 9 ],
  [ 94, 1355 ], [ 97, 7 ], [ 100, fail ] ]

</pre></div>

<p>Often one also wants to know which residue classes an rcwa mapping or an rcwa group fixes setwise:</p>

<p><a id="X8777A62286597D53" name="X8777A62286597D53"></a></p>

<h5>3.3-8 FixedResidueClasses</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FixedResidueClasses</code>( <var class="Arg">g</var>, <var class="Arg">maxmod</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FixedResidueClasses</code>( <var class="Arg">G</var>, <var class="Arg">maxmod</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the set of residue classes with modulus greater than 1 and less than or equal to <var class="Arg">maxmod</var> which the rcwa mapping <var class="Arg">g</var>, respectively the rcwa group <var class="Arg">G</var>, fixes setwise.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">FixedResidueClasses(ClassTransposition(0,2,1,4),8);</span>
[ 2(3), 3(4), 4(5), 6(7), 3(8), 7(8) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FixedResidueClasses(Group(ClassTransposition(0,2,1,4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             ClassTransposition(0,3,1,3)),12);</span>
[ 2(3), 8(9), 11(12) ]

</pre></div>

<p>Frequently one needs to compute balls of certain radius around points or group elements, be it to estimate the growth of a group, be it to see how an orbit looks like, be it to search for a group element with certain properties or be it for other purposes:</p>

<p><a id="X8735855587CC029F" name="X8735855587CC029F"></a></p>

<h5>3.3-9 <span class="Heading">
    Ball (for group, element and radius or group, point, radius and action)
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ball</code>( <var class="Arg">G</var>, <var class="Arg">g</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">‣ Ball</code>( <var class="Arg">G</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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Ball</code>( <var class="Arg">G</var>, <var class="Arg">p</var>, <var class="Arg">r</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">g</var> in the group <var class="Arg">G</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 group <var class="Arg">G</var>, respectively the ball of radius <var class="Arg">r</var> around the point <var class="Arg">p</var> under the action <code class="code">OnPoints</code> of the group <var class="Arg">G</var>,</p>

<p>All balls are understood with respect to <code class="code">GeneratorsOfGroup(<var class="Arg">G</var>)</code>. As membership tests can be expensive, the former method does not check whether <var class="Arg">g</var> is indeed an element of <var class="Arg">G</var>. The methods require that element- / point comparisons are cheap. They are not only applicable to rcwa groups. If the option <var class="Arg">Spheres</var> is set, the ball is split up and returned as a list of spheres. There is a related operation <code class="code">RestrictedBall(<var class="Arg">G</var>,<var class="Arg">g</var>,<var class="Arg">r</var>,<var class="Arg">modulusbound</var>)</code> specifically for rcwa groups which computes only those elements of the ball whose moduli do not exceed <var class="Arg">modulusbound</var>, and which can be reached from <var class="Arg">g</var> without computing intermediate elements whose moduli do exceed <var class="Arg">modulusbound</var>. The latter operation interprets an option <code class="code">"boundaffineparts"</code>. -- If this option is set and the group <var class="Arg">G</var> and the element <var class="Arg">g</var> are in sparse representation, then <var class="Arg">modulusbound</var> is actually taken to be a bound on the number of affine parts rather than a bound on the modulus.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                                   CyclicGroup(3))));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([1..10],k->Length(Ball(PSL2Z,[0,1],k,OnTuples)));</span>
[ 4, 8, 14, 22, 34, 50, 74, 106, 154, 218 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Ball(Group((1,2),(2,3),(3,4)),(),2:Spheres);</span>
[ [ () ], [ (3,4), (2,3), (1,2) ],
  [ (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,3,2) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(List([[1,2,4,6],[1,3,2,6],[2,3,4,6]],ClassTransposition));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">B := RestrictedBall(G,One(G),20,36:Spheres);; # try replacing 36 by 72</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(B,Length);</span>
[ 1, 3, 6, 12, 4, 6, 6, 4, 4, 4, 6, 6, 3, 3, 2, 0, 0, 0, 0, 0, 0 ]

</pre></div>

<p>It is possible to determine group elements which map a given tuple of elements of the underlying ring to a given other tuple, if such elements exist:</p>

<p><a id="X87A3462C82FD376E" name="X87A3462C82FD376E"></a></p>

<h5>3.3-10 RepresentativeAction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepresentativeAction</code>( <var class="Arg">G</var>, <var class="Arg">source</var>, <var class="Arg">destination</var>, <var class="Arg">action</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an element of <var class="Arg">G</var> which maps <var class="Arg">source</var> to <var class="Arg">destination</var> under the action given by <var class="Arg">action</var>.</p>

<p>If an element satisfying this condition does not exist, this method either returns <code class="code">fail</code> or runs into an infinite loop. The problem whether <var class="Arg">source</var> and <var class="Arg">destination</var> lie in the same orbit under the action <var class="Arg">action</var> of <var class="Arg">G</var> is hard, and in its general form most likely computationally undecidable.</p>

<p>In cases where rather a word in the generators of <var class="Arg">G</var> than the actual group element is needed, one should use the operation <code class="code">RepresentativeActionPreImage</code> instead. This operation takes five arguments. The first four are the same as those of <code class="code">RepresentativeAction</code>, and the fifth is a free group whose generators are to be used as letters of the returned word. Note that <code class="code">RepresentativeAction</code> calls <code class="code">RepresentativeActionPreImage</code> and evaluates the returned word. The evaluation of the word can very well take most of the time if <var class="Arg">G</var> is wild and coefficient explosion occurs.</p>

<p>The algorithm is based on computing balls of increasing radius around <var class="Arg">source</var> and <var class="Arg">destination</var> until they intersect non-trivially.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := ClassShift(1,4:Name:="b");; G := Group(a,b);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := RepresentativeAction(G,[7,4,9],[4,5,13],OnTuples);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(elm);</span>

Rcwa permutation of Z with modulus 12

        /
        | n-3 if n in 1(6) U 10(12)
        | n+4 if n in 5(12) U 9(12)
 n |-> <  n+1 if n in 4(12)
        | n   if n in 0(6) U 2(6) U 3(12) U 11(12)
        |
        \

<span class="GAPprompt">gap></span> <span class="GAPinput">List([7,4,9],n->n^elm);</span>
[ 4, 5, 13 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := RepresentativeAction(G,[6,-3,8],[-9,4,11],OnPoints);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(elm);</span>

Rcwa permutation of Z with modulus 12

        /
        | 2n/3      if n in 0(6) U 3(12)
        | (4n+1)/3  if n in 2(6) U 11(12)
        | (4n-1)/3  if n in 4(6) U 7(12)
 n |-> <  (2n-8)/3  if n in 1(12)
        | (4n-17)/3 if n in 5(12)
        | (4n-15)/3 if n in 9(12)
        |
        \

<span class="GAPprompt">gap></span> <span class="GAPinput">[6,-3,8]^elm; List([6,-3,8],n->n^elm); # `OnPoints' allows reordering</span>
[ -9, 4, 11 ]
[ 4, -9, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeGroup("a","b");; phi := EpimorphismByGenerators(F,G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := RepresentativeActionPreImage(G,[10,-4,9,5],[4,5,13,-8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                     OnTuples,F);</span>
a*b^-1*a^-1*(b^-1*a)^2*b*a*b^-2*a*b*a^-1*b
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := w^phi;</span>
<rcwa permutation of Z with modulus 324>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([10,-4,9,5],n->n^elm);</span>
[ 4, 5, 13, -8 ]

</pre></div>

<p>Sometimes an rcwa group fixes a certain partition of the underlying ring into unions of residue classes. If this happens, then any orbit is clearly a subset of exactly one of these parts. Further, such a partition often gives rise to proper quotients of the group:</p>

<p><a id="X8587246A7F890849" name="X8587246A7F890849"></a></p>

<h5>3.3-11 ProjectionsToInvariantUnionsOfResidueClasses</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ProjectionsToInvariantUnionsOfResidueClasses</code>( <var class="Arg">G</var>, <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the projections of the rcwa group <var class="Arg">G</var> to the unions of residue classes (mod <var class="Arg">m</var>) which it fixes setwise.</p>

<p>The corresponding partition of a set of representatives for the residue classes (mod <var class="Arg">m</var>) can be obtained by the operation <code class="code">OrbitsModulo(<var class="Arg">G</var>,<var class="Arg">m</var>)</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassShift(3,4));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ProjectionsToInvariantUnionsOfResidueClasses(G,4);</span>
[ [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> 
    [ ( 0(4), 1(4) ), IdentityMapping( Integers ) ], 
  [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> 
    [ ( 2(4), 3(4) ), <rcwa permutation of Z with modulus 4> ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List(last,phi->Support(Image(phi)));</span>
[ 0(4) U 1(4), 2(4) U 3(4) ]

</pre></div>

<p>Given two partitions of the underlying ring into the same number of unions of residue classes, there is always an rcwa permutation which maps the one to the other:</p>

<p><a id="X866843D08213067E" name="X866843D08213067E"></a></p>

<h5>3.3-12 RepresentativeAction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepresentativeAction</code>( <var class="Arg">RCWA(R)</var>, <var class="Arg">P1</var>, <var class="Arg">P2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: an element of RCWA(<span class="SimpleMath">R</span>) which maps the partition <var class="Arg">P1</var> to <var class="Arg">P2</var>.</p>

<p>The arguments <var class="Arg">P1</var> and <var class="Arg">P2</var> must be partitions of the underlying ring <span class="SimpleMath">R</span> into the same number of unions of residue classes. The method for <span class="SimpleMath">R = ℤ</span> recognizes the option <code class="code">IsTame</code>, which can be used to demand a tame result. If this option is set and there is no tame rcwa permutation which maps <var class="Arg">P1</var> to <var class="Arg">P2</var>, the method runs into an infinite loop. This happens if the condition in Theorem 2.8.9 in <a href="chapBib.html#biBKohl05">[Koh05]</a> is not satisfied. If the option <code class="code">IsTame</code> is not set and the partitions <var class="Arg">P1</var> and <var class="Arg">P2</var> both consist entirely of single residue classes, then the returned mapping is affine on any residue class in <var class="Arg">P1</var>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">P1 := AllResidueClassesModulo(3);</span>
[ 0(3), 1(3), 2(3) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">P2 := List([[0,2],[1,4],[3,4]],ResidueClass);</span>
[ 0(2), 1(4), 3(4) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := RepresentativeAction(RCWA(Integers),P1,P2);</span>
<rcwa permutation of Z with modulus 3>
<span class="GAPprompt">gap></span> <span class="GAPinput">P1^elm = P2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(elm);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame);</span>
<tame rcwa permutation of Z with modulus 24>
<span class="GAPprompt">gap></span> <span class="GAPinput">P1^elm = P2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">elm := RepresentativeAction(RCWA(Integers),</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [ResidueClass(1,3),</span>
<span class="GAPprompt">></span> <span class="GAPinput">             ResidueClassUnion(Integers,3,[0,2])],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [ResidueClassUnion(Integers,5,[2,4]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">             ResidueClassUnion(Integers,5,[0,1,3])]);</span>
<rcwa permutation of Z with modulus 6>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ResidueClass(1,3),ResidueClassUnion(Integers,3,[0,2])]^elm;</span>
[ 2(5) U 4(5), Z \ 2(5) U 4(5) ]

</pre></div>

<p><a id="X82DBAF35788FA239" name="X82DBAF35788FA239"></a></p>

<h5>3.3-13 CollatzLikeMappingByOrbitTree</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CollatzLikeMappingByOrbitTree</code>( <var class="Arg">G</var>, <var class="Arg">n</var>, <var class="Arg">min_r</var>, <var class="Arg">max_r</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: either an rcwa mapping <span class="SimpleMath">f</span> which maps the sphere of radius <span class="SimpleMath">r</span> about <var class="Arg">n</var> under the action of <var class="Arg">G</var> into the sphere of radius <span class="SimpleMath">r-1</span> about <var class="Arg">n</var> for every <span class="SimpleMath">r</span> ranging from <var class="Arg">min_r</var> to <var class="Arg">max_r</var>, or <code class="code">fail</code>.</p>

<p>Obviously not for every rcwa group and every root point a mapping <span class="SimpleMath">f</span> with these properties exists, and if it exists, it usually depends on the choice of generators of the group.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,2,2,4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">              ClassTransposition(1,4,2,6));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := SparseRep(G);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := CollatzLikeMappingByOrbitTree(G,0,4,10);</span>
<rcwa mapping of Z with modulus 4 and 4 affine parts>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>

Rcwa mapping of Z with modulus 4 and 4 affine parts

        /
        | n+1      if n in 0(4)
        | (3n+1)/2 if n in 1(4)
 n |-> <  n/2      if n in 2(4)
        | n-1      if n in 3(4)
        |
        \

<span class="GAPprompt">gap></span> <span class="GAPinput">B := Ball(G,0,15:Spheres);</span>
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 6 ], [ 7 ], [ 14 ], [ 9, 15 ], [ 8, 18, 30 ], 
  [ 5, 19, 31 ], [ 4, 10, 38, 62 ], [ 11, 25, 39, 41, 63 ], 
  [ 22, 24, 40, 50, 78, 82, 126 ], [ 23, 33, 51, 79, 83, 127 ], 
  [ 32, 46, 66, 102, 158, 166, 254 ], 
  [ 21, 47, 67, 103, 105, 159, 167, 169, 255 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List([3..15],i->IsSubset(B[i-1],B[i]^f));</span>
[ true, true, true, true, true, true, true, true, true, true, true, true,
  true ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Trajectory(f,52,[0,1]);</span>
[ 52, 53, 80, 81, 122, 61, 92, 93, 140, 141, 212, 213, 320, 321, 482, 241, 
  362, 181, 272, 273, 410, 205, 308, 309, 464, 465, 698, 349, 524, 525, 788, 
  789, 1184, 1185, 1778, 889, 1334, 667, 666, 333, 500, 501, 752, 753, 1130, 
  565, 848, 849, 1274, 637, 956, 957, 1436, 1437, 2156, 2157, 3236, 3237, 
  4856, 4857, 7286, 3643, 3642, 1821, 2732, 2733, 4100, 4101, 6152, 6153, 
  9230, 4615, 4614, 2307, 2306, 1153, 1730, 865, 1298, 649, 974, 487, 486, 
  243, 242, 121, 182, 91, 90, 45, 68, 69, 104, 105, 158, 79, 78, 39, 38, 19, 
  18, 9, 14, 7, 6, 3, 2, 1 ]

</pre></div>

<p><a id="X781CBEFA7F39B58D" name="X781CBEFA7F39B58D"></a></p>

<h4>3.4 <span class="Heading">
  Special attributes of tame residue-class-wise affine groups
</span></h4>

<p>There are a couple of attributes which a priori make only sense for tame rcwa groups. With their help, various structural information about a given such group can be obtained. We have already seen above that there are for example methods for <code class="code">IsSolvableGroup</code>, <code class="code">IsPerfectGroup</code> and <code class="code">DerivedSubgroup</code> available for tame rcwa groups, while testing wild groups for solvability or perfectness is currently not always feasible. The purpose of this section is to describe the specific attributes of tame groups which are needed for these computations.</p>

<p><a id="X7F523A6B87825AB8" name="X7F523A6B87825AB8"></a></p>

<h5>3.4-1 <span class="Heading">
    RespectedPartition (of a tame rcwa group or -permutation)
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RespectedPartition</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">‣ RespectedPartition</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a shortest and coarsest possible respected partition of the rcwa group <var class="Arg">G</var> / of the rcwa permutation <var class="Arg">g</var>.</p>

<p>A tame element <span class="SimpleMath">g</span> <span class="SimpleMath">∈</span> RCWA(<span class="SimpleMath">R</span>) permutes a partition of <span class="SimpleMath">R</span> into finitely many residue classes on all of which it is affine. Given a tame group <span class="SimpleMath">G</span> <span class="SimpleMath"><</span> RCWA(<span class="SimpleMath">R</span>), there is a common such partition for all elements of <span class="SimpleMath">G</span>. We call the mentioned partitions <em>respected partitions</em> of <span class="SimpleMath">g</span> or <span class="SimpleMath">G</span>, respectively.</p>

<p>An rcwa group or an rcwa permutation has a respected partition if and only if it is tame. This holds either by definition or by Theorem 2.5.8 in <a href="chapBib.html#biBKohl05">[Koh05]</a>, depending on how one introduces the notion of tameness.</p>

<p>There is an operation <code class="code">RespectsPartition(<var class="Arg">G</var>,<var class="Arg">P</var>)</code> / <code class="code">RespectsPartition(<var class="Arg">g</var>,<var class="Arg">P</var>)</code>, which tests whether <var class="Arg">G</var> or <var class="Arg">g</var> respects a given partition <var class="Arg">P</var>. The permutation induced by <var class="Arg">g</var> on <code class="code">P</code> can be computed efficiently by <code class="code">PermutationOpNC(<var class="Arg">g</var>,P,OnPoints)</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));</span>
<rcwa group over Z with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTame(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(G);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">P := RespectedPartition(G);</span>
[ 0(4), 2(4), 1(6), 3(6), 5(6) ]

</pre></div>

<p><a id="X831ADC1584DE6113" name="X831ADC1584DE6113"></a></p>

<h5>3.4-2 <span class="Heading">
    ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
  </span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ActionOnRespectedPartition</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">‣ KernelOfActionOnRespectedPartition</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">‣ RankOfKernelOfActionOnRespectedPartition</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: the action of the tame rcwa group <var class="Arg">G</var> on <code class="code">RespectedPartition(<var class="Arg">G</var>)</code>, the kernel of this action or the rank of the latter, respectively.</p>

<p>The method for <code class="code">KernelOfActionOnRespectedPartition</code> uses the package <strong class="pkg">Polycyclic</strong> <a href="chapBib.html#biBPolycyclic">[EHN13]</a>. The rank of the largest free abelian subgroup of the kernel of the action of <var class="Arg">G</var> on its stored respected partition is <code class="code">RankOfKernelOfActionOnRespectedPartition(<var class="Arg">G</var>)</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := ActionOnRespectedPartition(G);</span>
Group([ (1,3), (1,2) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">H = Action(G,P);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(H);</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">K := KernelOfActionOnRespectedPartition(G);</span>
<rcwa group over Z with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">RankOfKernelOfActionOnRespectedPartition(G);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(G,K);</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">List(GeneratorsOfGroup(K),Factorization);</span>
[ [ ClassShift( 0(4) ) ], [ ClassShift( 2(4) ) ], [ ClassShift( 1(6) ) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Image(IsomorphismPcpGroup(K));</span>
Pcp-group with orders [ 0, 0, 0 ]

</pre></div>

<p>Let <span class="SimpleMath">G</span> be a tame rcwa group over ℤ, let <span class="SimpleMath">mathcalP</span> be a respected partition of <span class="SimpleMath">G</span> and put <span class="SimpleMath">m := |mathcalP|</span>. Then there is an rcwa permutation <span class="SimpleMath">g</span> which maps <span class="SimpleMath">mathcalP</span> to the partition of ℤ into the residue classes (mod <span class="SimpleMath">m</span>), and the conjugate <span class="SimpleMath">G^g</span> of <span class="SimpleMath">G</span> under such a permutation is integral (cf. <a href="chapBib.html#biBKohl05">[Koh05]</a>, Theorem 2.5.14).</p>

<p>The conjugate <span class="SimpleMath">G^g</span> can be determined by the operation <code class="code">IntegralConjugate</code>, and the conjugating permutation <span class="SimpleMath">g</span> can be determined by the operation <code class="code">IntegralizingConjugator</code>. Both operations are applicable to rcwa permutations as well. Note that a tame rcwa group does not determine its integral conjugate uniquely.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G^IntegralizingConjugator(G) = IntegralConjugate(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">RespectedPartition(G);</span>
[ 0(4), 2(4), 1(6), 3(6), 5(6) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RespectedPartition(G)^IntegralizingConjugator(G);</span>
[ 0(5), 1(5), 2(5), 3(5), 4(5) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">last = RespectedPartition(IntegralConjugate(G));</span>
true

</pre></div>

<p><a id="X81941A247942FB99" name="X81941A247942FB99"></a></p>

<h4>3.5 <span class="Heading">Generating pseudo-random elements of RCWA(R) and CT(R)</span></h4>

<p>There are methods for the operation <code class="code">Random</code> for RCWA(<span class="SimpleMath">R</span>) and CT(<span class="SimpleMath">R</span>). These methods are designed to be suitable for generating interesting examples. No particular distribution is guaranteed.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">elm := Random(RCWA(Integers));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(elm);</span>

Rcwa permutation of Z with modulus 180

        /
        | 6n+12     if n in 2(10) U 4(10) U 6(10) U 8(10)
        | 3n+3      if n in 1(20) U 5(20) U 9(20) U 17(20)
        | 6n+10     if n in 0(10)
        | (n+1)/2   if n in 15(60) U 27(60) U 39(60) U 51(60)
        | (n+7)/2   if n in 19(60) U 31(60) U 43(60) U 55(60)
        | 3n+1      if n in 13(20)
        | (-n+17)/6 if n in 23(180) U 35(180) U 59(180) U 71(180) U 
 n |-> <                    95(180) U 131(180) U 143(180) U 179(180)
        | (-n-1)/6  if n in 11(180) U 47(180) U 83(180) U 155(180)
        | (-n+7)/2  if n in 3(60)
        | (n+3)/2   if n in 7(60)
        | (n-17)/6  if n in 107(180)
        | (-n+11)/6 if n in 119(180)
        | (-n+29)/6 if n in 167(180)
        |
        \

</pre></div>

<p>The elements which are returned by this method are obtained by multiplying class shifts (see <code class="func">ClassShift</code> (<a href="chap2.html#X86B611BD7EED62A1"><span class="RefLink">2.2-1</span></a>)), class reflections (see <code class="func">ClassReflection</code> (<a href="chap2.html#X7896C5417E3692B4"><span class="RefLink">2.2-2</span></a>)) and class transpositions (see <code class="func">ClassTransposition</code> (<a href="chap2.html#X8716A75F7DD1C46B"><span class="RefLink">2.2-3</span></a>)). These factors can be retrieved by factoring:</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">Factorization(elm);</span>
[ ClassTransposition(0,2,3,4), ClassTransposition(1,2,4,6), ClassShift(0,2), 
  ClassShift(1,3), ClassReflection(2,5), ClassReflection(1,3), 
  ClassReflection(1,2) ]

</pre></div>

<p><a id="X86327F6C83D09798" name="X86327F6C83D09798"></a></p>

<h4>3.6 <span class="Heading">The categories of residue-class-wise affine groups</span></h4>

<p><a id="X84AFBB997B694A3D" name="X84AFBB997B694A3D"></a></p>

<h5>3.6-1 IsRcwaGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRcwaGroup</code>( <var class="Arg">G</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">‣ IsRcwaGroupOverZ</code>( <var class="Arg">G</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">‣ IsRcwaGroupOverZ_pi</code>( <var class="Arg">G</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">‣ IsRcwaGroupOverGFqx</code>( <var class="Arg">G</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <var class="Arg">G</var> is an rcwa group, an rcwa group over the ring of integers, an rcwa group over a semilocalization of the ring of integers or an rcwa group over 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 groups over the ring of integers and over its semilocalizations. For this reason there is a category <code class="code">IsRcwaGroupOverZOrZ_pi</code> which is the union of <code class="code">IsRcwaGroupOverZ</code> and <code class="code">IsRcwaGroupOverZ_pi</code>.</p>

<p>To allow distinguishing the groups RCWA(<span class="SimpleMath">R</span>) and CT(<span class="SimpleMath">R</span>) from others, they have the characteristic property <code class="code">IsNaturalRCWA</code> or <code class="code">IsNaturalCT</code>, respectively.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap2.html">[Previous Chapter]</a>    <a href="chap4.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="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>

Messung V0.5 in Prozent
C=100 H=100 G=100

¤ Dauer der Verarbeitung: 0.34 Sekunden  (vorverarbeitet am  2026-04-27) ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.