5. Examples
  
  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.
  
  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.
  
  The  rcwa  mappings  defined  in this chapter (and in fact many more) can be
  found  in  the  file  pkg/rcwa/examples/examples.g,  so  there is no need to
  extract  them  from the manual files. This file can be read into the current
  GAP session by issueing RCWAReadExamples( );.
  
  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!
  
  
  5.1 Factoring Collatz' permutation of the integers
  
  In  1932, Lothar Collatz mentioned in his notebook the following permutation
  of the integers:
  
  ---------------------------  Example  ----------------------------
    
    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 ] ]
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    gap> Collatz in CT(Integers);  # `Collatz' lies in the simple group CT(Z).
    true
    gap> Length(Factorization(Collatz));
    212
    
  ------------------------------------------------------------------
  
  Setting  the  Info  level of InfoRCWA equal to 2 (simply issue RCWAInfo(2);)
  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.
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    gap> Length(Factorization(Collatz^-1));
    129
    
  ------------------------------------------------------------------
  
  This  is  already  a shorter product, but can still be improved. We remember
  the  mKnot's,  of  which  the  permutation  mKnot(3)  looks  very similar to
  Collatz'  permutation. Therefore it is straightforward to try to factor both
  mKnot(3) and Collatz/mKnot(3), and to look whether the sum of the numbers of
  factors is less than 129:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The   factors   PrimeSwitch(3)   are  products  of  6  class  transpositions
  (cf. PrimeSwitch  (2.5-2)).  At  the  end  of  Section  5.6,  a much smaller
  factorization task is performed "manually" for purposes of illustration.
  
  
  5.2 An rcwa mapping which seems to be contracting, but very slow
  
  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!):
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The  following mapping seems to be contracting as well, but its trajectories
  are much longer:
  
  -----------------------------  Log  ------------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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.
  
  When  constructing  the mapping f6, 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 Modulus(f6)th power of the denominator. In the example
  we have 5 * 7 * 11^3 = 46585 and 6^6 = 46656.
  
  Although  the  trajectories of T are much shorter than those of f6, it seems
  likely that this does not make the problem of deciding whether the mapping T
  is  contracting  essentially  easier  -- even for mappings with much shorter
  trajectories  than T  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.
  
  
  5.3 Checking a result by P. Andaloro
  
  In [And00], 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 RCWA.
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Further similar computations are shown in Section 5.13.
  
  
  5.4 Two examples by Matthews and Leigh
  
  In  [ML87],  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:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  What  is important here are the lengths of the intervals between two changes
  from one state to the other:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  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.
  
  
  5.5 Exploring the structure of a wild rcwa group
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Now  we  would  like  to know which orders torsion elements of G can have --
  taking  a  look  at  the  above  generators  it  seems  to make sense to try
  commutators:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Thus  even  this  rather  simple-minded  approach  reveals various different
  orders  of  torsion  elements, and the involved primes are also not all very
  "small".
  
  
  5.6 A wild rcwa mapping which has only finite cycles
  
  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.
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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 ] ]
    
  ------------------------------------------------------------------
  
  We  would  like to determine a partition of Z into unions of cycles of equal
  length:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  Finally,  the  permutation  kappa  should be factored into involutions (this
  time "by hand", for purposes of illustration):
  
  ---------------------------  Example  ----------------------------
    
    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);;
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.7 An abelian rcwa group over a polynomial ring
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Now we compute the action of the group G on one of its orbits, and make some
  statistics of the orbits of G containing polynomials of degree less than 4:
  
  ---------------------------  Example  ----------------------------
    
    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 ] ]
    
  ------------------------------------------------------------------
  
  Changing the generators a little causes the group structure to change a lot:
  
  ---------------------------  Example  ----------------------------
    
    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) ])
    
  ------------------------------------------------------------------
  
  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.
  
  
  5.8 A tame group generated by commutators of wild permutations
  
  In  this  section,  we have a look at 3 wild rcwa mappings whose commutators
  generate tame groups:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  Now we would like to have a look at [a,b] ...
  
  ---------------------------  Example  ----------------------------
    
    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
    
    
  ------------------------------------------------------------------
  
  ...  form  the  group generated by [a,b] and [a,c] and compute its action on
  one of its orbits:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Hence the group G 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 ab, ac or bc and the involution which maps
  any integer to its additive inverse:
  
  ---------------------------  Example  ----------------------------
    
    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"
    
  ------------------------------------------------------------------
  
  Thus  the  group generated by ab and t is isomorphic to C_2 x S_10. The next
  group is an extension of a perfect group of order 960:
  
  ---------------------------  Example  ----------------------------
    
    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'
    
  ------------------------------------------------------------------
  
  The last group is infinite:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.9 Checking for solvability
  
  Is  the  group generated by the permutations a and b from the last paragraph
  solvable?
  
  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 U  which  acts  on a finite set S of integers, and which induces
  on S a non-solvable finite permutation group:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Thus  the  subgroup  U  induces  on S a natural symmetric group of degree 6.
  Therefore  the group G is not solvable, as claimed. We conclude this example
  by factoring the group element elm into generators:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.10 Some examples over (semi)localizations of the integers
  
  We  start  with  something one can observe when trying to "transfer" an rcwa
  mapping from the ring of integers to one of its localizations:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The  above  can also be explained easily by pointing out that the modulus of
  the  inverse  of  a  is 3,  and that 3 is a unit of Z_(2). Moving to Z_(2,3)
  solves this problem:
  
  ---------------------------  Example  ----------------------------
    
    gap> a23 := SemilocalizedRcwaMapping(a,[2,3]);
    <rcwa mapping of Z_( 2, 3 ) with modulus 4>
    gap> IsBijective(a23);
    true
    
  ------------------------------------------------------------------
  
  We get additional finite cycles, e.g.:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  But  the  group  structure remains invariant under the "transfer" of a group
  with prime set 2,3 from Z to Z_(2,3):
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  "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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
    
  ------------------------------------------------------------------
  
  Again, viewed as an rcwa mapping of the integers the commutator given at the
  end of the example would not be surjective.
  
  
  5.11 Twisting 257-cycles into an rcwa mapping with modulus 32
  
  We define an rcwa mapping x 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.
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.12 The behaviour of the moduli of powers
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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
    
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.13 Images and preimages under the Collatz mapping
  
  We  have  a look at the images of the residue class 1(2) under powers of the
  Collatz mapping.
  
  ---------------------------  Example  ----------------------------
    
    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)
    
  ------------------------------------------------------------------
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The images of the residue class 0(3) under powers of T look as follows:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    gap> S := [ResidueClass(Integers,5,0)];
    [ 0(5) ]
    gap> for i in [1..12] do Add(S,S[i]^T); od;
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  
  5.14 A group which acts 4-transitively on the positive integers
  
  In this section, we would like to show that the group G generated by the two
  wild mappings
  
  ---------------------------  Example  ----------------------------
    
    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);;
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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)
    
  ------------------------------------------------------------------
  
  We  see  that  we  cannot always choose such a group element from the set of
  generators and their inverses -- otherwise the union would be Integers.
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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!):
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The resulting products have various different not quite small moduli:
  
  ---------------------------  Example  ----------------------------
    
    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 ] ]
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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)
    [  ]
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  We have to treat 4 separately:
  
  ---------------------------  Example  ----------------------------
    
    gap> 1^(u*a*u^2*a^-1*u);
    1
    gap> 4^(u*a*u^2*a^-1*u);
    3
    
  ------------------------------------------------------------------
  
  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.
  
  In  the  following,  we essentially repeat the above steps to show that this
  action is indeed 3-transitive:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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)
    [  ]
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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;
    [  ]
    
  ------------------------------------------------------------------
  
  The same for 4-transitivity:
  
  ---------------------------  Example  ----------------------------
    
    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);
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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;
    [  ]
    
  ------------------------------------------------------------------
  
  There is even some evidence that the degree of transitivity of the action of
  G on the positive integers is higher than 4:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  
  5.15 A group which acts 3-transitively, but not 4-transitively on Z
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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
    
    ]
    
    
  ------------------------------------------------------------------
  
  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.
  
  ---------------------------  Example  ----------------------------
    
    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 ] ]
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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):
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  This   shows   that  G  acts  not  4-transitively  on Z.  The  corresponding
  calculation for 3-tuples looks as follows:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Needless  to  say  that the latter kind of argumentation is not suitable for
  proving, but only for disproving k-transitivity.
  
  
  5.16 Grigorchuk groups
  
  In  this  section,  we  show  how  to  construct finite quotients of the two
  infinite  periodic groups introduced by Rostislav Grigorchuk in [Gri80] with
  the  help of RCWA. The first of these, nowadays known as "Grigorchuk group",
  is   investigated   in   an   example  given  on  the  GAP  website  --  see
  http://www.gap-system.org/Doc/Examples/grigorchuk.html.   The  RCWA  package
  permits  a  simpler and more elegant construction of the finite quotients of
  this  group:  The  function  TopElement  given on the mentioned webpage gets
  unnecessary, and the function SequenceElement can be simplified as follows:
  
  ------------------------------------------------------------------
    
    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;
    
  ------------------------------------------------------------------
  
  The actual constructors for the generators are modified as follows:
  
  ------------------------------------------------------------------
    
    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);
    
  ------------------------------------------------------------------
  
  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 [Gri80]:
  
  ---------------------------  Example  ----------------------------
    
    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));;
    
  ------------------------------------------------------------------
  
  We  can do similar things as shown in the example on the GAP webpage for the
  "first" Grigorchuk group:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  
  5.17 Forward orbits of a monoid with 2 generators
  
  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
  
  
                                         /
                                        | n/2          if n even,
            T_5+/-:  Z -> Z,   n  |->  <
                                        | (5n +/- 1)/2 if n odd
                                         \
  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:
  
  ---------------------------  Example  ----------------------------
    
    gap> T5m := RcwaMapping([[1,0,2],[5,-1,2]]);;
    gap> T5p := RcwaMapping([[1,0,2],[5, 1,2]]);;
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  
  5.18 Representations of the free group of rank 2
  
  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. [dlH00], page 27) from PSL(2,C) to RCWA(Z)
  (we use the notation from the cited book):
  
  ---------------------------  Example  ----------------------------
    
    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>
    
  ------------------------------------------------------------------
  
  We can do some checks:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  The generators are products of 3 class transpositions, each:
  
  ---------------------------  Example  ----------------------------
    
    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) ]
    
  ------------------------------------------------------------------
  
  The above construction is used by IsomorphismRcwaGroup (3.1-3) to embed free
  groups of any rank >= 2.
  
  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
  Table-Tennis  Lemma (see e.g. [dlH00], Section II.B.) to the infinite cyclic
  groups generated by the two generators and to the same two sets X1 and X2 as
  above:
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  Drawing  the  transition  graphs  of  r1  and  r2  for  modulus 4  may  help
  understanding  what  is actually done in this calculation. It is easy to see
  that the group generated by r1 and r2 is not free:
  
  ---------------------------  Example  ----------------------------
    
    gap> Order(r1/r2);
    3
    
  ------------------------------------------------------------------
  
  
  5.19 Representations of the modular group PSL(2,Z)
  
  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:
  
  ---------------------------  Example  ----------------------------
    
    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 ]
    
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    
    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
    
  ------------------------------------------------------------------
  
  A  slightly  different  representation  of PSL(2,Z) can be obtained by using
  RCWA's  general  method for IsomorphismRcwaGroup for free products of finite
  groups:
  
  ---------------------------  Example  ----------------------------
    
    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
    
    ]
    
    
  ------------------------------------------------------------------