<?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 5: Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap4.html">Previous Chapter</a> <a href="chap6.html">Next Chapter</a> </div>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>
<div class="ChapSects"><a href="chap5.html#X7A489A5D79DA9E5C">5. <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X86C2BAE3876985A6">5.1 <span class="Heading">
Factoring Collatz' permutation of the integers
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X878499AF7889FD9E">5.2 <span class="Heading">
An rcwa mapping which seems to be contracting, but very slow
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X84A915BA833E0BDE">5.3 <span class="Heading">Checking a result by P. Andaloro</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7E8CD9B67ED78735">5.4 <span class="Heading">Two examples by Matthews and Leigh</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7A8F55CA87A16900">5.5 <span class="Heading">Exploring the structure of a wild rcwa group</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7D0928AE839F1C49">5.6 <span class="Heading">A wild rcwa mapping which has only finite cycles</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7A8605E680F664BF">5.7 <span class="Heading">An abelian rcwa group over a polynomial ring</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X87383623856ED81B">5.8 <span class="Heading">
A tame group generated by commutators of wild permutations
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X78DFE4B4821E07A6">5.9 <span class="Heading">Checking for solvability</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X783D54DC7A646273">5.10 <span class="Heading">Some examples over (semi)localizations of the integers</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X846D7D087861E0AC">5.11 <span class="Heading">
Twisting 257-cycles into an rcwa mapping with modulus 32
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X78D5DC93845CA6A0">5.12 <span class="Heading"> The behaviour of the moduli of powers </span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X855A3CD88459958B">5.13 <span class="Heading"> Images and preimages under the Collatz mapping </span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7968C1DF7EF0BD8E">5.14 <span class="Heading">
A group which acts 4-transitively on the positive integers
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X87E7FCE27EACDA38">5.15 <span class="Heading">
A group which acts 3-transitively, but not 4-transitively on Z
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X85DD5E9C7878CAE3">5.16 <span class="Heading">
Grigorchuk groups
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7DD9502F80364631">5.17 <span class="Heading">
Forward orbits of a monoid with 2 generators
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X81407BD58648D206">5.18 <span class="Heading">
Representations of the free group of rank 2
</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X85B4B4DA83B09E81">5.19 <span class="Heading">
Representations of the modular group PSL(2,Z)
</span></a>
</div>
</div>
<h3>5. <span class="Heading">Examples</span></h3>
<p>This chapter discusses a number of "nice" examples of rcwa mappings and -groups in detail. All of them show different aspects of the package, and the order in which they appear is entirely arbitrary. In particular they are not ordered by degree of interestingness or difficulty.</p>
<p>Please note that now since quite a while no further examples have been added to this chapter, and that the capabilities of this package have been extended considerably in the meantime.</p>
<p>The rcwa mappings defined in this chapter (and in fact many more) can be found in the file <code class="file">pkg/rcwa/examples/examples.g</code>, so there is no need to extract them from the manual files. This file can be read into the current <strong class="pkg">GAP</strong> session by issueing <code class="code">RCWAReadExamples( );</code>.</p>
<p>The examples are typically far from discussing the respective aspects exhaustively. It is quite likely that in many instances by just a few little modifications or additional easy commands you can find out interesting things yourself -- have fun!</p>
<p><a id="X86C2BAE3876985A6" name="X86C2BAE3876985A6"></a></p>
<h4>5.1 <span class="Heading">
Factoring Collatz' permutation of the integers
</span></h4>
<p>In 1932, Lothar Collatz mentioned in his notebook the following permutation of the integers:</p>
<table class="example">
<tr><td><pre>
gap> Collatz := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);;
gap> SetName(Collatz,"Collatz"); Display(Collatz);
Rcwa mapping of Z with modulus 3
n mod 3 | n^Collatz
------------------------------------+------------------------------------
0 | 2n/3
1 | (4n - 1)/3
2 | (4n + 1)/3
gap> ShortCycles(Collatz,[-50..50],50); # There are some finite cycles:
[ [ -111, -74, -99, -66, -44, -59, -79, -105, -70, -93, -62, -83 ],
[ -9, -6, -4, -5, -7 ], [ -3, -2 ], [ -1 ], [ 0 ], [ 1 ], [ 2, 3 ],
[ 4, 5, 7, 9, 6 ], [ 44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66 ] ]
</pre></td></tr></table>
<p>The cycle structure of Collatz' permutation has not been completely determined yet. In particular it is not known whether the cycle containing 8 is finite or infinite. Nevertheless, the factorization routine included in this package can determine a factorization of this permutation into class transpositions, i.e. involutions interchanging two disjoint residue classes:</p>
<table class="example">
<tr><td><pre>
gap> Collatz in CT(Integers); # `Collatz' lies in the simple group CT(Z).
true
gap> Length(Factorization(Collatz));
212
</pre></td></tr></table>
<p>Setting the Info level of <code class="code">InfoRCWA</code> equal to 2 (simply issue <code class="code">RCWAInfo(2);</code>) causes the factorization routine to display detailed information on the progress of the factoring process. For reasons of saving space, this is not done in this manual.</p>
<p>We would like to get a factorization into fewer factors. Firstly, we try to factor the inverse -- just like the various options interpreted by the factorization routine, this has influence on decisions taken during the factoring process:</p>
<table class="example">
<tr><td><pre>
gap> Length(Factorization(Collatz^-1));
129
</pre></td></tr></table>
<p>This is already a shorter product, but can still be improved. We remember the <code class="code">mKnot</code>'s, of which the permutation <code class="code">mKnot(3)</code> looks very similar to Collatz' permutation. Therefore it is straightforward to try to factor both <code class="code">mKnot(3)</code> and <code class="code">Collatz/mKnot(3)</code>, and to look whether the sum of the numbers of factors is less than 129:</p>
<table class="example">
<tr><td><pre>
gap> KnotFacts := Factorization(mKnot(3));;
gap> QuotFacts := Factorization(Collatz/mKnot(3));;
gap> List([KnotFacts,QuotFacts],Length);
[ 59, 9 ]
gap> CollatzFacts := Concatenation(QuotFacts,KnotFacts);
[ ClassTransposition(0,6,4,6), ClassTransposition(0,6,5,6),
ClassTransposition(0,6,3,6), ClassTransposition(0,6,1,6),
ClassTransposition(0,6,2,6), ClassTransposition(2,3,4,6),
ClassTransposition(0,3,4,6), ClassTransposition(2,3,1,6),
ClassTransposition(0,3,1,6), ClassTransposition(0,36,35,36),
ClassTransposition(0,36,22,36), ClassTransposition(0,36,18,36),
ClassTransposition(0,36,17,36), ClassTransposition(0,36,14,36),
ClassTransposition(0,36,20,36), ClassTransposition(0,36,4,36),
ClassTransposition(2,36,8,36), ClassTransposition(2,36,16,36),
ClassTransposition(2,36,13,36), ClassTransposition(2,36,9,36),
ClassTransposition(2,36,7,36), ClassTransposition(2,36,6,36),
ClassTransposition(2,36,3,36), ClassTransposition(2,36,10,36),
ClassTransposition(2,36,15,36), ClassTransposition(2,36,12,36),
ClassTransposition(2,36,5,36), ClassTransposition(21,36,28,36),
ClassTransposition(21,36,33,36), ClassTransposition(21,36,30,36),
ClassTransposition(21,36,23,36), ClassTransposition(21,36,34,36),
ClassTransposition(21,36,31,36), ClassTransposition(21,36,27,36),
ClassTransposition(21,36,25,36), ClassTransposition(21,36,24,36),
ClassTransposition(26,36,32,36), ClassTransposition(26,36,29,36),
ClassTransposition(10,18,35,36), ClassTransposition(5,18,35,36),
ClassTransposition(10,18,17,36), ClassTransposition(5,18,17,36),
ClassTransposition(8,12,14,24), ClassTransposition(6,9,17,18),
ClassTransposition(3,9,17,18), ClassTransposition(0,9,17,18),
ClassTransposition(6,9,16,18), ClassTransposition(3,9,16,18),
ClassTransposition(0,9,16,18), ClassTransposition(6,9,11,18),
ClassTransposition(3,9,11,18), ClassTransposition(0,9,11,18),
ClassTransposition(6,9,4,18), ClassTransposition(3,9,4,18),
ClassTransposition(0,9,4,18), ClassTransposition(0,6,14,24),
ClassTransposition(0,6,2,24), ClassTransposition(8,12,17,18),
ClassTransposition(7,12,17,18), ClassTransposition(8,12,11,18),
ClassTransposition(7,12,11,18), PrimeSwitch(3)^-1,
ClassTransposition(7,12,17,18), ClassTransposition(2,6,17,18),
ClassTransposition(0,3,17,18), PrimeSwitch(3)^-1, PrimeSwitch(3)^-1,
PrimeSwitch(3)^-1 ]
gap> Product(CollatzFacts) = Collatz; # Check.
true
</pre></td></tr></table>
<p>The factors <code class="code">PrimeSwitch(3)</code> are products of 6 class transpositions (cf. <code class="func">PrimeSwitch</code> (<a href="chap2.html#X861C74E97AE5DA3B"><b>2.5-2</b></a>)). At the end of Section <a href="chap5.html#X7D0928AE839F1C49"><b>5.6</b></a>, a much smaller factorization task is performed "manually" for purposes of illustration.</p>
<p><a id="X878499AF7889FD9E" name="X878499AF7889FD9E"></a></p>
<h4>5.2 <span class="Heading">
An rcwa mapping which seems to be contracting, but very slow
</span></h4>
<p>The iterates of an integer under the Collatz mapping T seem to approach its contraction centre -- this is the finite set where all trajectories end up after a finite number of steps -- rather quickly and do not get very large before doing so (of course this is a purely heuristic statement as the 3n+1 Conjecture has not been proved so far!):</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);;
gap> S0 := LikelyContractionCentre(T,100,1000);
#I Warning: `LikelyContractionCentre' is highly probabilistic.
The returned result can only be regarded as a rough guess.
See ?LikelyContractionCentre for more information.
[ -136, -91, -82, -68, -61, -55, -41, -37, -34, -25, -17, -10, -7, -5,
-1, 0, 1, 2 ]
gap> S0^T = S0; # This holds by definition of the contraction centre.
true
gap> List([1..30],n->Length(Trajectory(T,n,S0)));
[ 1, 1, 5, 2, 4, 6, 11, 3, 13, 5, 10, 7, 7, 12, 12, 4, 9, 14, 14, 6, 6,
11, 11, 8, 16, 8, 70, 13, 13, 13 ]
gap> Maximum(List([1..1000],n->Length(Trajectory(T,n,S0))));
113
gap> Maximum(List([1..1000],n->Maximum(Trajectory(T,n,S0))));
125252
</pre></td></tr></table>
<p>The following mapping seems to be contracting as well, but its trajectories are much longer:</p>
<table class="example">
<tr><td><pre>
gap> f6 := RcwaMapping([[ 1,0,6],[ 5, 1,6],[ 7,-2,6],
> [11,3,6],[11,-2,6],[11,-1,6]]);;
gap> SetName(f6,"f6");
gap> Display(f6);
Rcwa mapping of Z with modulus 6
n mod 6 | n^f6
------------------------------------+------------------------------------
0 | n/6
1 | (5n + 1)/6
2 | (7n - 2)/6
3 | (11n + 3)/6
4 | (11n - 2)/6
5 | (11n - 1)/6
gap> S0 := LikelyContractionCentre(f6,1000,100000);;
#I Warning: `LikelyContractionCentre' is highly probabilistic.
The returned result can only be regarded as a rough guess.
See ?LikelyContractionCentre for more information.
gap> Trajectory(f6,25,S0);
[ 25, 21, 39, 72, 12, 2 ]
gap> List([1..100],n->Length(Trajectory(f6,n,S0)));
[ 1, 1, 3, 4, 1, 2, 3, 2, 1, 5, 7, 2, 8, 17, 3, 16, 1, 4, 17, 6, 5, 2,
5, 5, 6, 1, 4, 2, 15, 1, 1, 3, 2, 5, 13, 3, 2, 3, 4, 1, 8, 4, 4, 2, 7,
19, 23517, 3, 9, 3, 1, 18, 14, 2, 20, 23512, 14, 2, 6, 6, 1, 4, 19,
12, 23511, 8, 23513, 10, 1, 13, 13, 3, 1, 23517, 7, 20, 7, 9, 9, 6,
12, 8, 6, 18, 14, 23516, 31, 12, 23545, 4, 21, 19, 5, 1, 17, 17, 13,
19, 6, 23515 ]
gap> Maximum(Trajectory(f6,47,S0));
7363391777762473304431877054771075818733690108051469808715809256737742295\
45698886054
</pre></td></tr></table>
<p>Computing the trajectory of 3224 takes quite a while -- this trajectory ascends to about 3 * 10^2197, before it approaches the fixed point 2 after 19949562 steps.</p>
<p>When constructing the mapping <code class="code">f6</code>, the denominators of the partial mappings have been chosen to be equal and the numerators have been chosen to be numbers coprime to the common denominator, whose product is just a little bit smaller than the <code class="code">Modulus(f6)</code>th power of the denominator. In the example we have 5 * 7 * 11^3 = 46585 and 6^6 = 46656.</p>
<p>Although the trajectories of <code class="code">T</code> are much shorter than those of <code class="code">f6</code>, it seems likely that this does not make the problem of deciding whether the mapping <code class="code">T</code> is contracting essentially easier -- even for mappings with much shorter trajectories than <code class="code">T</code> the problem seems to be equally hard. A solution can usually only be found in trivial cases, i.e. for example when there is some k such that applying the kth power of the respective mapping to any integer decreases its absolute value.</p>
<p><a id="X84A915BA833E0BDE" name="X84A915BA833E0BDE"></a></p>
<h4>5.3 <span class="Heading">Checking a result by P. Andaloro</span></h4>
<p>In <a href="chapBib.html#biBAndaloro00">[And00]</a>, P. Andaloro has shown that proving that trajectories of integers n in 1(16) under the Collatz mapping always contain 1 would be sufficient to prove the 3n+1 Conjecture. In the sequel, this result is verified by <strong class="pkg">RCWA</strong>. Checking that the union of the images of the residue class 1(16) under powers of the Collatz mapping T contains Z \ 0(3) is obviously enough. Thus we put S := 1(16), and successively unite the set S with its image under T:</p>
<table class="example">
<tr><td><pre>
gap> S := ResidueClass(Integers,16,1);
1(16)
gap> S := Union(S,S^T);
1(16) U 2(24)
gap> S := Union(S,S^T);
1(12) U 2(24) U 17(48) U 33(48)
gap> S := Union(S,S^T);
<union of 30 residue classes (mod 144)>
gap> S := Union(S,S^T);
<union of 42 residue classes (mod 144)>
gap> S := Union(S,S^T);
<union of 172 residue classes (mod 432)>
gap> S := Union(S,S^T);
<union of 676 residue classes (mod 1296)>
gap> S := Union(S,S^T);
<union of 810 residue classes (mod 1296)>
gap> S := Union(S,S^T);
<union of 2638 residue classes (mod 3888)>
gap> S := Union(S,S^T);
<union of 33 residue classes (mod 48)>
gap> S := Union(S,S^T);
<union of 33 residue classes (mod 48)>
gap> Union(S,ResidueClass(Integers,3,0)); # Et voila ...
Integers
</pre></td></tr></table>
<p>Further similar computations are shown in Section <a href="chap5.html#X855A3CD88459958B"><b>5.13</b></a>.</p>
<p><a id="X7E8CD9B67ED78735" name="X7E8CD9B67ED78735"></a></p>
<h4>5.4 <span class="Heading">Two examples by Matthews and Leigh</span></h4>
<p>In <a href="chapBib.html#biBMatthewsLeigh87">[ML87]</a>, K. R. Matthews and G. M. Leigh have shown that two trajectories of the following (surjective, but not injective) mappings are acyclic (mod x) and divergent:</p>
<table class="example">
<tr><td><pre>
gap> x := Indeterminate(GF(4),1);; SetName(x,"x");
gap> R := PolynomialRing(GF(2),1);
GF(2)[x]
gap> ML1 := RcwaMapping(R,x,[[1,0,x],[(x+1)^3,1,x]]*One(R));;
gap> ML2 := RcwaMapping(R,x,[[1,0,x],[(x+1)^2,1,x]]*One(R));;
gap> SetName(ML1,"ML1"); SetName(ML2,"ML2");
gap> Display(ML1);
Rcwa mapping of GF(2)[x] with modulus x
P mod x | P^ML1
------------------------+------------------------------------------------
0*Z(2) | P/x
Z(2)^0 | ((x^3+x^2+x+Z(2)^0)*P + Z(2)^0)/x
gap> Display(ML2);
Rcwa mapping of GF(2)[x] with modulus x
P mod x | P^ML2
------------------------+------------------------------------------------
0*Z(2) | P/x
Z(2)^0 | ((x^2+Z(2)^0)*P + Z(2)^0)/x
gap> List([ML1,ML2],IsSurjective);
[ true, true ]
gap> List([ML1,ML2],IsInjective);
[ false, false ]
gap> traj1 := Trajectory(ML1,One(R),16);
[ Z(2)^0, x^2+x+Z(2)^0, x^4+x^2+x, x^3+x+Z(2)^0, x^5+x^4+x^2, x^4+x^3+x,
x^3+x^2+Z(2)^0, x^5+x^2+Z(2)^0, x^7+x^6+x^5+x^3+Z(2)^0,
x^9+x^7+x^6+x^5+x^3+x+Z(2)^0, x^11+x^10+x^8+x^7+x^6+x^5+x^2,
x^10+x^9+x^7+x^6+x^5+x^4+x, x^9+x^8+x^6+x^5+x^4+x^3+Z(2)^0,
x^11+x^8+x^7+x^6+x^4+x+Z(2)^0, x^13+x^12+x^11+x^8+x^7+x^6+x^4,
x^12+x^11+x^10+x^7+x^6+x^5+x^3 ]
gap> traj2 := Trajectory(ML2,(x^3+x+1)*One(R),16);
[ x^3+x+Z(2)^0, x^4+x+Z(2)^0, x^5+x^3+x^2+x+Z(2)^0, x^6+x^3+Z(2)^0,
x^7+x^5+x^4+x^2+x, x^6+x^4+x^3+x+Z(2)^0, x^7+x^4+x^3+x+Z(2)^0,
x^8+x^6+x^5+x^4+x^3+x+Z(2)^0, x^9+x^6+x^3+x+Z(2)^0,
x^10+x^8+x^7+x^5+x^4+x+Z(2)^0, x^11+x^8+x^7+x^5+x^4+x^3+x^2+x+Z(2)^0,
x^12+x^10+x^9+x^8+x^7+x^5+Z(2)^0, x^13+x^10+x^7+x^4+x,
x^12+x^9+x^6+x^3+Z(2)^0, x^13+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x,
x^12+x^10+x^9+x^7+x^6+x^4+x^3+x+Z(2)^0 ]
</pre></td></tr></table>
<p>The pattern which Matthews and Leigh used to show the divergence of the above trajectories can be recognized easily by looking at the corresponding Markov chains with the two states 0 mod x and 1 mod x:</p>
<table class="example">
<tr><td><pre>
gap> traj1modx := Trajectory(ML1,One(R),400,x);;
gap> traj2modx := Trajectory(ML2,(x^3+x+1)*One(R),600,x);;
gap> List(traj1modx{[1..150]},val->Position([Zero(R),One(R)],val)-1);
[ 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1,
1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
gap> List(traj2modx{[1..150]},val->Position([Zero(R),One(R)],val)-1);
[ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
</pre></td></tr></table>
<p>What is important here are the lengths of the intervals between two changes from one state to the other:</p>
<table class="example">
<tr><td><pre>
gap> ChangePoints := l->Filtered([1..Length(l)-1],pos->l[pos]<>l[pos+1]);;
gap> Diffs := l->List([1..Length(l)-1],pos->l[pos+1]-l[pos]);;
gap> Diffs(ChangePoints(traj1modx)); # The pattern in the first ...
[ 1, 1, 2, 4, 2, 2, 4, 8, 4, 4, 8, 16, 8, 8, 16, 32, 16, 16, 32, 64, 32,
32, 64 ]
gap> Diffs(ChangePoints(traj2modx)); # ... and in the second example.
[ 1, 7, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 49, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 97, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 193, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
gap> Diffs(ChangePoints(last)); # Make this a bit more obvious.
[ 1, 3, 1, 7, 1, 15, 1, 31, 1, 63, 1 ]
</pre></td></tr></table>
<p>This looks clearly acyclic, thus the trajectories diverge. Needless to say however that this computational evidence does not replace the proof along these lines given in the article cited above, but just sheds a light on the idea behind it.</p>
<p><a id="X7A8F55CA87A16900" name="X7A8F55CA87A16900"></a></p>
<h4>5.5 <span class="Heading">Exploring the structure of a wild rcwa group</span></h4>
<p>In this example, a simple attempt to should be made to investigate the structure of a given wild group by finding orders of torsion elements. In general, determining the structure of a given wild group seems to be a very hard task. First of all, the group in question has to be defined:</p>
<table class="example">
<tr><td><pre>
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> SetName(u,"u");
gap> Display(u);
Rcwa mapping of Z with modulus 5
n mod 5 | n^u
------------------------------------+------------------------------------
0 | 3n/5
1 | (9n + 1)/5
2 | (3n - 1)/5
3 | (9n - 2)/5
4 | (9n + 4)/5
gap> nu := ClassShift(0,1);;
gap> G := Group(u,nu);
<rcwa group over Z with 2 generators>
gap> IsTame(G);
false
</pre></td></tr></table>
<p>Now we would like to know which orders torsion elements of <code class="code">G</code> can have -- taking a look at the above generators it seems to make sense to try commutators:</p>
<table class="example">
<tr><td><pre>
gap> l := Filtered([0..100],k->IsTame(Comm(u,nu^k)));
[ 0, 2, 3, 5, 6, 9, 10, 12, 13, 15, 17, 18, 20, 21, 24, 25, 27, 28, 30,
32, 33, 35, 36, 39, 40, 42, 43, 45, 47, 48, 50, 51, 54, 55, 57, 58,
60, 62, 63, 65, 66, 69, 70, 72, 73, 75, 77, 78, 80, 81, 84, 85, 87,
88, 90, 92, 93, 95, 96, 99, 100 ]
gap> List(l,k->Order(Comm(u,nu^k)));
[ 1, 6, 5, 3, 5, 5, 3, infinity, 7, infinity, 7, 5, 3, infinity,
infinity, 3, 5, 7, infinity, 7, infinity, 3, 5, 5, 3, 5, infinity,
infinity, infinity, 5, 3, 5, 5, 3, infinity, 7, infinity, 7, 5, 3,
infinity, infinity, 3, 5, 7, infinity, 7, infinity, 3, 5, 5, 3, 5,
infinity, infinity, infinity, 5, 3, 5, 5, 3 ]
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> Display(Comm(u,nu^13));
Bijective rcwa mapping of Z with modulus 9
n mod 9 | n^f
------------------------------------+------------------------------------
0 3 6 | n + 5
1 4 7 | 3n - 9
2 8 | n - 11
5 | (n + 16)/3
gap> Order(Comm(u,nu^13));
7
gap> u2 := u^2;
<wild bijective rcwa mapping of Z with modulus 25>
gap> Filtered([1..16],k->IsTame(Comm(u2,nu^k))); # k < 15 -> commutator wild!
[ 15 ]
gap> Order(Comm(u2,nu^15));
infinity
gap> u2nu17 := Comm(u2,nu^17);
<bijective rcwa mapping of Z with modulus 81>
gap> cycs := ShortCycles(u2nu17,[-100..100],100);;
gap> List(cycs,Length);
[ 72, 72, 73, 72, 73, 72, 72, 73, 72, 72, 72, 73, 72, 72, 73, 72, 72,
73, 72, 72, 73, 72, 72 ]
gap> Lcm(last);
5256
gap> u2nu17^5256; # This element has indeed order 2^3*3^2*73 = 5256.
IdentityMapping( Integers )
gap> u2nu18 := Comm(u2,nu^18);
<bijective rcwa mapping of Z with modulus 81>
gap> cycs := ShortCycles(u2nu18,[-100..100],100);;
gap> List(cycs,Length);
[ 22, 22, 22, 21, 22, 22, 22, 21, 21, 22, 22, 21, 22, 21, 22, 22, 21,
22, 22, 21, 22, 22, 21 ]
gap> Lcm(last);
462
gap> u2nu18^462; # This is an element of order 2*3*7*11 = 462.
IdentityMapping( Integers )
gap> Order(Comm(u2,nu^20));
29
gap> Order(Comm(u2,nu^25));
9
gap> Order(Comm(u2,nu^30));
15
</pre></td></tr></table>
<p>Thus even this rather simple-minded approach reveals various different orders of torsion elements, and the involved primes are also not all very "small".</p>
<p><a id="X7D0928AE839F1C49" name="X7D0928AE839F1C49"></a></p>
<h4>5.6 <span class="Heading">A wild rcwa mapping which has only finite cycles</span></h4>
<p>Some wild rcwa mappings of Z have only finite cycles. In this section, a permutation is examined which can be shown to be such a mapping and which is likely to be something like a "minimal" example.</p>
<p>Over R = GF(q)[x], the degree function gives rise to a partition of R into finite sets which is left invariant by suitable wild rcwa mappings. Over R = Z the situation looks different -- there is no such "natural" partition into finite sets which can be fixed by a wild rcwa mapping.</p>
<table class="example">
<tr><td><pre>
gap> kappa := RcwaMapping([[1,0,1],[1,0,1],[3,2,2],[1,-1,1],
> [2,0,1],[1,0,1],[3,2,2],[1,-1,1],
> [1,1,3],[1,0,1],[3,2,2],[2,-2,1]]);;
gap> SetName(kappa,"kappa");
gap> List([-5..5],k->Modulus(kappa^k));
[ 7776, 1296, 432, 72, 24, 1, 12, 72, 144, 864, 1728 ]
gap> Display(kappa);
Bijective rcwa mapping of Z with modulus 12
n mod 12 | n^kappa
------------------------------------+------------------------------------
0 1 5 9 | n
2 6 10 | (3n + 2)/2
3 7 | n - 1
4 | 2n
8 | (n + 1)/3
11 | 2n - 2
gap> List([-32..32],n->Length(Cycle(kappa,n)));
[ 4, 1, 4, 4, 7, 1, 10, 10, 1, 1, 4, 4, 7, 1, 10, 10, 4, 1, 7, 7, 1, 1,
7, 7, 4, 1, 4, 4, 2, 1, 1, 2, 1, 1, 4, 4, 4, 1, 7, 7, 4, 1, 7, 7, 1,
1, 10, 10, 7, 1, 4, 4, 7, 1, 10, 10, 1, 1, 4, 4, 4, 1, 13, 13, 7 ]
gap> List([2..14],k->Maximum(List([1..2^k],n->Length(Cycle(kappa,n)))));
[ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40 ]
gap> List([2..14],k->Length(Cycle(kappa,2^k-2)));
[ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40 ]
gap> Cycle(kappa,2^12-2);
[ 4094, 6142, 9214, 13822, 20734, 31102, 46654, 69982, 104974, 157462,
236194, 354292, 708584, 236195, 472388, 157463, 314924, 104975,
209948, 69983, 139964, 46655, 93308, 31103, 62204, 20735, 41468,
13823, 27644, 9215, 18428, 6143, 12284, 4095 ]
gap> last mod 12;
[ 2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 4, 8, 11, 8, 11, 8, 11, 8,
11, 8, 11, 8, 11, 8, 11, 8, 11, 8, 11, 8, 11, 8, 3 ]
gap> lengthstats := Collected(List(ShortCycles(kappa,[1..12^4],100),
> Length));
[ [ 1, 6912 ], [ 4, 1728 ], [ 7, 864 ], [ 10, 432 ], [ 13, 216 ],
[ 16, 108 ], [ 19, 54 ], [ 22, 27 ], [ 25, 13 ], [ 28, 7 ], [ 31, 3 ],
[ 34, 2 ], [ 37, 1 ], [ 40, 1 ] ]
</pre></td></tr></table>
<p>We would like to determine a partition of Z into unions of cycles of equal length:</p>
<table class="example">
<tr><td><pre>
gap> C := [Difference(Integers,MovedPoints(kappa))];; pow := [kappa^0];;
gap> rc := function(r,m) return ResidueClass(r,m); end;;
gap> for i in [1..3] do
> Add(pow,kappa^i);
> C[i+1] := Difference(rc(2,4),
> Union(Union(C{[1..i]}),
> Union(List([0..i],j->Intersection(
> rc(2,4)^pow[j+1],
> rc(2,4)^(pow[i-j+1]^-1))))));
> od;
gap> C;
[ 1(4) U 0(12) U [ -2 ], 2(24) U 18(24), 6(48) U 38(48) U 10(72) U 58(72)
, <union of 38 residue classes (mod 864)> ]
gap> List(C,S->Length(Cycle(kappa,S)));
[ 1, 4, 7, 10 ]
gap> Cycle(kappa,C[1]);
[ 1(4) U 0(12) U [ -2 ] ]
gap> Cycle(kappa,C[2]);
[ 2(24) U 18(24), 4(36) U 28(36), 8(72) U 56(72), 3(24) U 19(24) ]
gap> cycle7 := Cycle(kappa,C[3]);;
gap> for S in cycle7 do View(S); Print("\n"); od;
6(48) U 38(48) U 10(72) U 58(72)
10(72) U 58(72) U 16(108) U 88(108)
16(108) U 88(108) U 32(216) U 176(216)
11(72) U 59(72) U 32(216) U 176(216)
11(72) U 59(72) U 20(144) U 116(144)
7(48) U 39(48) U 20(144) U 116(144)
6(48) U 7(48) U 38(48) U 39(48)
gap> cycle10 := Cycle(kappa,C[4]);;
gap> for S in cycle10 do View(S); Print("\n"); od;
<union of 38 residue classes (mod 864)>
<union of 38 residue classes (mod 1296)>
<union of 12 residue classes (mod 648)>
<union of 12 residue classes (mod 648)>
<union of 22 residue classes (mod 1296)>
<union of 12 residue classes (mod 432)>
<union of 22 residue classes (mod 864)>
<union of 12 residue classes (mod 288)>
<union of 14 residue classes (mod 288)>
<union of 16 residue classes (mod 288)>
gap> List(cycle10,Density);
[ 19/432, 19/648, 1/54, 1/54, 11/648, 1/36, 11/432, 1/24, 7/144, 1/18 ]
gap> List(last,Float);
[ 0.0439815, 0.029321, 0.0185185, 0.0185185, 0.0169753, 0.0277778,
0.025463, 0.0416667, 0.0486111, 0.0555556 ]
gap> Sum(last2);
47/144
gap> Density(Union(cycle10));
47/432
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> P := List(C,S->Union(Cycle(kappa,S)));;
gap> for S in P do View(S); Print("\n"); od;
1(4) U 0(12) U [ -2 ]
<union of 18 residue classes (mod 72)>
<union of 78 residue classes (mod 432)>
<union of 282 residue classes (mod 2592)>
gap> P2 := AsUnionOfFewClasses(P[2]);
[ 2(24), 3(24), 18(24), 19(24), 4(36), 28(36), 8(72), 56(72) ]
gap> Permutation(kappa,P2);
(1,5,7,2)(3,6,8,4)
gap> P3 := AsUnionOfFewClasses(P[3]);
[ 6(48), 7(48), 38(48), 39(48), 10(72), 11(72), 58(72), 59(72), 16(108),
88(108), 20(144), 116(144), 32(216), 176(216) ]
gap> Permutation(kappa,P3);
(1,5,9,13,6,11,2)(3,7,10,14,8,12,4)
gap> P4 := AsUnionOfFewClasses(P[4]);
[ 14(96), 15(96), 78(96), 79(96), 22(144), 23(144), 118(144), 119(144),
34(216), 35(216), 178(216), 179(216), 44(288), 236(288), 52(324),
268(324), 68(432), 356(432), 104(648), 536(648) ]
gap> Permutation(kappa,P4);
(1,5,9,15,19,10,17,6,13,2)(3,7,11,16,20,12,18,8,14,4)
gap> List(P,S->Set(List(Intersection([1..12^4],S),n->Length(Cycle(kappa,n)))));
[ [ 1 ], [ 4 ], [ 7 ], [ 10 ] ]
gap> Set(List(Intersection([1..12^4],Difference(Integers,Union(P))),
> n->Length(Cycle(kappa,n))));
[ 13, 16, 19, 22, 25, 28, 31, 34, 37, 40 ]
</pre></td></tr></table>
<p>Finally, the permutation <code class="code">kappa</code> should be factored into involutions (this time "by hand", for purposes of illustration):</p>
<table class="example">
<tr><td><pre>
gap> elm1 := kappa;
kappa
gap> Multpk(elm1,2,1)^elm1;
8(12)
gap> Multpk(elm1,2,-1)^elm1;
4(6)
gap> fact1 := ClassTransposition(4,6,8,12);;
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> elm2 := elm1/fact1;
<bijective rcwa mapping of Z with modulus 12>
gap> Display(elm2);
Bijective rcwa mapping of Z with modulus 12
n mod 12 | n^f
------------------------------------+------------------------------------
0 1 4 5 9 | n
2 6 10 | 3n + 2
3 7 11 | n - 1
8 | (n + 1)/3
gap> Multpk(elm2,3,1)^elm2;
8(12)
gap> Multpk(elm2,3,-1)^elm2;
3(4)
gap> fact2 := ClassTransposition(3,4,8,12);;
gap> elm3 := elm2/fact2;
<bijective rcwa mapping of Z with modulus 4>
gap> Display(elm3);
Bijective rcwa mapping of Z with modulus 4
n mod 4 | n^f
------------------------------------+------------------------------------
0 1 | n
2 | n + 1
3 | n - 1
gap> fact3 := ClassTransposition(2,4,3,4);;
gap> elm4 := elm3/fact3;
IdentityMapping( Integers )
gap> kappafacts := [ fact3, fact2, fact1 ];
[ ClassTransposition(2,4,3,4), ClassTransposition(3,4,8,12),
ClassTransposition(4,6,8,12) ]
gap> kappa = Product(kappafacts);
true
</pre></td></tr></table>
<p><a id="X7A8605E680F664BF" name="X7A8605E680F664BF"></a></p>
<h4>5.7 <span class="Heading">An abelian rcwa group over a polynomial ring</span></h4>
<p>In this section, a wild rcwa group over GF(4)[x] should be invstigated, which happens to be abelian. Of course in general, rcwa groups also over this ring are usually far from being abelian (see below). We start by defining this group:</p>
<table class="example">
<tr><td><pre>
gap> x := Indeterminate(GF(4),1);; SetName(x,"x");
gap> R := PolynomialRing(GF(4),1);
GF(2^2)[x]
gap> e := One(GF(4));;
gap> p := x^2 + x + e;; q := x^2 + e;;
gap> r := x^2 + x + Z(4);; s := x^2 + x + Z(4)^2;;
gap> cg := List( AllResidues(R,x^2), pol -> [ p, p * pol mod q, q ] );;
gap> ch := List( AllResidues(R,x^2), pol -> [ r, r * pol mod s, s ] );;
gap> g := RcwaMapping( R, q, cg );
<rcwa mapping of GF(2^2)[x] with modulus x^2+Z(2)^0>
gap> h := RcwaMapping( R, s, ch );
<rcwa mapping of GF(2^2)[x] with modulus x^2+x+Z(2^2)^2>
gap> List([g,h],Order);
[ infinity, infinity ]
gap> List([g,h],IsTame);
[ false, false ]
gap> G := Group(g,h);
<rcwa group over GF(2^2)[x] with 2 generators>
gap> IsAbelian(G);
true
</pre></td></tr></table>
<p>Now we compute the action of the group <code class="code">G</code> on one of its orbits, and make some statistics of the orbits of <code class="code">G</code> containing polynomials of degree less than 4:</p>
<table class="example">
<tr><td><pre>
gap> orb := Orbit(G,x^5);
[ x^5, x^5+x^4+x^2+Z(2)^0, x^5+x^3+x^2+Z(2^2)*x+Z(2)^0, x^5+x^3,
x^5+x^4+x^3+x^2+Z(2^2)^2*x+Z(2^2)^2, x^5+x, x^5+x^4+x^3,
x^5+x^2+Z(2^2)^2*x, x^5+x^4+x^2+x, x^5+x^3+x^2+Z(2^2)^2*x+Z(2)^0,
x^5+x^4+Z(2^2)*x+Z(2^2), x^5+x^3+x, x^5+x^4+x^3+x^2+Z(2^2)*x+Z(2^2),
x^5+x^4+x^3+x+Z(2)^0, x^5+x^2+Z(2^2)*x, x^5+x^4+Z(2^2)^2*x+Z(2^2)^2 ]
gap> H := Action(G,orb);
Group([ (1,2,4,7,6,9,12,14)(3,5,8,11,10,13,15,16),
(1,3,6,10)(2,5,9,13)(4,8,12,15)(7,11,14,16) ])
gap> IsAbelian(H); # check ...
true
gap> Exponent(H);
8
gap> Collected(List(ShortOrbits(G,AllResidues(R,x^4),100),Length));
[ [ 1, 4 ], [ 2, 6 ], [ 4, 12 ], [ 8, 24 ] ]
</pre></td></tr></table>
<p>Changing the generators a little causes the group structure to change a lot:</p>
<table class="example">
<tr><td><pre>
gap> cg[1][2] := cg[1][2] + (x^2 + e) * p * q;;
gap> ch[7][2] := ch[7][2] + x * r * s;;
gap> g := RcwaMapping( R, q, cg );; h := RcwaMapping( R, s, ch );;
gap> G := Group(g,h);
<rcwa group over GF(2^2)[x] with 2 generators>
gap> orb := Orbit(G,Zero(R));;
gap> Length(orb);
87
gap> Collected(List(orb,DegreeOfLaurentPolynomial));
[ [ 1, 2 ], [ 2, 4 ], [ 3, 16 ], [ 4, 64 ], [ infinity, 1 ] ]
gap> H := Action(G,orb);
<permutation group with 2 generators>
gap> IsNaturalAlternatingGroup(H);
true
gap> orb := Orbit(G,x^6);;
gap> Length(orb);
512
gap> H := Action(G,orb);
<permutation group with 2 generators>
gap> IsNaturalSymmetricGroup(H) or IsNaturalAlternatingGroup(H);
false
gap> blk := Blocks(H,[1..512]);;
gap> List(blk,Length);
[ 128, 128, 128, 128 ]
gap> Action(H,blk,OnSets);
Group([ (1,2)(3,4), (1,3)(2,4) ])
</pre></td></tr></table>
<p>Thus the modified group has a quotient isomorphic to the alternating group of degree 87, and a quotient isomorphic to some wreath product or a subgroup thereof acting transitively, but not primitively on 512 points.</p>
<p><a id="X87383623856ED81B" name="X87383623856ED81B"></a></p>
<h4>5.8 <span class="Heading">
A tame group generated by commutators of wild permutations
</span></h4>
<p>In this section, we have a look at 3 wild rcwa mappings whose commutators generate tame groups:</p>
<table class="example">
<tr><td><pre>
gap> a := RcwaMapping([[3,0,2],[3, 1,4],[3,0,2],[3,-1,4]]);;
gap> b := RcwaMapping([[3,0,2],[3,13,4],[3,0,2],[3,-1,4]]);;
gap> c := RcwaMapping([[3,0,2],[3, 1,4],[3,0,2],[3,11,4]]);;
gap> SetName(a,"a"); SetName(b,"b"); SetName(c,"c");
gap> List([a,b,c],IsTame);
[ false, false, false ]
gap> ab := Comm(a,b);; ac := Comm(a,c);; bc := Comm(b,c);;
gap> SetName(ab,"[a,b]"); SetName(ac,"[a,c]"); SetName(bc,"[b,c]");
gap> List([ab,ac,bc],Order);
[ 6, 6, 12 ]
</pre></td></tr></table>
<p>Now we would like to have a look at [<var class="Arg">a</var>,<var class="Arg">b</var>] ...</p>
<table class="example">
<tr><td><pre>
gap> Display(ab);
Bijective rcwa mapping of Z with modulus 18, of order 6
n mod 18 | n^[a,b]
------------------------------------+------------------------------------
0 2 3 8 9 11 12 17 | n
1 10 | 2n - 5
4 7 13 16 | n + 3
5 14 | 2n - 4
6 | (n + 2)/2
15 | (n - 5)/2
</pre></td></tr></table>
<p>... form the group generated by [<var class="Arg">a</var>,<var class="Arg">b</var>] and [<var class="Arg">a</var>,<var class="Arg">c</var>] and compute its action on one of its orbits:</p>
<table class="example">
<tr><td><pre>
gap> G := Group(ab,ac);
<rcwa group over Z with 2 generators>
gap> orb := Orbit(G,1);
[ -15, -12, -7, -6, -5, -4, -3, -2, -1, 1 ]
gap> H := Action(G,orb);
Group([ (2,5,8,10,7,6), (1,3,6,9,4,5) ])
gap> Size(H);
3628800
gap> Size(G); # G acts faithfully on orb.
3628800
</pre></td></tr></table>
<p>Hence the group <var class="Arg">G</var> is isomorphic to the symmetric group on 10 points and acts faithfully on the orbit containing 1. Another question is which groups arise if we take as generators either <var class="Arg">ab</var>, <var class="Arg">ac</var> or <var class="Arg">bc</var> and the involution which maps any integer to its additive inverse:</p>
<table class="example">
<tr><td><pre>
gap> t := ClassReflection(0,1);;
gap> Display(t);
Bijective rcwa mapping of Z: n -> -n
gap> G := Group(ab,t);
<rcwa group over Z with 2 generators>
gap> Size(G);
7257600
gap> phi := IsomorphismPermGroup(G);
[ [a,b], ClassReflection(0,1) ] ->
[ (1,36,12,27,9,15)(2,34,10,25,7,13)(3,35,11,26,8,14),
(1,18)(2,17)(3,16)(4,15)(5,14)(6,13)(7,12)(8,11)(9,10)(20,21)(22,
36)(23,35)(24,34)(25,33)(26,32)(27,31)(28,30) ]
gap> StructureDescription(Image(phi));
"C2 x S10"
</pre></td></tr></table>
<p>Thus the group generated by <var class="Arg">ab</var> and <var class="Arg">t</var> is isomorphic to C_2 x S_10. The next group is an extension of a perfect group of order 960:</p>
<table class="example">
<tr><td><pre>
gap> G := Group(ac,t);;
gap> Size(G);
3840
gap> H := Image(IsomorphismPermGroup(G));;
gap> P := DerivedSubgroup(H);;
gap> Size(P);
960
gap> IsPerfect(P);
true
gap> PerfectGroup(PerfectIdentification(P));
A5 2^4'
</pre></td></tr></table>
<p>The last group is infinite:</p>
<table class="example">
<tr><td><pre>
gap> G := Group(bc,t);;
gap> Size(G);
infinity
gap> Order(bc*t);
infinity
gap> Modulus(G);
18
gap> RespectedPartition(G);
[ 1(9), 2(9), 4(9), 5(9), 7(9), 8(9), 0(18), 3(18), 6(18), 9(18),
12(18), 15(18) ]
gap> ActionOnRespectedPartition(G);
Group([ (1,5,8,2,4,12)(3,9,6,11), (1,6)(2,5)(3,4)(8,12)(9,11) ])
gap> StructureDescription(last);
"S10"
gap> RankOfKernelOfActionOnRespectedPartition(G);
9
</pre></td></tr></table>
<p><a id="X78DFE4B4821E07A6" name="X78DFE4B4821E07A6"></a></p>
<h4>5.9 <span class="Heading">Checking for solvability</span></h4>
<p>Is the group generated by the permutations <var class="Arg">a</var> and <var class="Arg">b</var> from the last paragraph solvable?</p>
<p>This group is wild. Presently there is no general method available for testing wild rcwa groups for solvability. But nevertheless, for the given group we can obtain a negative answer to this question. The idea is to find a subgroup <var class="Arg">U</var> which acts on a finite set <var class="Arg">S</var> of integers, and which induces on <var class="Arg">S</var> a non-solvable finite permutation group:</p>
<table class="example">
<tr><td><pre>
gap> a := RcwaMapping([[3,0,2],[3, 1,4],[3,0,2],[3,-1,4]]);; SetName(a,"a");
gap> b := RcwaMapping([[3,0,2],[3,13,4],[3,0,2],[3,-1,4]]);; SetName(b,"b");
gap> G := Group(a,b);;
gap> ShortOrbits(Group(Comm(a,b)),[-10..10],100);
[ [ -10 ], [ -9 ], [ -30, -21, -14, -13, -11, -8 ], [ -7 ], [ -6 ],
[ -12, -5, -4, -3, -2, 1 ], [ -1 ], [ 0 ], [ 2 ], [ 3 ],
[ 4, 5, 6, 7, 10, 15 ], [ 8 ], [ 9 ] ]
gap> S := [ 4, 5, 6, 7, 10, 15 ];;
gap> Cycle(Comm(a,b),4);
[ 4, 7, 10, 15, 5, 6 ]
gap> elm := RepresentativeAction(G,S,Permuted(S,(1,4)),OnTuples);
<bijective rcwa mapping of Z with modulus 81>
gap> List(S,n->n^elm);
[ 7, 5, 6, 4, 10, 15 ]
gap> U := Group(Comm(a,b),elm);
<rcwa group over Z with 2 generators>
gap> Action(U,S);
Group([ (1,4,5,6,2,3), (1,4) ])
gap> IsNaturalSymmetricGroup(last);
true
</pre></td></tr></table>
<p>Thus the subgroup <var class="Arg">U</var> induces on <var class="Arg">S</var> a natural symmetric group of degree 6. Therefore the group <var class="Arg">G</var> is not solvable, as claimed. We conclude this example by factoring the group element <var class="Arg">elm</var> into generators:</p>
<table class="example">
<tr><td><pre>
gap> F := FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> RepresentativeActionPreImage(G,S,Permuted(S,(1,4)),OnTuples,F);
a^-2*b^-2*a*b*a^-1*b*a*b^-2*a
gap> a^-2*b^-2*a*b*a^-1*b*a*b^-2*a = elm;
true
</pre></td></tr></table>
<p><a id="X783D54DC7A646273" name="X783D54DC7A646273"></a></p>
<h4>5.10 <span class="Heading">Some examples over (semi)localizations of the integers</span></h4>
<p>We start with something one can observe when trying to "transfer" an rcwa mapping from the ring of integers to one of its localizations:</p>
<table class="example">
<tr><td><pre>
gap> a2 := LocalizedRcwaMapping(a,2);
<rcwa mapping of Z_( 2 ) with modulus 4>
gap> IsSurjective(a2); # As expected
true
gap> IsInjective(a2); # Why not??
false
gap> 0^a2;
0
gap> (1/3)^a2; # That's the reason!
0
</pre></td></tr></table>
<p>The above can also be explained easily by pointing out that the modulus of the inverse of <code class="code">a</code> is 3, and that 3 is a unit of Z_(2). Moving to Z_(2,3) solves this problem:</p>
<table class="example">
<tr><td><pre>
gap> a23 := SemilocalizedRcwaMapping(a,[2,3]);
<rcwa mapping of Z_( 2, 3 ) with modulus 4>
gap> IsBijective(a23);
true
</pre></td></tr></table>
<p>We get additional finite cycles, e.g.:</p>
<table class="example">
<tr><td><pre>
gap> List(ShortOrbits(Group(a23),[0..50]/5,50),orb->Cycle(a23,orb[1]));
[ [ 0 ], [ 1/5, 2/5, 3/5 ],
[ 4/5, 6/5, 9/5, 8/5, 12/5, 18/5, 27/5, 19/5, 13/5, 11/5, 7/5 ],
[ 1 ], [ 2, 3 ], [ 14/5, 21/5, 17/5 ],
[ 16/5, 24/5, 36/5, 54/5, 81/5, 62/5, 93/5, 71/5, 52/5, 78/5, 117/5,
89/5, 68/5, 102/5, 153/5, 116/5, 174/5, 261/5, 197/5, 149/5,
113/5, 86/5, 129/5, 98/5, 147/5, 109/5, 83/5, 61/5, 47/5, 34/5,
51/5, 37/5, 29/5, 23/5 ], [ 4, 6, 9, 7, 5 ] ]
gap> List(last,Length);
[ 1, 3, 11, 1, 2, 3, 34, 5 ]
gap> List(ShortOrbits(Group(a23),[0..50]/7,50),orb->Cycle(a23,orb[1]));
[ [ 0 ], [ -1/7, 1/7 ], [ 2/7, 3/7, 4/7, 6/7, 9/7, 5/7 ], [ 1 ],
[ 2, 3 ], [ 4, 6, 9, 7, 5 ] ]
gap> List(last,Length);
[ 1, 2, 6, 1, 2, 5 ]
</pre></td></tr></table>
<p>But the group structure remains invariant under the "transfer" of a group with prime set 2,3 from Z to Z_(2,3):</p>
<table class="example">
<tr><td><pre>
gap> b23 := SemilocalizedRcwaMapping(b,[2,3]);;
gap> c23 := SemilocalizedRcwaMapping(c,[2,3]);;
gap> ab23 := Comm(a23,b23);
<rcwa mapping of Z_( 2, 3 ) with modulus 18>
gap> ac23 := Comm(a23,c23);
<rcwa mapping of Z_( 2, 3 ) with modulus 18>
gap> G := Group(ab23,ac23);
<rcwa group over Z_( 2, 3 ) with 2 generators>
gap> S := Intersection(Enumerator(Rationals){[1..128]},Z_pi([2,3]));
[ -10, -9, -8, -7, -6, -5, -4, -3, -2, -9/5, -8/5, -10/7, -7/5, -9/7,
-6/5, -8/7, -1, -6/7, -4/5, -5/7, -3/5, -4/7, -3/7, -2/5, -2/7, -1/5,
-1/7, 0, 1/11, 1/7, 1/5, 2/7, 2/5, 3/7, 4/7, 3/5, 5/7, 4/5, 6/7, 1,
8/7, 6/5, 9/7, 7/5, 10/7, 8/5, 9/5, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
gap> orbs := ShortOrbits(G,S,50);;
gap> List(orbs,Length);
[ 10, 1, 10, 1, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10,
10, 1, 1, 10, 1 ]
gap> ForAll(orbs,orb->IsNaturalSymmetricGroup(Action(G,orb)));
true
</pre></td></tr></table>
<p>"Transferring" a non-invertible rcwa mapping from the ring of integers to some of its (semi)localizations can also turn it into an invertible one:</p>
<table class="example">
<tr><td><pre>
gap> v := RcwaMapping([[6,0,1],[1,-7,2],[6,0,1],[1,-1,1],
> [6,0,1],[1, 1,2],[6,0,1],[1,-1,1]]);;
gap> SetName(v,"v");
gap> Display(v);
Rcwa mapping of Z with modulus 8
n mod 8 | n^v
------------------------------------+------------------------------------
0 2 4 6 | 6n
1 | (n - 7)/2
3 7 | n - 1
5 | (n + 1)/2
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> IsInjective(v);
true
gap> IsSurjective(v);
false
gap> Image(v);
Z \ 4(12) U 8(12)
gap> Difference(Integers,last);
4(12) U 8(12)
gap> v2 := LocalizedRcwaMapping(v,2);
<rcwa mapping of Z_( 2 ) with modulus 8>
gap> IsBijective(v2);
true
gap> Display(v2^-1);
Bijective rcwa mapping of Z_( 2 ) with modulus 4
n mod 4 | n^f
------------------------------------+------------------------------------
0 | 1/3 n / 2
1 | 2 n + 7
2 | n + 1
3 | 2 n - 1
gap> S := ResidueClass(Z_pi(2),2,0);; l := [S];;
gap> for i in [1..10] do Add(l,l[Length(l)]^v2); od;
gap> l; # Visibly v2 is wild ...
[ 0(2), 0(4), 0(8), 0(16), 0(32), 0(64), 0(128), 0(256), 0(512),
0(1024), 0(2048) ]
gap> w2 := RcwaMapping(Z_pi(2),[[1,0,2],[2,-1,1],[1,1,1],[2,-1,1]]);;
gap> v2w2 := Comm(v2,w2);; SetName(v2w2,"[v2,w2]"); v2w2^-1;;
gap> Display(v2w2);
Bijective rcwa mapping of Z_( 2 ) with modulus 8
n mod 8 | n^[v2,w2]
------------------------------------+------------------------------------
0 3 4 7 | n
1 | n + 4
2 6 | 3 n
5 | n - 4
</pre></td></tr></table>
<p>Again, viewed as an rcwa mapping of the integers the commutator given at the end of the example would not be surjective.</p>
<p><a id="X846D7D087861E0AC" name="X846D7D087861E0AC"></a></p>
<h4>5.11 <span class="Heading">
Twisting 257-cycles into an rcwa mapping with modulus 32
</span></h4>
<p>We define an rcwa mapping <var class="Arg">x</var> of order 257 with modulus 32. The easiest way to construct such a mapping is to prescribe a transition graph and then to assign suitable affine mappings to its vertices.</p>
<table class="example">
<tr><td><pre>
gap> x := RcwaMapping(
> [[ 16, 2, 1], [ 16, 18, 1], [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1], [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1], [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 16, 1], [ 16, 18, 1], [ 1, 16, 1], [ 16, 18, 1],
> [ 1, 0, 16], [ 16, 18, 1], [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1], [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1], [ 1,-14, 1], [ 16, 18, 1],
> [ 1,-14, 1], [ 16, 18, 1], [ 1,-14, 1], [ 1,-31, 1]]);;
gap> SetName(x,"x"); Order(x);; Display(x);
Bijective rcwa mapping of Z with modulus 32, of order 257
n mod 32 | n^x
------------------------------------+------------------------------------
0 | 16n + 2
1 3 5 7 9 11 13 15 17 19 21 |
23 25 27 29 | 16n + 18
2 4 6 8 10 12 14 | n + 16
16 | n/16
18 20 22 24 26 28 30 | n - 14
31 | n - 31
gap> Cycle(x,[1],0);
[ 0, 2, 18, 4, 20, 6, 22, 8, 24, 10, 26, 12, 28, 14, 30, 16, 1, 34, 50,
36, 52, 38, 54, 40, 56, 42, 58, 44, 60, 46, 62, 48, 3, 66, 82, 68, 84,
70, 86, 72, 88, 74, 90, 76, 92, 78, 94, 80, 5, 98, 114, 100, 116, 102,
118, 104, 120, 106, 122, 108, 124, 110, 126, 112, 7, 130, 146, 132,
148, 134, 150, 136, 152, 138, 154, 140, 156, 142, 158, 144, 9, 162,
178, 164, 180, 166, 182, 168, 184, 170, 186, 172, 188, 174, 190, 176,
11, 194, 210, 196, 212, 198, 214, 200, 216, 202, 218, 204, 220, 206,
222, 208, 13, 226, 242, 228, 244, 230, 246, 232, 248, 234, 250, 236,
252, 238, 254, 240, 15, 258, 274, 260, 276, 262, 278, 264, 280, 266,
282, 268, 284, 270, 286, 272, 17, 290, 306, 292, 308, 294, 310, 296,
312, 298, 314, 300, 316, 302, 318, 304, 19, 322, 338, 324, 340, 326,
342, 328, 344, 330, 346, 332, 348, 334, 350, 336, 21, 354, 370, 356,
372, 358, 374, 360, 376, 362, 378, 364, 380, 366, 382, 368, 23, 386,
402, 388, 404, 390, 406, 392, 408, 394, 410, 396, 412, 398, 414, 400,
25, 418, 434, 420, 436, 422, 438, 424, 440, 426, 442, 428, 444, 430,
446, 432, 27, 450, 466, 452, 468, 454, 470, 456, 472, 458, 474, 460,
476, 462, 478, 464, 29, 482, 498, 484, 500, 486, 502, 488, 504, 490,
506, 492, 508, 494, 510, 496, 31 ]
gap> Length(last);
257
</pre></td></tr></table>
<p><a id="X78D5DC93845CA6A0" name="X78D5DC93845CA6A0"></a></p>
<h4>5.12 <span class="Heading"> The behaviour of the moduli of powers </span></h4>
<p>In this section some examples are given, which illustrate how different the series of the moduli of powers of a given rcwa mapping of the integers can look like.</p>
<table class="example">
<tr><td><pre>
gap> List([0..4],i->Modulus(a^i));
[ 1, 4, 16, 64, 256 ]
gap> List([0..6],i->Modulus(ab^i));
[ 1, 18, 18, 18, 18, 18, 1 ]
gap> g:=RcwaMapping([[2,2,1],[1, 4,1],[1,0,2],[2,2,1],[1,-4,1],[1,-2,1]]);;
gap> h:=RcwaMapping([[2,2,1],[1,-2,1],[1,0,2],[2,2,1],[1,-1,1],[1, 1,1]]);;
gap> List([0..7],i->Modulus(g^i));
[ 1, 6, 12, 12, 12, 12, 6, 1 ]
gap> List([1..18],i->Modulus((g^3*h)^i));
[ 12, 6, 12, 12, 12, 6, 12, 6, 12, 12, 12, 6, 12, 6, 12, 12, 12, 6 ]
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> List([0..3],i->Modulus(u^i));
[ 1, 5, 25, 125 ]
gap> v6 := RcwaMapping([[-1,2,1],[1,-1,1],[1,-1,1]]);;
gap> List([0..6],i->Modulus(v6^i));
[ 1, 3, 3, 3, 3, 3, 1 ]
gap> w8 := RcwaMapping([[-1,3,1],[1,-1,1],[1,-1,1],[1,-1,1]]);;
gap> List([0..8],i->Modulus(w8^i));
[ 1, 4, 4, 4, 4, 4, 4, 4, 1 ]
gap> z := RcwaMapping([[2, 1, 1],[1, 1,1],[2, -1,1],[2, -2,1],
> [1, 6, 2],[1, 1,1],[1, -6,2],[2, 5,1],
> [1, 6, 2],[1, 1,1],[1, 1,1],[2, -5,1],
> [1, 0, 1],[1, -4,1],[1, 0,1],[2,-10,1]]);;
gap> SetName(z,"z");
gap> IsBijective(z);
true
gap> Display(z);
Bijective rcwa mapping of Z with modulus 16
n mod 16 | n^z
------------------------------------+------------------------------------
0 | 2n + 1
1 5 9 10 | n + 1
2 | 2n - 1
3 | 2n - 2
4 8 | (n + 6)/2
6 | (n - 6)/2
7 | 2n + 5
11 | 2n - 5
12 14 | n
13 | n - 4
15 | 2n - 10
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> List([0..25],i->Modulus(z^i));
[ 1, 16, 32, 64, 64, 128, 128, 128, 128, 128, 128, 256, 256, 256, 256,
256, 256, 512, 512, 512, 512, 512, 512, 1024, 1024, 1024 ]
gap> e1 := RcwaMapping([[1,4,1],[2,0,1],[1,0,2],[2,0,1]]);;
gap> e2 := RcwaMapping([[1,4,1],[2,0,1],[1,0,2],[1,0,1],
> [1,4,1],[2,0,1],[1,0,1],[1,0,1]]);;
gap> List([e1,e2],Order);
[ infinity, infinity ]
gap> List([1..20],i->Modulus(e1^i));
[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]
gap> List([1..20],i->Modulus(e2^i));
[ 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4 ]
gap> SetName(e1,"e1"); SetName(e2,"e2"); Display(e2);
Bijective rcwa mapping of Z with modulus 8, of order infinity
n mod 8 | n^e2
------------------------------------+------------------------------------
0 4 | n + 4
1 5 | 2n
2 | n/2
3 6 7 | n
gap> e2^2 = Restriction(RcwaMapping([[1,2,1]]),RcwaMapping([[4,0,1]]));
true
</pre></td></tr></table>
<p><a id="X855A3CD88459958B" name="X855A3CD88459958B"></a></p>
<h4>5.13 <span class="Heading"> Images and preimages under the Collatz mapping </span></h4>
<p>We have a look at the images of the residue class 1(2) under powers of the Collatz mapping.</p>
<table class="example">
<tr><td><pre>
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);;
gap> S0 := ResidueClass(Integers,2,1);;
gap> S1 := S0^T;
2(3)
gap> S2 := S1^T;
1(3) U 8(9)
gap> S3 := S2^T;
2(3) U 4(9)
gap> S4 := S3^T;
Z \ 0(3) U 5(9)
gap> S5 := S4^T;
Z \ 0(3) U 7(9)
gap> S6 := S5^T;
Z \ 0(3)
gap> S7 := S6^T;
Z \ 0(3)
</pre></td></tr></table>
<p>Thus the image gets stable after applying the mapping T for the 6th time. Hence T^6 maps the residue class 1(2) surjectively onto the union of the residue classes 1(3) and 2(3), which T stabilizes setwise. Now we would like to determine the preimages of 1(3) and 2(3) in 1(2) under T^6. The residue class 1(2) has to be the disjoint union of these sets.</p>
<table class="example">
<tr><td><pre>
gap> U := Intersection(PreImage(T^6,ResidueClass(Integers,3,1)),S0);
<union of 11 residue classes (mod 64)>
gap> V := Intersection(PreImage(T^6,ResidueClass(Integers,3,2)),S0);
<union of 21 residue classes (mod 64)>
gap> AsUnionOfFewClasses(U);
[ 1(64), 5(64), 7(64), 9(64), 21(64), 23(64), 29(64), 31(64), 49(64),
51(64), 59(64) ]
gap> AsUnionOfFewClasses(V);
[ 3(32), 11(32), 13(32), 15(32), 25(32), 17(64), 19(64), 27(64), 33(64),
37(64), 39(64), 41(64), 53(64), 55(64), 61(64), 63(64) ]
gap> Union(U,V) = S0 and Intersection(U,V) = []; # consistency check
true
</pre></td></tr></table>
<p>The images of the residue class 0(3) under powers of T look as follows:</p>
<table class="example">
<tr><td><pre>
gap> S0 := ResidueClass(Integers,3,0);
0(3)
gap> S1 := S0^T;
0(3) U 5(9)
gap> S2 := S1^T;
0(3) U 5(9) U 7(9) U 8(27)
gap> S3 := S2^T;
<union of 20 residue classes (mod 27)>
gap> S4 := S3^T;
<union of 73 residue classes (mod 81)>
gap> S5 := S4^T;
Z \ 10(81) U 37(81)
gap> S6 := S5^T;
Integers
gap> S7 := S6^T;
Integers
</pre></td></tr></table>
<p>Thus every integer is the image of a multiple of 3 under T^6. This means that it would be sufficient to prove the 3n+1 Conjecture for multiples of 3. We can obtain the corresponding result for multiples of 5 as follows:</p>
<table class="example">
<tr><td><pre>
gap> S := [ResidueClass(Integers,5,0)];
[ 0(5) ]
gap> for i in [1..12] do Add(S,S[i]^T); od;
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> for s in S do View(s); Print("\n"); od;
0(5)
0(5) U 8(15)
0(5) U 4(15) U 8(15)
0(5) U 2(15) U 4(15) U 8(15) U 29(45)
<union of 73 residue classes (mod 135)>
<union of 244 residue classes (mod 405)>
<union of 784 residue classes (mod 1215)>
<union of 824 residue classes (mod 1215)>
<union of 2593 residue classes (mod 3645)>
<union of 2647 residue classes (mod 3645)>
<union of 2665 residue classes (mod 3645)>
<union of 2671 residue classes (mod 3645)>
1(3) U 2(3) U 0(15)
gap> Union(S[13],ResidueClass(Integers,3,0));
Integers
gap> List(S,Si->Float(Density(Si)));
[ 0.2, 0.266667, 0.333333, 0.422222, 0.540741, 0.602469, 0.645267,
0.678189, 0.711385, 0.7262, 0.731139, 0.732785, 0.733333 ]
</pre></td></tr></table>
<p><a id="X7968C1DF7EF0BD8E" name="X7968C1DF7EF0BD8E"></a></p>
<h4>5.14 <span class="Heading">
A group which acts 4-transitively on the positive integers
</span></h4>
<p>In this section, we would like to show that the group G generated by the two wild mappings</p>
<table class="example">
<tr><td><pre>
gap> a := RcwaMapping([[3,0,2],[3,1,4],[3,0,2],[3,-1,4]]);;
gap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);;
gap> SetName(a,"a"); SetName(u,"u"); G := Group(a,u);;
</pre></td></tr></table>
<p>which we have already investigated in earlier examples acts 4-transitively on the set of positive integers. Obviously, it acts on the set of positive integers. First we show that this action is transitive. We start by checking in which residue classes sufficiently large positive integers are mapped to smaller ones by a suitable group element:</p>
<table class="example">
<tr><td><pre>
gap> List([a,a^-1,u,u^-1],DecreasingOn);
[ 1(2), 0(3), 0(5) U 2(5), 2(3) ]
gap> Union(last);
Z \ 4(30) U 16(30) U 28(30)
</pre></td></tr></table>
<p>We see that we cannot always choose such a group element from the set of generators and their inverses -- otherwise the union would be <code class="code">Integers</code>.</p>
<table class="example">
<tr><td><pre>
gap> List([a,a^-1,u,u^-1,a^2,a^-2,u^2,u^-2],DecreasingOn);
[ 1(2), 0(3), 0(5) U 2(5), 2(3), 1(8) U 7(8), 0(3) U 2(9) U 7(9),
0(25) U 12(25) U 17(25) U 20(25), 2(3) U 1(9) U 3(9) ]
gap> Union(last); # Still not enough ...
Z \ 4(90) U 58(90) U 76(90)
gap> List([a,a^-1,u,u^-1,a^2,a^-2,u^2,u^-2,a*u,u*a,(a*u)^-1,(u*a)^-1],
> DecreasingOn);
[ 1(2), 0(3), 0(5) U 2(5), 2(3), 1(8) U 7(8), 0(3) U 2(9) U 7(9),
0(25) U 12(25) U 17(25) U 20(25), 2(3) U 1(9) U 3(9),
3(5) U 0(10) U 7(20) U 9(20), 0(5) U 2(5), 2(3), 3(9) U 4(9) U 8(9) ]
gap> Union(last); # ... but that's it!
Integers
</pre></td></tr></table>
<p>Finally, we have to deal with "small" integers. We use the notation for the coefficients of rcwa mappings introduced at the beginning of this manual. Let c_r(m) > a_r(m). Then we easily see that (a_r(m)n+b_r(m))/c_r(m) > n implies n < b_r(m)/(c_r(m)-a_r(m)). Thus we can restrict our considerations to integers n < b_rm max, where b_rm max is the largest second entry of a coefficient triple of one of the group elements in our list:</p>
<table class="example">
<tr><td><pre>
gap> List([a,a^-1,u,u^-1,a^2,a^-2,u^2,u^-2,a*u,u*a,(a*u)^-1,(u*a)^-1],
> f->Maximum(List(Coefficients(f),c->c[2])));
[ 1, 1, 4, 2, 7, 7, 56, 28, 25, 17, 17, 11 ]
gap> Maximum(last);
56
</pre></td></tr></table>
<p>Thus this upper bound is 56. The rest is easy -- all we have to do is to check that the orbit containing 1 contains also all other positive integers less than or equal to 56:</p>
<table class="example">
<tr><td><pre>
gap> S := [1];;
gap> while not IsSubset(S,[1..56]) do
> S := Union(S,S^a,S^u,S^(a^-1),S^(u^-1));
> od;
gap> IsSubset(S,[1..56]);
true
</pre></td></tr></table>
<p>Checking 2-transitivity is computationally harder, and in the sequel we will omit some steps which are in practice needed to find out "what to do". The approach taken here is to show that the stabilizer of 1 in G acts transitively on the set of positive integers greater than 1. We do this by similar means as used above for showing the transitivity of the action of G on the positive integers. We start by determining all products of at most 5 generators and their inverses, which stabilize 1 (taking at most 4-generator products would not suffice!):</p>
<table class="example">
<tr><td><pre>
gap> gens := [a,u,a^-1,u^-1];;
gap> tups := Concatenation(List([1..5],k->Tuples([1..4],k)));;
gap> Length(tups);
1364
gap> tups := Filtered(tups,tup->ForAll([[1,3],[3,1],[2,4],[4,2]],
> l->PositionSublist(tup,l)=fail));;
gap> Length(tups);
484
gap> stab := [];;
gap> for tup in tups do
> n := 1;
> for i in tup do n := n^gens[i]; od;
> if n = 1 then Add(stab,tup); fi;
> od;
gap> Length(stab);
118
gap> stabelm := List(stab,tup->Product(List(tup,i->gens[i])));;
gap> ForAll(stabelm,elm->1^elm=1); # Check.
true
</pre></td></tr></table>
<p>The resulting products have various different not quite small moduli:</p>
<table class="example">
<tr><td><pre>
gap> List(stabelm,Modulus);
[ 4, 3, 16, 25, 9, 81, 64, 100, 108, 100, 25, 75, 27, 243, 324, 243,
256, 400, 144, 400, 100, 432, 324, 400, 80, 400, 625, 25, 75, 135,
150, 75, 225, 81, 729, 486, 729, 144, 144, 81, 729, 1296, 729, 6561,
1024, 1600, 192, 1600, 400, 576, 432, 1600, 320, 1600, 2500, 100, 100,
180, 192, 192, 108, 972, 1728, 972, 8748, 1600, 400, 320, 80, 1600,
2500, 300, 2500, 625, 625, 75, 675, 75, 75, 135, 405, 600, 120, 600,
1875, 75, 225, 405, 225, 225, 675, 243, 2187, 729, 2187, 216, 216,
243, 2187, 1944, 2187, 19683, 576, 144, 576, 432, 81, 81, 729, 2187,
5184, 324, 8748, 243, 2187, 19683, 26244, 19683 ]
gap> Lcm(last);
12597120000
gap> Collected(Factors(last));
[ [ 2, 10 ], [ 3, 9 ], [ 5, 4 ] ]
</pre></td></tr></table>
<p>Similar as before, we determine for any of the above mappings the residue classes whose elements larger than the largest b_r(m) - coefficient of the respective mapping are mapped to smaller integers:</p>
<table class="example">
<tr><td><pre>
gap> decs := List(stabelm,DecreasingOn);;
gap> List(decs,Modulus);
[ 2, 3, 8, 25, 9, 9, 16, 100, 12, 50, 25, 75, 27, 81, 54, 81, 64, 400,
48, 200, 100, 72, 108, 400, 80, 200, 625, 25, 75, 45, 75, 75, 225, 81,
243, 81, 243, 144, 144, 81, 243, 216, 243, 243, 128, 1600, 64, 400,
400, 48, 144, 1600, 320, 400, 2500, 100, 100, 60, 96, 192, 108, 324,
144, 324, 972, 400, 400, 80, 80, 400, 2500, 100, 1250, 625, 625, 25,
75, 75, 75, 45, 135, 600, 120, 150, 1875, 75, 225, 135, 225, 225, 675,
243, 729, 243, 729, 108, 216, 243, 729, 162, 729, 2187, 144, 144, 144,
144, 81, 81, 243, 729, 1296, 324, 972, 243, 729, 2187, 1458, 2187 ]
gap> Lcm(last);
174960000
</pre></td></tr></table>
<p>Since the least common multiple of the moduli of these unions of residue classes is as large as 174960000, directly forming their union and checking whether it is equal to the set of integers would take relatively much time and memory. However, starting with the set of integers and subtracting the above sets one-by-one in a suitably chosen order is cheap:</p>
<table class="example">
<tr><td><pre>
gap> SortParallel(decs,stabelm,
> function(S1,S2)
> return First([1..100],k->Factorial(k) mod Modulus(S1)=0)
> < First([1..100],k->Factorial(k) mod Modulus(S2)=0);
> end);
gap> S := Integers;;
gap> for i in [1..Length(decs)] do
> S_old := S; S := Difference(S,decs[i]);
> if S <> S_old then ViewObj(S); Print("\n"); fi;
> if S = [] then maxind := i; break; fi;
> od;
0(2)
2(6) U 4(6)
<union of 8 residue classes (mod 30)>
<union of 19 residue classes (mod 90)>
<union of 114 residue classes (mod 720)>
<union of 99 residue classes (mod 720)>
<union of 57 residue classes (mod 720)>
<union of 54 residue classes (mod 720)>
<union of 41 residue classes (mod 720)>
<union of 35 residue classes (mod 720)>
<union of 8 residue classes (mod 720)>
4(720) U 94(720) U 148(720) U 238(720)
<union of 24 residue classes (mod 5760)>
<union of 72 residue classes (mod 51840)>
<union of 48 residue classes (mod 51840)>
<union of 192 residue classes (mod 259200)>
<union of 168 residue classes (mod 259200)>
<union of 120 residue classes (mod 259200)>
<union of 96 residue classes (mod 259200)>
<union of 72 residue classes (mod 259200)>
<union of 60 residue classes (mod 259200)>
<union of 48 residue classes (mod 259200)>
<union of 24 residue classes (mod 259200)>
<union of 12 residue classes (mod 259200)>
<union of 24 residue classes (mod 777600)>
<union of 12 residue classes (mod 777600)>
111604(194400) U 14404(777600) U 208804(777600)
[ ]
</pre></td></tr></table>
<p>Similar as above, it remains to check that the "small" integers all lie in the orbit containing 2. Obviously, it is sufficient to check that any integer greater than 2 is mapped to a smaller one by some suitably chosen element of the stabilizer under consideration:</p>
<table class="example">
<tr><td><pre>
gap> Maximum(List(stabelm{[1..maxind]},
> f->Maximum(List(Coefficients(f),c->c[2]))));
6581
gap> Filtered([3..6581],n->Minimum(List(stabelm,elm->n^elm))>=n);
[ 4 ]
</pre></td></tr></table>
<p>We have to treat 4 separately:</p>
<table class="example">
<tr><td><pre>
gap> 1^(u*a*u^2*a^-1*u);
1
gap> 4^(u*a*u^2*a^-1*u);
3
</pre></td></tr></table>
<p>Now we know that any positive integer greater than 1 lies in the same orbit under the action of the stabilizer of 1 in G as 2, thus that this stabilizer acts transitively on N \ 1. But this means that we have established the 2-transitivity of the action of G on N.</p>
<p>In the following, we essentially repeat the above steps to show that this action is indeed 3-transitive:</p>
<table class="example">
<tr><td><pre>
gap> tups := Concatenation(List([1..6],k->Tuples([1..4],k)));;
gap> tups := Filtered(tups,tup->ForAll([[1,3],[3,1],[2,4],[4,2]],
> l->PositionSublist(tup,l)=fail));;
gap> stab := [];;
gap> for tup in tups do
> l := [1,2];
> for i in tup do l := List(l,n->n^gens[i]); od;
> if l = [1,2] then Add(stab,tup); fi;
> od;
gap> Length(stab);
212
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> stabelm := List(stab,tup->Product(List(tup,i->gens[i])));;
gap> decs := List(stabelm,DecreasingOn);;
gap> SortParallel(decs,stabelm,function(S1,S2)
> return First([1..100],k->Factorial(k) mod Mod(S1)=0)
> < First([1..100],k->Factorial(k) mod Mod(S2)=0); end);
gap> S := Integers;;
gap> for i in [1..Length(decs)] do
> S_old := S; S := Difference(S,decs[i]);
> if S <> S_old then ViewObj(S); Print("\n"); fi;
> if S = [] then break; fi;
> od;
Z \ 1(8) U 7(8)
<union of 151 residue classes (mod 240)>
<union of 208 residue classes (mod 720)>
<union of 51 residue classes (mod 720)>
<union of 45 residue classes (mod 720)>
<union of 39 residue classes (mod 720)>
<union of 33 residue classes (mod 720)>
<union of 23 residue classes (mod 720)>
<union of 19 residue classes (mod 720)>
<union of 17 residue classes (mod 720)>
<union of 16 residue classes (mod 720)>
<union of 14 residue classes (mod 720)>
<union of 8 residue classes (mod 720)>
<union of 7 residue classes (mod 720)>
238(360) U 4(720) U 148(720) U 454(720)
<union of 38 residue classes (mod 5760)>
<union of 37 residue classes (mod 5760)>
<union of 25 residue classes (mod 5760)>
<union of 21 residue classes (mod 5760)>
<union of 17 residue classes (mod 5760)>
<union of 16 residue classes (mod 5760)>
<union of 138 residue classes (mod 51840)>
<union of 48 residue classes (mod 51840)>
<union of 32 residue classes (mod 51840)>
<union of 20 residue classes (mod 51840)>
<union of 16 residue classes (mod 51840)>
<union of 68 residue classes (mod 259200)>
<union of 42 residue classes (mod 259200)>
<union of 32 residue classes (mod 259200)>
<union of 26 residue classes (mod 259200)>
<union of 25 residue classes (mod 259200)>
<union of 11 residue classes (mod 259200)>
<union of 10 residue classes (mod 259200)>
<union of 7 residue classes (mod 259200)>
13414(129600) U 2164(259200) U 66964(259200) U 228964(259200)
2164(259200) U 66964(259200) U 228964(259200)
[ ]
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> Maximum(List(stabelm,f->Maximum(List(Coefficients(f),c->c[2]))));
515816
gap> smallnum := [4..515816];;
gap> for i in [1..Length(stabelm)] do
> smallnum := Filtered(smallnum,n->n^stabelm[i]>=n);
> od;
gap> smallnum;
[ ]
</pre></td></tr></table>
<p>The same for 4-transitivity:</p>
<table class="example">
<tr><td><pre>
gap> tups := Concatenation(List([1..8],k->Tuples([1..4],k)));;
gap> tups := Filtered(tups,tup->ForAll([[1,3],[3,1],[2,4],[4,2]],
> l->PositionSublist(tup,l)=fail));;
gap> stab := [];;
gap> for tup in tups do
> l := [1,2,3];
> for i in tup do l := List(l,n->n^gens[i]); od;
> if l = [1,2,3] then Add(stab,tup); fi;
> od;
gap> Length(stab);
528
gap> stabelm := [];;
gap> for i in [1..Length(stab)] do
> elm := One(G);
> for j in stab[i] do
> if Modulus(elm) > 10000 then elm := fail; break; fi;
> elm := elm * gens[j];
> od;
> if elm <> fail then Add(stabelm,elm); fi;
> od;
gap> Length(stabelm);
334
gap> decs := List(stabelm,DecreasingOn);;
gap> SortParallel(decs,stabelm,
> function(S1,S2)
> return First([1..100],k->Factorial(k) mod Modulus(S1) = 0)
> < First([1..100],k->Factorial(k) mod Modulus(S2) = 0);
> end);
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> S := Integers;;
gap> for i in [1..Length(decs)] do
> S_old := S; S := Difference(S,decs[i]);
> if S <> S_old then ViewObj(S); Print("\n"); fi;
> if S = [] then maxind := i; break; fi;
> od;
Z \ 1(8) U 7(8)
<union of 46 residue classes (mod 72)>
<union of 20 residue classes (mod 72)>
4(18)
<union of 28 residue classes (mod 576)>
<union of 22 residue classes (mod 576)>
<union of 21 residue classes (mod 576)>
40(72) U 4(144) U 94(144) U 346(576) U 418(576)
<union of 16 residue classes (mod 576)>
<union of 15 residue classes (mod 576)>
4(144) U 94(144) U 346(576) U 418(576)
<union of 30 residue classes (mod 5184)>
<union of 26 residue classes (mod 5184)>
<union of 6 residue classes (mod 1296)>
<union of 504 residue classes (mod 129600)>
<union of 324 residue classes (mod 129600)>
<union of 282 residue classes (mod 129600)>
<union of 239 residue classes (mod 129600)>
<union of 218 residue classes (mod 129600)>
<union of 194 residue classes (mod 129600)>
<union of 154 residue classes (mod 129600)>
<union of 97 residue classes (mod 129600)>
<union of 85 residue classes (mod 129600)>
<union of 77 residue classes (mod 129600)>
<union of 67 residue classes (mod 129600)>
<union of 125 residue classes (mod 259200)>
<union of 108 residue classes (mod 259200)>
<union of 107 residue classes (mod 259200)>
<union of 101 residue classes (mod 259200)>
<union of 100 residue classes (mod 259200)>
<union of 84 residue classes (mod 259200)>
<union of 80 residue classes (mod 259200)>
<union of 76 residue classes (mod 259200)>
<union of 70 residue classes (mod 259200)>
<union of 66 residue classes (mod 259200)>
<union of 54 residue classes (mod 259200)>
<union of 53 residue classes (mod 259200)>
<union of 47 residue classes (mod 259200)>
<union of 43 residue classes (mod 259200)>
<union of 31 residue classes (mod 259200)>
<union of 24 residue classes (mod 259200)>
<union of 23 residue classes (mod 259200)>
<union of 13 residue classes (mod 259200)>
57406(129600) U 115006(129600) U 192676(259200) U 250276(259200)
57406(129600) U 192676(259200) U 250276(259200) U 374206(388800)
57406(129600) U 192676(259200) U 250276(259200)
250276(259200) U 57406(388800) U 316606(388800) U 451876(777600)
316606(388800) U 451876(777600) U 509476(777600) U 768676(777600)
<union of 18 residue classes (mod 3110400)>
451876(777600) U 509476(777600) U 705406(777600) U 768676(777600) U
2649406(3110400)
451876(777600) U 705406(777600) U 768676(777600) U 2649406(3110400)
451876(777600) U 705406(777600) U 2649406(3110400)
705406(777600) U 2007076(3110400) U 2649406(3110400) U 2784676(3110400)
<union of 14 residue classes (mod 9331200)>
2260606(2332800) U 5759806(9331200) U 5895076(9331200) U 8227876(9331200)
4593406(6998400) U 15091006(27993600) U 17559076(27993600) U 24557476(
27993600)
<union of 14 residue classes (mod 83980800)>
18590206(20995200) U 24557476(83980800) U 45552676(83980800) U 71078206(
83980800)
[ ]
gap> Maximum(List(stabelm{[1..maxind]},
> f->Maximum(List(Coefficients(f),c->c[2]))));
58975
gap> smallnum := [5..58975];;
gap> for i in [1..maxind] do
> smallnum := Filtered(smallnum,n->n^stabelm[i]>=n);
> od;
gap> smallnum;
[ ]
</pre></td></tr></table>
<p>There is even some evidence that the degree of transitivity of the action of G on the positive integers is higher than 4:</p>
<table class="example">
<tr><td><pre>
gap> phi := EpimorphismFromFreeGroup(G);
[ a, u ] -> [ a, u ]
gap> F := Source(phi);
<free group on the generators [ a, u ]>
gap> List([5..20],
> n->RepresentativeActionPreImage(G,[1,2,3,4,5],
> [1,2,3,4,n],OnTuples,F));
[ <identity ...>, a^-3*u^4*a*u^-2*a^2,
a^-2*u*a^-1*u*a^-1*u*a^-1*u*a^-1*u^-1*a, a^4*u^-2*a^-4, a^-1*u^-4*a,
u^2*a^-1*u^2*a^-1*u^-2, u^-2*a^-2*u^4, a^-1*u^2*a, a^-1*u^-6*a,
a^2*u^4*a^2*u^2, u^-4*a*u^-2*a^-3, a^-1*u^-2*a^-3*u^4*a^2,
a^3*u^2*a*u^2, a*u^-4*a*u^-4*a^-2, u^-2*a*u^2*a*u^-2, u^-4*a^2*u^2 ]
</pre></td></tr></table>
<p><a id="X87E7FCE27EACDA38" name="X87E7FCE27EACDA38"></a></p>
<h4>5.15 <span class="Heading">
A group which acts 3-transitively, but not 4-transitively on Z
</span></h4>
<p>In this section, we would like to show that the wild group G generated by the two tame mappings n -> n + 1 and tau_1(2),0(4) acts 3-transitively, but not 4-transitively on the set of integers.</p>
<table class="example">
<tr><td><pre>
gap> G := Group(ClassShift(0,1),ClassTransposition(1,2,0,4));
<rcwa group over Z with 2 generators>
gap> IsTame(G);
false
gap> (G.1^-2*G.2)^3*(G.1^2*G.2)^3; # G <> the free product C_infty * C_2.
IdentityMapping( Integers )
gap> Display(G);
Wild rcwa group over Z, generated by
[
Tame bijective rcwa mapping of Z: n -> n + 1
Bijective rcwa mapping of Z with modulus 4, of order 2
n mod 4 | n^ClassTransposition(1,2,0,4)
------------------------------------+------------------------------------
0 | (n + 2)/2
1 3 | 2n - 2
2 | n
]
</pre></td></tr></table>
<p>This group acts transitively on Z, since already the cyclic group generated by the first of the two generators does so. Next we have to show that it acts 2-transitively. We essentially proceed as in the example in the previous section, by checking that the stabilizer of 0 acts transitively on Z \ 0.</p>
<table class="example">
<tr><td><pre>
gap> gens := [ClassShift(0,1)^-1,ClassTransposition(1,2,0,4),ClassShift(0,1)];;
gap> tups := Concatenation(List([1..6],k->Tuples([-1,0,1],k)));;
gap> tups := Filtered(tups,tup->ForAll([[0,0],[-1,1],[1,-1]],
> l->PositionSublist(tup,l)=fail));;
gap> Length(tups);
189
gap> stab := [];;
gap> for tup in tups do
> n := 0;
> for i in tup do n := n^gens[i+2]; od;
> if n = 0 then Add(stab,tup); fi;
> od;
gap> stabelm := List(stab,tup->Product(List(tup,i->gens[i+2])));;
gap> Collected(List(stabelm,Modulus));
[ [ 4, 6 ], [ 8, 4 ], [ 16, 3 ] ]
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> decs := List(stabelm,DecreasingOn);
[ 0(4), 3(4), 0(4), 3(4), 2(4), 0(4), 4(8), 2(4), 2(4), 0(4), 1(4),
0(8), 3(8) ]
gap> Union(decs);
Integers
</pre></td></tr></table>
<p>Similar as in the previous section, it remains to check that the integers with "small" absolute value all lie in the orbit containing 1 under the action of the stabilizer of 0:</p>
<table class="example">
<tr><td><pre>
gap> Maximum(List(stabelm,f->Maximum(List(Coefficients(f),c->AbsInt(c[2])))));
21
gap> S := [1];;
gap> for elm in stabelm do S := Union(S,S^elm,S^(elm^-1)); od;
gap> IsSubset(S,Difference([-21..21],[0])); # Not yet ..
false
gap> for elm in stabelm do S := Union(S,S^elm,S^(elm^-1)); od;
gap> IsSubset(S,Difference([-21..21],[0])); # ... but now!
true
</pre></td></tr></table>
<p>Now we have to check for 3-transitivity. Since we cannot find for every residue class an element of the pointwise stabilizer of 0,1 which properly divides its elements, we also have to take additions and subtractions into consideration. Since the moduli of all of our stabilizer elements are quite small, simply looking at sets of representatives is cheap:</p>
<table class="example">
<tr><td><pre>
gap> tups := Concatenation(List([1..10],k->Tuples([-1,0,1],k)));;
gap> tups := Filtered(tups,tup->ForAll([[0,0],[-1,1],[1,-1]],
> l->PositionSublist(tup,l)=fail));;
gap> Length(tups);
3069
gap> stab := [];;
gap> for tup in tups do
> l := [0,1];
> for i in tup do l := List(l,n->n^gens[i+2]); od;
> if l = [0,1] then Add(stab,tup); fi;
> od;
gap> Length(stab);
10
gap> stabelm := List(stab,tup->Product(List(tup,i->gens[i+2])));;
gap> Maximum(List(stabelm,Modulus));
8
gap> Maximum(List(stabelm,
> f->Maximum(List(Coefficients(f),c->AbsInt(c[2])))));
8
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> decsp := List(stabelm,elm->Filtered([9..16],n->n^elm<n));
[ [ 9, 13 ], [ 10, 12, 14, 16 ], [ 12, 16 ], [ 9, 13 ], [ 12, 16 ],
[ 9, 11, 13, 15 ], [ 9, 11, 13, 15 ], [ 12, 16 ], [ 12, 16 ],
[ 9, 11, 13, 15 ] ]
gap> Union(decsp);
[ 9, 10, 11, 12, 13, 14, 15, 16 ]
gap> decsm := List(stabelm,elm->Filtered([-16..-9],n->n^elm>n));
[ [ -15, -13, -11, -9 ], [ -16, -12 ], [ -16, -12 ], [ -15, -11 ],
[ -16, -14, -12, -10 ], [ -15, -11 ], [ -15, -11 ],
[ -16, -14, -12, -10 ], [ -16, -14, -12, -10 ], [ -15, -11 ] ]
gap> Union(decsm);
[ -16, -15, -14, -13, -12, -11, -10, -9 ]
gap> S := [2];;
gap> for elm in stabelm do S := Union(S,S^elm,S^(elm^-1)); od;
gap> IsSubset(S,Difference([-8..8],[0,1]));
true
</pre></td></tr></table>
<p>At this point we have established 3-transitivity. It remains to check that the group G does not act 4-transitively. We do this by checking that it is not transitive on 4-tuples (mod 4). Since n mod 8 determines the image of n under a generator of G (mod 4), it suffices to compute (mod 8):</p>
<table class="example">
<tr><td><pre>
gap> orb := [[0,1,2,3]];;
gap> extend := function ()
> local gen;
> for gen in gens do
> orb := Union(orb,List(orb,l->List(l,n->n^gen) mod 8));
> od;
> end;;
gap> repeat
> old := ShallowCopy(orb);
> extend(); Print(Length(orb),"\n");
> until orb = old;
7
27
97
279
573
916
1185
1313
1341
1344
1344
gap> Length(Set(List(orb,l->l mod 4)));
120
gap> last < 4^4;
true
</pre></td></tr></table>
<p>This shows that G acts not 4-transitively on Z. The corresponding calculation for 3-tuples looks as follows:</p>
<table class="example">
<tr><td><pre>
gap> orb := [[0,1,2]];;
gap> repeat
> old := ShallowCopy(orb);
> extend(); Print(Length(orb),"\n");
> until orb = old;
7
27
84
207
363
459
503
512
512
gap> Length(Set(List(orb,l->l mod 4)));
64
gap> last = 4^3;
true
</pre></td></tr></table>
<p>Needless to say that the latter kind of argumentation is not suitable for proving, but only for disproving k-transitivity.</p>
<p><a id="X85DD5E9C7878CAE3" name="X85DD5E9C7878CAE3"></a></p>
<h4>5.16 <span class="Heading">
Grigorchuk groups
</span></h4>
<p>In this section, we show how to construct finite quotients of the two infinite periodic groups introduced by Rostislav Grigorchuk in <a href="chapBib.html#biBGrigorchuk80">[Gri80]</a> with the help of <strong class="pkg">RCWA</strong>. The first of these, nowadays known as "Grigorchuk group", is investigated in an example given on the <strong class="pkg">GAP</strong> website -- see <span class="URL"><a href="http://www.gap-system.org/Doc/Examples/grigorchuk.html">http://www.gap-system.org/Doc/Examples/grigorchuk.html</a></span>. The <strong class="pkg">RCWA</strong> package permits a simpler and more elegant construction of the finite quotients of this group: The function <code class="code">TopElement</code> given on the mentioned webpage gets unnecessary, and the function <code class="code">SequenceElement</code> can be simplified as follows:</p>
<table class="example">
<tr><td><pre>
SequenceElement := function ( r, level )
return Permutation(Product(Filtered([1..level-1],k->k mod 3 <> r),
k->ClassTransposition( 2^(k-1)-1,2^(k+1),
2^k+2^(k-1)-1,2^(k+1))),
[0..2^level-1]);
end;
</pre></td></tr></table>
<p>The actual constructors for the generators are modified as follows:</p>
<table class="example">
<tr><td><pre>
a := level -> Permutation(ClassTransposition(0,2,1,2),[0..2^level-1]);
b := level -> SequenceElement(0,level);
c := level -> SequenceElement(2,level);
d := level -> SequenceElement(1,level);
</pre></td></tr></table>
<p>All computations given on the webpage can now be done just as with the "original" construction of the quotients of the Grigorchuk group. In the sequel, we construct finite quotients of the second group introduced in <a href="chapBib.html#biBGrigorchuk80">[Gri80]</a>:</p>
<table class="example">
<tr><td><pre>
gap> FourCycle := RcwaMapping((4,5,6,7),[4..7]);
<bijective rcwa mapping of Z with modulus 4, of order 4>
gap> GrigorchukGroup2Generator := function ( level )
> if level = 1 then return FourCycle; else
> return Restriction(FourCycle, RcwaMapping([[4,1,1]]))
> * Restriction(FourCycle, RcwaMapping([[4,3,1]]))
> * Restriction(GrigorchukGroup2Generator(level-1),
> RcwaMapping([[4,0,1]]));
> fi;
> end;;
gap> GrigorchukGroup2 := level -> Group(FourCycle,
> GrigorchukGroup2Generator(level));;
</pre></td></tr></table>
<p>We can do similar things as shown in the example on the <strong class="pkg">GAP</strong> webpage for the "first" Grigorchuk group:</p>
<table class="example">
<tr><td><pre>
gap> G := List([1..4],lev->GrigorchukGroup2(lev)); # The first 4 quotients.
[ <rcwa group over Z with 2 generators>,
<rcwa group over Z with 2 generators>,
<rcwa group over Z with 2 generators>,
<rcwa group over Z with 2 generators> ]
gap> H := List([1..4],lev->Action(G[lev],[0..4^lev-1])); # Isom. perm.-gps.
[ Group([ (1,2,3,4), (1,2,3,4) ]),
Group([ (1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16),
(1,5,9,13)(2,6,10,14)(4,8,12,16) ]),
<permutation group with 2 generators>,
<permutation group with 2 generators> ]
gap> List(H,Size);
[ 4, 1024, 4294967296, 1329227995784915872903807060280344576 ]
gap> List(last,n->Collected(Factors(n)));
[ [ [ 2, 2 ] ], [ [ 2, 10 ] ], [ [ 2, 32 ] ], [ [ 2, 120 ] ] ]
gap> List(H,NilpotencyClassOfGroup);
[ 1, 6, 14, 40 ]
</pre></td></tr></table>
<p><a id="X7DD9502F80364631" name="X7DD9502F80364631"></a></p>
<h4>5.17 <span class="Heading">
Forward orbits of a monoid with 2 generators
</span></h4>
<p>The 3n+1 Conjecture asserts that the forward orbit of any positive integer under the Collatz mapping T contains 1. In contrast, it seems likely that "most" trajectories of the two mappings</p>
<p><center> <img src = "t5pm.png" width = "372" height = "61" alt = "T5+/-: Z -> Z, n |-> (n/2 if n even, (5n+/-1)/2 if n odd)" /> </center></p>
<p>diverge. However we can show by means of computation that the forward orbit of any positive integer under the action of the monoid generated by the two mappings T_5^- and T_5^+ indeed contains 1. First of all, we enter the generators:</p>
<table class="example">
<tr><td><pre>
gap> T5m := RcwaMapping([[1,0,2],[5,-1,2]]);;
gap> T5p := RcwaMapping([[1,0,2],[5, 1,2]]);;
</pre></td></tr></table>
<p>We look for a number k such that for any residue class r(2^k) there is a product f of k mappings T_5^pm whose restriction to r(2^k) is given by n -> (an+b)/c where c>a:</p>
<table class="example">
<tr><td><pre>
gap> k := 1;;
gap> repeat
> maps := List(Tuples([T5m,T5p],k),Product);
> decr := List(maps,DecreasingOn);
> decreasable := Union(decr);
> Print(k,": "); View(decreasable); Print("\n");
> k := k + 1;
> until decreasable = Integers;
1: 0(2)
2: 0(4)
3: Z \ 1(8) U 7(8)
4: 0(4) U 3(16) U 6(16) U 10(16) U 13(16)
5: Z \ 7(32) U 25(32)
6: <union of 48 residue classes (mod 64)>
7: Integers
</pre></td></tr></table>
<p>Thus k=7 serves our purposes. To be sure that for any positive integer n our monoid contains a mapping f such that n^f<n, we still need to check this condition for "small" n. Since in case c>a we have (an+b)/c >= n if only if n <= b/(c-a), we only need to check those n which are not larger than the largest coefficient b_r(m) occuring in any of the products under consideration:</p>
<table class="example">
<tr><td><pre>
gap> maxb := Maximum(List(maps,f->Maximum(List(Coefficients(f),t->t[2]))));
25999
gap> small := Filtered([1..maxb],n->ForAll(maps,f->n^f>=n));
[ 1, 7, 9, 11 ]
</pre></td></tr></table>
<p>This means that except of 1, only for n in {7,9,11} there is no product of 7 mappings T_5^pm which maps n to a smaller integer. We check that also the forward orbits of these three integers contain 1 by successively computing preimages of 1:</p>
<table class="example">
<tr><td><pre>
gap> S := [1];; k := 0;;
gap> repeat
> S := Union(S,PreImage(T5m,S),PreImage(T5p,S));
> k := k+1;
> until IsSubset(S,small);
gap> k;
17
</pre></td></tr></table>
<p><a id="X81407BD58648D206" name="X81407BD58648D206"></a></p>
<h4>5.18 <span class="Heading">
Representations of the free group of rank 2
</span></h4>
<p>The free group of rank 2 embeds into RCWA(Z) -- in fact it embeds even in the subgroup which is generated by all class transpositions. An explicit embedding can be constructed by transferring the construction of the so-called "Schottky groups" (cf. <a href="chapBib.html#biBLaHarpe00">[dlH00]</a>, page 27) from PSL(2,C) to RCWA(Z) (we use the notation from the cited book):</p>
<table class="example">
<tr><td><pre>
gap> D := AllResidueClassesModulo(4);
[ 0(4), 1(4), 2(4), 3(4) ]
gap> gamma1 := RepresentativeAction(RCWA(Integers),
> Difference(Integers,D[1]),D[2]);;
gap> gamma2 := RepresentativeAction(RCWA(Integers),
> Difference(Integers,D[3]),D[4]);;
gap> F2 := Group(gamma1,gamma2);
<rcwa group over Z with 2 generators>
</pre></td></tr></table>
<p>We can do some checks:</p>
<table class="example">
<tr><td><pre>
gap> X1 := Union(D{[1,2]});; X2 := Union(D{[3,4]});;
gap> IsSubset(X1,X2^gamma1) and IsSubset(X1,X2^(gamma1^-1))
> and IsSubset(X2,X1^gamma2) and IsSubset(X2,X1^(gamma2^-1));
true
</pre></td></tr></table>
<p>The generators are products of 3 class transpositions, each:</p>
<table class="example">
<tr><td><pre>
gap> Factorization(gamma1);
[ ClassTransposition(0,2,1,2), ClassTransposition(3,4,5,8),
ClassTransposition(0,2,1,8) ]
gap> Factorization(gamma2);
[ ClassTransposition(0,2,1,2), ClassTransposition(1,4,7,8),
ClassTransposition(0,2,3,8) ]
</pre></td></tr></table>
<p>The above construction is used by <code class="func">IsomorphismRcwaGroup</code> (<a href="chap3.html#X7EB8A301790290C7"><b>3.1-3</b></a>) to embed free groups of any rank >= 2.</p>
<p>We give another only slightly different representation of the free group of rank 2. We verify that it really is one by applying the so-called <em>Table-Tennis Lemma</em> (see e.g. <a href="chapBib.html#biBLaHarpe00">[dlH00]</a>, Section II.B.) to the infinite cyclic groups generated by the two generators and to the same two sets <code class="code">X1</code> and <code class="code">X2</code> as above:</p>
<table class="example">
<tr><td><pre>
gap> r1 := ClassTransposition(0,2,1,2)*ClassTransposition(0,2,1,4);;
gap> r2 := ClassTransposition(0,2,1,2)*ClassTransposition(0,2,3,4);;
gap> F2 := Group(r1^2,r2^2);; SetName(F2,"F_2");
gap> List(GeneratorsOfGroup(F2),IsTame);
[ false, false ]
gap> IsSubset(X1,X2^F2.1) and IsSubset(X1,X2^(F2.1^-1))
> and IsSubset(X2,X1^F2.2) and IsSubset(X2,X1^(F2.2^-1));
true
gap> [Sources(r1),Sinks(r1),Loops(r1)]; # compare with X1
[ [ 0(4) ], [ 1(4) ], [ 0(4), 1(4) ] ]
gap> [Sources(r2),Sinks(r2),Loops(r2)]; # compare with X2
[ [ 2(4) ], [ 3(4) ], [ 2(4), 3(4) ] ]
gap> IsSubset(X1,Union(Sinks(r1))) and IsSubset(X1,Union(Sinks(r1^-1)))
> and IsSubset(X2,Union(Sinks(r2))) and IsSubset(X2,Union(Sinks(r2^-1)));
true
gap> IsSubset(Union(Sinks(r1)),X2^F2.1) and
> IsSubset(Union(Sinks(r1^-1)),X2^(F2.1^-1));
true
gap> IsSubset(Union(Sinks(r2)),X1^F2.2) and
> IsSubset(Union(Sinks(r2^-1)),X1^(F2.2^-1));
true
</pre></td></tr></table>
<p>Drawing the transition graphs of <code class="code">r1</code> and <code class="code">r2</code> for modulus 4 may help understanding what is actually done in this calculation. It is easy to see that the group generated by <code class="code">r1</code> and <code class="code">r2</code> is <em>not</em> free:</p>
<table class="example">
<tr><td><pre>
gap> Order(r1/r2);
3
</pre></td></tr></table>
<p><a id="X85B4B4DA83B09E81" name="X85B4B4DA83B09E81"></a></p>
<h4>5.19 <span class="Heading">
Representations of the modular group PSL(2,Z)
</span></h4>
<p>The modular group PSL(2,Z) embeds in the group generated by all class transpositions as well. We give an embedding, and check that it really is one by applying the Table Tennis Lemma as in the previous section:</p>
<table class="example">
<tr><td><pre>
gap> PSL2Z :=
> Group(ClassTransposition(0,3,1,3) * ClassTransposition(0,3,2,3),
> ClassTransposition(1,3,0,6) * ClassTransposition(2,3,3,6));;
gap> List(GeneratorsOfGroup(PSL2Z),Order);
[ 3, 2 ]
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> X1 := Difference(Integers,ResidueClass(0,3));
Z \ 0(3)
gap> X2 := ResidueClass(0,3);
0(3)
gap> IsSubset(X1,X2^PSL2Z.1) and IsSubset(X1,X2^(PSL2Z.1^2));
true
gap> IsSubset(X2,X1^PSL2Z.2);
true
</pre></td></tr></table>
<p>A slightly different representation of PSL(2,Z) can be obtained by using <strong class="pkg">RCWA</strong>'s general method for <code class="code">IsomorphismRcwaGroup</code> for free products of finite groups:</p>
<table class="example">
<tr><td><pre>
gap> Display(Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(3),
> CyclicGroup(2)))));
Wild rcwa group over Z, generated by
[
Bijective rcwa mapping of Z with modulus 4
n mod 4 | n^f
------------------------------------+------------------------------------
0 | n + 2
1 3 | 2n - 2
2 | n/2
Bijective rcwa mapping of Z with modulus 2
n mod 2 | n^f
------------------------------------+------------------------------------
0 | n + 1
1 | n - 1
]
</pre></td></tr></table>
<p> </p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap4.html">Previous Chapter</a> <a href="chap6.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
2439
