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">Goto Chapter: <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>

<a href="chap3_mj.html">[MathJax on]</a>
<a id="X874A3BB684F0639A" name="X874A3BB684F0639A"></a>
<div class="ChapSects"><a href="chap3.html#X874A3BB684F0639A">3 Residue-Class-Wise Affine Groups</a>
<div class="ContSect"> <a href="chap3.html#X81242A6586A604A3">3.1 Constructing residue-class-wise affine groups</a>

<div class="ContSSBlock">
 <a href="chap3.html#X7EB8A301790290C7">3.1-1 IsomorphismRcwaGroup</a>
 <a href="chap3.html#X79CAE48981C11FE8">3.1-2 DirectProduct</a>
 <a href="chap3.html#X80D13D2A7AD73C2C">3.1-3 
 WreathProduct
 (for an rcwa group over Z, with a permutation group or (ℤ,+))
 </a>

 <a href="chap3.html#X8794913B878DD5C4">3.1-4 MergerExtension</a>
 <a href="chap3.html#X8143AB647801F438">3.1-5 GroupByResidueClasses</a>
 <a href="chap3.html#X852EF2C079E4D7FF">3.1-6 
 Restriction (of an rcwa mapping or -group, by an injective rcwa mapping)
 </a>

 <a href="chap3.html#X82171D7287CBED95">3.1-7 
 Induction (of an rcwa mapping or -group, by an injective rcwa mapping)
 </a>

 <a href="chap3.html#X79450C1C8756FEB3">3.1-8 RCWA</a>
 <a href="chap3.html#X7BD42D8481300E25">3.1-9 CT</a>
</div></div>
<div class="ContSect"> <a href="chap3.html#X80C042BE82EE0F9A">3.2 
 Basic routines for investigating residue-class-wise affine groups
</a>

<div class="ContSSBlock">
 <a href="chap3.html#X864A7E3E87F366A8">3.2-1 StructureDescription</a>
 <a href="chap3.html#X83527DA37C5CB2C7">3.2-2 EpimorphismFromFpGroup</a>
 <a href="chap3.html#X8463E34286344F06">3.2-3 PreImagesRepresentative</a>
</div></div>
<div class="ContSect"> <a href="chap3.html#X8151BE577FFDCE87">3.3 
 The natural action of an rcwa group on the underlying ring
</a>

<div class="ContSSBlock">
 <a href="chap3.html#X7C046BE97EE53692">3.3-1 Orbit (for an rcwa group and either a point or a set) </a>

 <a href="chap3.html#X7B7A3AF97D195E33">3.3-2 GrowthFunctionOfOrbit</a>
 <a href="chap3.html#X7D9DFAC97F9F0891">3.3-3 DrawOrbitPicture</a>
 <a href="chap3.html#X78F145197F63A25D">3.3-4 
 ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations)
 </a>

 <a href="chap3.html#X80D18D0778A96C16">3.3-5 
 ShortResidueClassOrbits & ShortResidueClassCycles
 </a>

 <a href="chap3.html#X80C080287A355EFF">3.3-6 ComputeCycleLength</a>
 <a href="chap3.html#X7F76B04E86C77B94">3.3-7 CycleRepresentativesAndLengths</a>
 <a href="chap3.html#X8777A62286597D53">3.3-8 FixedResidueClasses</a>
 <a href="chap3.html#X8735855587CC029F">3.3-9 
 Ball (for group, element and radius or group, point, radius and action)
 </a>

 <a href="chap3.html#X87A3462C82FD376E">3.3-10 RepresentativeAction</a>
 <a href="chap3.html#X8587246A7F890849">3.3-11 ProjectionsToInvariantUnionsOfResidueClasses</a>
 <a href="chap3.html#X866843D08213067E">3.3-12 RepresentativeAction</a>
 <a href="chap3.html#X82DBAF35788FA239">3.3-13 CollatzLikeMappingByOrbitTree</a>
</div></div>
<div class="ContSect"> <a href="chap3.html#X781CBEFA7F39B58D">3.4 
 Special attributes of tame residue-class-wise affine groups
</a>

<div class="ContSSBlock">
 <a href="chap3.html#X7F523A6B87825AB8">3.4-1 
 RespectedPartition (of a tame rcwa group or -permutation)
 </a>

 <a href="chap3.html#X831ADC1584DE6113">3.4-2 
 ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
 </a>

</div></div>
<div class="ContSect"> <a href="chap3.html#X81941A247942FB99">3.5 Generating pseudo-random elements of RCWA(R) and CT(R)</a>

</div>
<div class="ContSect"> <a href="chap3.html#X86327F6C83D09798">3.6 The categories of residue-class-wise affine groups</a>

<div class="ContSSBlock">
 <a href="chap3.html#X84AFBB997B694A3D">3.6-1 IsRcwaGroup</a>
</div></div>
</div>

<h3>3 Residue-Class-Wise Affine Groups</h3>

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

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

<h4>3.1 Constructing residue-class-wise affine groups</h4>

As any other groups in GAP, 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>.

<div class="example"><pre>

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

</pre></div>

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

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

<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>
Returns: a monomorphism from the group <var class="Arg">G</var> to RCWA(<var class="Arg">R</var>) or to RCWA(ℤ), respectively.

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(ℤ).

<div class="example"><pre>

gap> F := FreeProduct(Group((1,2)(3,4),(1,3)(2,4)),Group((1,2,3)),
> SymmetricGroup(3));
<fp group on the generators [ f1, f2, f3, f4, f5 ]>
gap> IsomorphismRcwaGroup(F);
[ 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> ]
gap> IsomorphismRcwaGroup(FreeGroup(2));
[ f1, f2 ] -> [ <wild rcwa permutation of Z with modulus 8>,
 <wild rcwa permutation of Z with modulus 8> ]
gap> F2 := Image(last);
<wild rcwa group over Z with 2 generators>

</pre></div>

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:

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

<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>
Returns: an rcwa group isomorphic to the direct product of the rcwa groups over ℤ given as arguments.

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 n ↦ mn, n ↦ mn+1, n ↦ mn+2 ... (→ <code class="func">Restriction</code> (<a href="chap3.html#X852EF2C079E4D7FF">3.1-6</a>)), where m denotes the number of groups given as arguments.

<div class="example"><pre>

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

</pre></div>

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

<h5>3.1-3 
 WreathProduct
 (for an rcwa group over Z, with a permutation group or (ℤ,+))
 </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>
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.

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 (→ <code class="func">Restriction</code> (<a href="chap3.html#X852EF2C079E4D7FF">3.1-6</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>.

<div class="example"><pre>

gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;
gap> F2wrA5 := WreathProduct(F2,AlternatingGroup(5));;
gap> Embedding(F2wrA5,1);
[ <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> ]
gap> Embedding(F2wrA5,2);
[ (1,2,3,4,5), (3,4,5) ] -> [ ( 0(5), 1(5), 2(5), 3(5), 4(5) ),
 ( 2(5), 3(5), 4(5) ) ]
gap> ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1)));
<wild rcwa group over Z with 2 generators>
gap> Embedding(ZwrZ,1);
[ ClassShift( Z ) ] ->
[ <tame rcwa permutation of Z with modulus 4, of order infinity> ]
gap> Embedding(ZwrZ,2);
[ ClassShift( Z ) ] -> [ <wild rcwa permutation of Z with modulus 4> ]

</pre></div>

Also, rcwa groups can be obtained as particular extensions of finite permutation groups:

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

<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>
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>.

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>.

Let n be the largest moved point of <var class="Arg">G</var>, and let H be the tame subgroup of CT(ℤ) which respects the partition mathcalP of ℤ into the residue classes (mod n), and which acts on mathcalP as <var class="Arg">G</var> acts on {1, dots, n}. Further assume that <var class="Arg">points</var> = {p_1, dots, p_k} and <var class="Arg">point</var> = p, and put r_i := p_i-1, i = 1, dots, k and r := p-1. Now let σ be the product of the class transpositions τ_r_i(n),r+(i-1)n(kn), i = 1, dots, k. The group returned by this operation is the extension of H by the involution σ. -- 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.

<div class="example"><pre>

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

</pre></div>

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

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

<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>
Returns: the group which is generated by all class transpositions which interchange disjoint residue classes in <var class="Arg">classes</var>.

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

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.

<div class="example"><pre>

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

</pre></div>

Various ways to construct rcwa groups are based on certain monomorphisms from the group RCWA(R) 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 restriction monomorphisms. The following operation computes images of rcwa mappings and -groups under these embeddings of RCWA(R) into itself:

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

<h5>3.1-6 
 Restriction (of an rcwa mapping or -group, by an injective rcwa mapping)
 </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>
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>.

By definition, the restriction g_f 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 f ⋅ g_f = g ⋅ f 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>.

The restriction 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.

<div class="example"><pre>

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

</pre></div>

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

<h5>3.1-7 
 Induction (of an rcwa mapping or -group, by an injective rcwa mapping)
 </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>
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>.

Induction 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>.

<div class="example"><pre>

gap> Induction(F2tilde,RcwaMapping([[5,3,1]])) = F2;
true

</pre></div>

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

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.

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 modulus 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 multiplier respectively divisor of an rcwa group is the lcm of the multipliers respectively divisors of its elements in case such an lcm exists and ∞ otherwise. The prime set 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 class-wise translating, integral or class-wise order-preserving 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).

<div class="example"><pre>

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

</pre></div>

All rcwa groups over a ring R are subgroups of RCWA(R). The group RCWA(R) itself is not finitely generated, thus cannot be constructed as described above. It is handled as a special case:

<a id="X79450C1C8756FEB3" name="X79450C1C8756FEB3"></a>

<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>
Returns: the group RCWA(<var class="Arg">R</var>) of all residue-class-wise affine permutations of the ring <var class="Arg">R</var>.

<div class="example"><pre>

gap> RCWA_Z := RCWA(Integers);
RCWA(Z)
gap> IsSubgroup(RCWA_Z,G);
true

</pre></div>

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">3.5</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>:

<div class="example"><pre>

gap> List([2,105],NrConjugacyClassesOfRCWAZOfOrder);
[ infinity, 218 ]

</pre></div>

We denote the group which is generated by all class transpositions of the ring R by CT(R). This group is handled as a special case as well:

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

<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>
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>.

<div class="example"><pre>

gap> CT_Z := CT(Integers);
CT(Z)
gap> IsSimpleGroup(CT_Z); # One of a number of stored attributes/properties.
true
gap> V := CT([2],Integers);
CT_[ 2 ](Z)
gap> GeneratorsOfGroup(V);
[ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 0(2), 1(4) ), ( 1(4), 2(4) ) ]
gap> G := CT([2,3],Integers); 
CT_[ 2, 3 ](Z)
gap> GeneratorsOfGroup(G);
[ ( 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>

The group CT(ℤ) has an outer automorphism which is given by conjugation with n ↦ -n - 1. 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.

<div class="example"><pre>

gap> ct := ClassTransposition(0,2,1,6);
( 0(2), 1(6) )
gap> Mirrored(ct);
( 1(2), 4(6) )
gap> G := Group(List([[0,2,1,2],[0,3,2,3],[2,4,1,6]],ClassTransposition));;
gap> ShortOrbits(G,[-100..100],100);
[ [ 0 .. 5 ] ]
gap> ShortOrbits(Mirrored(G),[-100..100],100);
[ [ -6 .. -1 ] ]

</pre></div>

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

<div class="example"><pre>

gap> NrElementsOfCTZWithGivenModulus{[1..8]};
[ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680 ]

</pre></div>

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 ℕ_0 in RCWA(ℤ). It can be determined by the function <code class="code">NrConjugacyClassesOfCTZOfOrder</code>.

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

<h4>3.2 
 Basic routines for investigating residue-class-wise affine groups
</h4>

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 a very little!) information on the group structure is a dedicated method for the operation <code class="code">StructureDescription</code>:

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

<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>
Returns: a string which sometimes gives a little glimpse of the structure of the rcwa group <var class="Arg">G</var>.

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

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 2,3,4,dots are denoted by <code class="code">F2</code>, <code class="code">F3</code>, <code class="code">F4</code>, dots. 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.

<div class="example"><pre>

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

</pre></div>

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.

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">3.4-1</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.

<div class="example"><pre>

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

</pre></div>

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

<div class="example"><pre>

gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,3,1,3));;
gap> IsomorphismPermGroup(G);
[ ( 0(2), 1(2) ), ( 0(3), 1(3) ) ] -> [ (1,2)(3,4)(5,6), (1,2)(4,5) ]

</pre></div>

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.).

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.

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, RCWA 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.

<div class="example"><pre>

gap> G := Group(ClassShift(0,3),ClassTransposition(0,3,2,6));;
gap> ClassShift(2,6)^7 * ClassTransposition(0,3,2,6)
> * ClassShift(0,3)^-3 in G;
true
gap> ClassShift(0,1) in G;
false

</pre></div>

The conjugacy problem for rcwa groups is difficult, and RCWA provides only methods to solve it in some reasonably easy cases.

<div class="example"><pre>

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

</pre></div>

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

<div class="example"><pre>

gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(1,3));;
gap> H := Group(ClassTransposition(0,2,1,6),ClassShift(1,3));;
gap> IsTame(G);
true
gap> IsTame(H);
false

</pre></div>

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.

<div class="example"><pre>

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

When investigating a group, a basic task is to find relations among the generators:

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

<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>
Returns: an epimorphism from a finitely presented group to the rcwa group <var class="Arg">G</var>.

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.

<div class="example"><pre>

gap> a := ClassTransposition(2,4,3,4);;
gap> b := ClassTransposition(4,6,8,12);;
gap> c := ClassTransposition(3,4,4,6);;
gap> G := SparseRep(Group(a,b,c));
<(2(4),3(4)),(4(6),8(12)),(3(4),4(6))>
gap> phi := EpimorphismFromFpGroup(G,6);
#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) ) ]
gap> RelatorsOfFpGroup(Source(phi));
[ 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>

A related very common task is to factor group elements into generators:

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

<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>
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.

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.

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">3.3-10</a>).

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>.

<div class="example"><pre>

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

</pre></div>

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

<h4>3.3 
 The natural action of an rcwa group on the underlying ring
</h4>

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 RCWA's functionality related to this action.

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:

<div class="example"><pre>

gap> G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));;
gap> IsTransitive(G,Integers);
true

</pre></div>

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:

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

</dd>
<dt><code class="code">words</code>, <code class="code">classes</code></dt>
<dd>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.

</dd>
<dt><code class="code">smallpointbound</code></dt>
<dd>in addition to finding a list of group elements g_i such that for any large enough integer n in the support of <var class="Arg">G</var> there is some g_i such that n^g_i < n, 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.

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

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

</dd>
</dl>
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>.

<div class="example"><pre>

gap> G := Group(List([[0,2,1,2],[0,3,2,3],[1,2,2,4]],
> ClassTransposition));
<(0(2),1(2)),(0(3),2(3)),(1(2),2(4))>
gap> IsTransitiveOnNonnegativeIntegersInSupport(G);
true
gap> TransitivityCertificate(G);
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 ] )
gap> SimplifiedCertificate(last);
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 ] )
gap> G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],
> ClassTransposition)); # '3n+1 group'
<(0(2),1(2)),(1(2),2(4)),(1(4),2(6))>
gap> cert := TryToComputeTransitivityCertificate(G,10);
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 ] )
gap> Union(Flat(cert.classes));
<union of 90 residue classes (mod 96) (6 classes)>
gap> Difference(Integers,Union(Flat(cert.classes)));
12(48) U 28(48) U 52(96) U 84(96)
gap> cert := TryToComputeTransitivityCertificate(G,20); # try larger bound
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 ] )
gap> Difference(Integers,Union(Flat(cert.classes)));
<union of 44 residue classes (mod 768) (14 classes)>
gap> Intersection([0..100],last);
[ 52, 60, 76, 84 ]

</pre></div>

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 ℕ_0 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:

<dl>
<dt><code class="code">R</code></dt>
<dd>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.

</dd>
<dt><code class="code">D</code></dt>
<dd>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.

</dd>
<dt><code class="code">g</code></dt>
<dd>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>.

</dd>
<dt><code class="code">phi</code></dt>
<dd>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.

</dd>
<dt><code class="code">w</code></dt>
<dd>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>.

</dd>
</dl>

<div class="example"><pre>

gap> G := Group(ClassTransposition(1,3,2,3),ClassTransposition(3,4,4,6),
> ClassTransposition(2,4,1,6));
<(1(3),2(3)),(3(4),4(6)),(2(4),1(6))>
gap> R := SupersetOfOrbitRepresentatives(G,4,6);
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>

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

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

<h5>3.3-1 Orbit (for an rcwa group and either a point or a set) </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>
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.

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.

<div class="example"><pre>

gap> G := Group(ClassShift(0,2),ClassTransposition(0,3,1,3));
<rcwa group over Z with 2 generators>
gap> Orbit(G,0);
Z \ 5(6)
gap> Orbit(G,5);
[ 5 ]
gap> Orbit(G,ResidueClass(0,2));
[ 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) ]
gap> Length(Orbit(G,ResidueClass(0,4)));
80
gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,2,1,4),
> ClassReflection(0,3));
<rcwa group over Z with 3 generators>
--> --------------------

--> maximum size reached

--> --------------------

quality100%

¤ Dauer der Verarbeitung: 0.42 Sekunden ¤

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 ist noch experimentell.