<!-- #################################################################### -->
<!-- ##                                                                ## -->
<!-- ##  examples.xml         RCWA documentation          Stefan Kohl  ## -->
<!-- ##                                                                ## -->
<!-- ##  $Id: examples.xml,v 1.67 2005/12/19 17:48:43 stefan Exp $     ## -->
<!-- ##                                                                ## -->
<!-- #################################################################### -->

<Chapter Label="ch:Examples"><Heading>Examples</Heading>

This chapter lists some <Q>nice</Q> examples of rcwa mappings and -groups.
The rcwa mappings mentioned in this chapter can be found in the file
<F>pkg/rcwa/examples/examples.g</F>, so there is no need to extract them
from the manual files. This file can be read into the current &GAP; session
by issueing <C>RCWAReadExamples( );</C>.

<!-- #################################################################### -->

<Section Label="sec:FactoringTheCollatzPermutation">
<Heading>
  Factoring Collatz' permutation of the integers
</Heading>

In 1932, Lothar Collatz mentioned in his notebook the following permutation
of the integers:

<Example>
<![CDATA[
gap> Collatz := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);;
gap> SetName(Collatz,"Collatz");
gap> 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

]]>
</Example>

This permutation has a few finite cycles, but its cycle structure
has not been determined yet. In particular it is not known whether
the cycle containing 8 is finite or infinite.

<Example>
<![CDATA[
gap> List(ShortOrbits(Group(Collatz),[-100..100],100),
>         orb->Cycle(Collatz,Minimum(orb)));
[ [ -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 ] ]
gap> List(last,Length);
[ 12, 5, 2, 1, 1, 1, 2, 5, 12 ]
]]>
</Example>

Nevertheless, the factorization routine included in this package can
determine a factorization of this permutation into involutions interchanging
two disjoint residue classes, each (for reasons of saving a bit space in
this manual, we factor the inverse mapping instead and revert the list
afterwards):

<Example>
<![CDATA[
gap> RCWAInfo(2); # Switch Info output on.
gap> Reversed(FactorizationIntoGenerators(Collatz^-1:ExpandPrimeSwitches));
#I  Modulus(<g>) = 4, Multiplier(<g>) = 3, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 16, Multiplier(<g>) = 3, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 6, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 12
#I  p = 3, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 3(6), 5(12), 7(12), 8(12), 0(48) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 6(8) ]
#I  Found 5 pairs.
#I  After filtering and splitting: 5 pairs.
#I  Dividing by ClassTransposition(3,6,6,8) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,5,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,7,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,8,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,0,48) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 6, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 12
#I  p = 3, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 7(12), 8(12), 0(96) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 6(8) ]
#I  Found 3 pairs.
#I  After filtering and splitting: 3 pairs.
#I  Dividing by ClassTransposition(6,8,7,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,8,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,8,0,96) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 12, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 24, Divisor(<g>) = 12
#I  p = 3, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 7(12), 0(192) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 2(4) ]
#I  Found 2 pairs.
#I  After filtering and splitting: 2 pairs.
#I  Dividing by ClassTransposition(2,4,7,12) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 24, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(2,4,0,192) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 24, Divisor(<g>) = 4
#I  Dividing by PrimeSwitch(3) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 48, Divisor(<g>) = 12
#I  p = 3, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 0(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 2(4) ]
#I  Found 1 pairs.
#I  After filtering and splitting: 1 pairs.
#I  Dividing by ClassTransposition(2,4,0,384) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 128, Divisor(<g>) = 4
#I  p = 2, kmult = 7, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 384(1536) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 2(4), 3(6), 1(12), 11(12) ]
#I  Found 3 pairs.
#I  After filtering and splitting: 5 pairs.
#I  Dividing by ClassTransposition(2,12,384,1536) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 32, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(1,12,384,1536) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 32, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,12,384,1536) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 32, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(10,12,384,1536) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 32, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(11,12,384,1536) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 32, Divisor(<g>) = 4
#I  p = 2, kmult = 5, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 0(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 3(6), 1(12), 6(12), 10(12), 11(12) ]
#I  Found 4 pairs.
#I  After filtering and splitting: 4 pairs.
#I  Dividing by ClassTransposition(1,12,0,384) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(6,12,0,384) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(10,12,0,384) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(11,12,0,384) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  p = 2, kmult = 4, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 48(192), 192(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 3(6), 6(12), 10(12), 11(12) ]
#I  Found 3 pairs.
#I  After filtering and splitting: 3 pairs.
#I  Dividing by ClassTransposition(6,12,48,192) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(10,12,48,192) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(11,12,48,192) from the right.
#I  Modulus(<g>) = 48, Multiplier(<g>) = 16, Divisor(<g>) = 4
#I  p = 2, kmult = 4, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 192(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 3(6), 10(12), 11(12) ]
#I  Splitting classes being divided by q*p^kdiv.
#I  Found 4 pairs.
#I  After filtering and splitting: 4 pairs.
#I  Dividing by ClassTransposition(10,24,192,384) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 8, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(11,24,192,384) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 8, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(22,24,192,384) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 8, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(23,24,192,384) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 8, Divisor(<g>) = 4
#I  p = 2, kmult = 3, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 72(96), 96(192), 0(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 3(6), 11(12), 22(24) ]
#I  Found 2 pairs.
#I  After filtering and splitting: 2 pairs.
#I  Dividing by ClassTransposition(11,12,72,96) from the right.
#I  Dividing by ClassTransposition(22,24,96,192) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 8, Divisor(<g>) = 4
#I  p = 2, kmult = 3, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 0(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 3(6) ]
#I  Splitting classes being divided by q*p^kdiv.
#I  Splitting classes being divided by q*p^kdiv.
#I  Splitting classes being divided by q*p^kdiv.
#I  Found 8 pairs.
#I  After filtering and splitting: 8 pairs.
#I  Dividing by ClassTransposition(3,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(9,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(15,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(21,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(27,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(33,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(39,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(45,48,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  p = 2, kmult = 2, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 44(48), 48(96), 192(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 9(12), 15(24), 27(48) ]
#I  Found 2 pairs.
#I  After filtering and splitting: 2 pairs.
#I  Dividing by ClassTransposition(9,12,44,48) from the right.
#I  Dividing by ClassTransposition(15,24,48,96) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 4, Divisor(<g>) = 4
#I  p = 2, kmult = 2, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 192(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 27(48) ]
#I  Splitting classes being divided by q*p^kdiv.
#I  Found 2 pairs.
#I  After filtering and splitting: 2 pairs.
#I  Dividing by ClassTransposition(27,96,192,384) from the right.
#I  Modulus(<g>) = 384, Multiplier(<g>) = 2, Divisor(<g>) = 4
#I  Dividing by ClassTransposition(75,96,192,384) from the right.
#I  Modulus(<g>) = 384, Multiplier(<g>) = 2, Divisor(<g>) = 4
#I  p = 2, kmult = 1, kdiv = 2
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 4(24), 17(24), 24(48), 96(192), 0(384) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 75(96) ]
#I  Found 1 pairs.
#I  After filtering and splitting: 1 pairs.
#I  Dividing by ClassTransposition(75,96,0,384) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  p = 2, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 4(24), 17(24), 24(48), 96(192) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 7(12), 5(24), 12(24), 16(24), 75(96) ]
#I  Found 6 pairs.
#I  After filtering and splitting: 6 pairs.
#I  Dividing by ClassTransposition(7,12,4,24) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  Dividing by ClassTransposition(7,12,17,24) from the right.
#I  Dividing by ClassTransposition(5,24,24,48) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  Dividing by ClassTransposition(12,24,24,48) from the right.
#I  Modulus(<g>) = 192, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  Dividing by ClassTransposition(16,24,24,48) from the right.
#I  Dividing by ClassTransposition(75,96,96,192) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  p = 2, kmult = 1, kdiv = 1
#I  Image of classes being multiplied by q*p^kmult:
#I  [ 17(24) ]
#I  Image of classes being divided by q*p^kdiv:
#I  [ 12(24), 16(24) ]
#I  Splitting classes being multiplied by q*p^kmult.
#I  Found 4 pairs.
#I  After filtering and splitting: 4 pairs.
#I  Dividing by ClassTransposition(12,24,17,48) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  Dividing by ClassTransposition(16,24,17,48) from the right.
#I  Dividing by ClassTransposition(12,24,41,48) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 2, Divisor(<g>) = 2
#I  Dividing by ClassTransposition(16,24,41,48) from the right.
#I  Modulus(<g>) = 96, Multiplier(<g>) = 1, Divisor(<g>) = 1
#I  Determining largest sources of affine mappings.
#I  Computing respected partition.
#I  Computing induced permutation on respected partition 
[ 12(24), 14(24), 18(24), 13(48), 22(48), 23(48), 28(48), 31(48), 32(48), 
  33(48), 34(48), 35(48), 39(48), 44(48), 45(48), 0(96), 1(96), 2(96), 3(96), 
  4(96), 5(96), 6(96), 7(96), 8(96), 9(96), 10(96), 11(96), 15(96), 16(96), 
  17(96), 19(96), 20(96), 21(96), 24(96), 25(96), 26(96), 27(96), 29(96), 
  30(96), 37(96), 40(96), 41(96), 43(96), 46(96), 47(96), 48(96), 49(96), 
  50(96), 51(96), 52(96), 53(96), 54(96), 55(96), 56(96), 57(96), 58(96), 
  59(96), 63(96), 64(96), 65(96), 67(96), 68(96), 69(96), 72(96), 73(96), 
  74(96), 75(96), 77(96), 78(96), 85(96), 88(96), 89(96), 91(96), 94(96), 
  95(96) ].
#I  Factoring the rest into class shifts.
#I  Checking the result.
[ ClassTransposition(4,6,7,12), ClassTransposition(2,6,1,12), 
  ClassTransposition(2,4,5,6), ClassTransposition(0,4,1,6), 
  ClassTransposition(5,6,4,8), ClassTransposition(1,6,0,8), 
  ClassTransposition(4,6,7,12), ClassTransposition(2,6,1,12), 
  ClassTransposition(2,4,5,6), ClassTransposition(0,4,1,6), 
  ClassTransposition(5,6,4,8), ClassTransposition(1,6,0,8), 
  ClassTransposition(4,6,7,12), ClassTransposition(2,6,1,12), 
  ClassTransposition(2,4,5,6), ClassTransposition(0,4,1,6), 
  ClassTransposition(5,6,4,8), ClassTransposition(1,6,0,8), 
  ClassTransposition(3,6,6,8), ClassTransposition(6,8,5,12), 
  ClassTransposition(6,8,7,12), ClassTransposition(6,8,8,12), 
  ClassTransposition(6,8,0,48), ClassTransposition(4,6,7,12), 
  ClassTransposition(2,6,1,12), ClassTransposition(2,4,5,6), 
  ClassTransposition(0,4,1,6), ClassTransposition(5,6,4,8), 
  ClassTransposition(1,6,0,8), ClassTransposition(6,8,7,12), 
  ClassTransposition(6,8,8,12), ClassTransposition(6,8,0,96), 
  ClassTransposition(4,6,7,12), ClassTransposition(2,6,1,12), 
  ClassTransposition(2,4,5,6), ClassTransposition(0,4,1,6), 
  ClassTransposition(5,6,4,8), ClassTransposition(1,6,0,8), 
  ClassTransposition(2,4,7,12), ClassTransposition(2,4,0,192), 
  ClassTransposition(4,6,7,12), ClassTransposition(2,6,1,12), 
  ClassTransposition(2,4,5,6), ClassTransposition(0,4,1,6), 
  ClassTransposition(5,6,4,8), ClassTransposition(1,6,0,8), 
  ClassTransposition(2,4,0,384), ClassTransposition(2,12,384,1536), 
  ClassTransposition(1,12,384,1536), ClassTransposition(6,12,384,1536), 
  ClassTransposition(10,12,384,1536), ClassTransposition(11,12,384,1536), 
  ClassTransposition(1,12,0,384), ClassTransposition(6,12,0,384), 
  ClassTransposition(10,12,0,384), ClassTransposition(11,12,0,384), 
  ClassTransposition(6,12,48,192), ClassTransposition(10,12,48,192), 
  ClassTransposition(11,12,48,192), ClassTransposition(10,24,192,384), 
  ClassTransposition(11,24,192,384), ClassTransposition(22,24,192,384), 
  ClassTransposition(23,24,192,384), ClassTransposition(11,12,72,96), 
  ClassTransposition(22,24,96,192), ClassTransposition(3,48,0,384), 
  ClassTransposition(9,48,0,384), ClassTransposition(15,48,0,384), 
  ClassTransposition(21,48,0,384), ClassTransposition(27,48,0,384), 
  ClassTransposition(33,48,0,384), ClassTransposition(39,48,0,384), 
  ClassTransposition(45,48,0,384), ClassTransposition(9,12,44,48), 
  ClassTransposition(15,24,48,96), ClassTransposition(27,96,192,384), 
  ClassTransposition(75,96,192,384), ClassTransposition(75,96,0,384), 
  ClassTransposition(7,12,4,24), ClassTransposition(7,12,17,24), 
  ClassTransposition(5,24,24,48), ClassTransposition(12,24,24,48), 
  ClassTransposition(16,24,24,48), ClassTransposition(75,96,96,192), 
  ClassTransposition(12,24,17,48), ClassTransposition(16,24,17,48), 
  ClassTransposition(12,24,41,48), ClassTransposition(16,24,41,48), 
  ClassTransposition(3,96,43,96), ClassTransposition(3,96,40,96), 
  ClassTransposition(3,96,26,96), ClassTransposition(3,96,30,96), 
  ClassTransposition(3,96,24,96), ClassTransposition(3,96,25,96), 
  ClassTransposition(3,96,29,96), ClassTransposition(3,96,11,96), 
  ClassTransposition(3,96,10,96), ClassTransposition(3,96,15,96), 
  ClassTransposition(3,96,27,96), ClassTransposition(3,96,51,96), 
  ClassTransposition(3,96,91,96), ClassTransposition(3,96,88,96), 
  ClassTransposition(3,96,74,96), ClassTransposition(3,96,78,96), 
  ClassTransposition(3,96,72,96), ClassTransposition(3,96,73,96), 
  ClassTransposition(3,96,77,96), ClassTransposition(3,96,59,96), 
  ClassTransposition(3,96,58,96), ClassTransposition(3,96,63,96), 
  ClassTransposition(3,96,75,96), ClassTransposition(0,96,95,96), 
  ClassTransposition(0,96,94,96), ClassTransposition(0,96,85,96), 
  ClassTransposition(0,96,89,96), ClassTransposition(0,96,49,96), 
  ClassTransposition(0,96,53,96), ClassTransposition(0,96,57,96), 
  ClassTransposition(0,96,56,96), ClassTransposition(0,96,55,96), 
  ClassTransposition(0,96,52,96), ClassTransposition(0,96,69,96), 
  ClassTransposition(0,96,68,96), ClassTransposition(0,96,65,96), 
  ClassTransposition(0,96,67,96), ClassTransposition(0,96,64,96), 
  ClassTransposition(0,96,50,96), ClassTransposition(0,96,54,96), 
  ClassTransposition(0,96,48,96), ClassTransposition(0,96,47,96), 
  ClassTransposition(0,96,46,96), ClassTransposition(0,96,37,96), 
  ClassTransposition(0,96,41,96), ClassTransposition(0,96,1,96), 
  ClassTransposition(0,96,5,96), ClassTransposition(0,96,9,96), 
  ClassTransposition(0,96,8,96), ClassTransposition(0,96,7,96), 
  ClassTransposition(0,96,4,96), ClassTransposition(0,96,21,96), 
  ClassTransposition(0,96,20,96), ClassTransposition(0,96,17,96), 
  ClassTransposition(0,96,19,96), ClassTransposition(0,96,16,96), 
  ClassTransposition(0,96,2,96), ClassTransposition(0,96,6,96), 
  ClassTransposition(13,48,35,48), ClassTransposition(13,48,34,48), 
  ClassTransposition(13,48,39,48), ClassTransposition(13,48,33,48), 
  ClassTransposition(13,48,32,48), ClassTransposition(13,48,31,48), 
  ClassTransposition(13,48,28,48), ClassTransposition(13,48,45,48), 
  ClassTransposition(13,48,44,48), ClassTransposition(13,48,23,48), 
  ClassTransposition(13,48,22,48), ClassTransposition(12,24,14,24), 
  ClassTransposition(12,24,18,24) ]
gap> Product(last) = Collatz; # Check the result.
true
gap> Length(last2);
159
gap> RCWAInfo(0); # Switch Info output off again.
]]>
</Example>

See the end of Section <Ref Label="sec:WildButFiniteCycles"/> for a much
smaller factorization task performed <Q>manually</Q> for purposes of
illustration.
 
</Section>

<!-- #################################################################### -->

<Section Label="sec:SlowlyContractingMapping">
<Heading>
  An rcwa mapping which seems to be contracting, but very slow
</Heading>

The iterates of an integer under the Collatz mapping <M>T</M> 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 Collatz conjecture has not been proved so far!):

<Example>
<![CDATA[
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 information on how to improve this guess.
[ -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> Trajectory(T,27,S0,"stop");
[ 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 
  233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 
  425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 
  3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 
  23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2 ]
gap> List([1..40],n->Length(Trajectory(T,n,S0,"stop")));
[ 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, 67, 5, 18, 10, 10, 15, 15, 15, 23, 7 ]
gap> Maximum(List([1..1000],n->Length(Trajectory(T,n,S0,"stop"))));
113
gap> Maximum(List([1..1000],n->Maximum(Trajectory(T,n,S0,"stop"))));
125252
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

The following mapping also seems to be contracting, but its trajectories
are much longer:

<Log>
<![CDATA[
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);

Integral rcwa mapping 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.
gap> Trajectory(f6,25,S0,"stop");
[ 25, 21, 39, 72, 12, 2 ]
gap> List([1..100],n->Length(Trajectory(f6,n,S0,"stop")));
[ 2, 2, 3, 4, 2, 2, 3, 2, 2, 5, 7, 2, 8, 17, 3, 16, 2, 4, 17, 6, 5, 2, 5, 5, 
  6, 2, 4, 2, 15, 2, 2, 3, 2, 5, 13, 3, 2, 3, 4, 2, 8, 4, 4, 2, 7, 19, 23517, 
  3, 9, 3, 2, 18, 14, 2, 20, 23512, 14, 2, 6, 6, 2, 4, 19, 12, 23511, 8, 
  23513, 10, 2, 13, 13, 3, 2, 23517, 7, 20, 7, 9, 9, 6, 12, 8, 6, 18, 14, 
  23516, 31, 12, 23545, 4, 21, 19, 5, 2, 17, 17, 13, 19, 6, 23515 ]
gap> Maximum(Trajectory(f6,47,S0,"stop"));;
736339177776247330443187705477107581873369010805146980871580925673774229545698\
886054
]]>
</Log>

Computing the trajectory of 3224 takes quite a while -- this trajectory
ascends to about <M>3 \cdot 10^{2197}</M>, before it approaches the fixed
point&nbsp;2 after 19949562 steps. <P/>

When constructing the mapping <C>f6</C>, 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 <C>Modulus(f6)</C>th power of the
denominator. In the example we have <M>5 \cdot 7 \cdot 11^3 = 46585</M>
and <M>6^6 = 46656</M>. <P/>

Although the trajectories of <C>T</C> are much shorter than those of
<C>f6</C>, it seems likely that this does not make the problem of deciding
whether the mapping&nbsp;<C>T</C> is contracting essentially easier --
even for mappings with much shorter trajectories than&nbsp;<C>T</C>
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 <M>k</M> such that
applying the <M>k</M>th power of the respective mapping to any integer
decreases its absolute value.

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:AndaloroResult">
<Heading>Checking a result by P. Andaloro</Heading>

In <Cite Key="Andaloro00"/>, P.&nbsp;Andaloro has shown that proving that
trajectories of integers <M>n \in 1(16)</M> under the Collatz mapping always
end up with&nbsp;1 would be sufficient for proving the Collatz conjecture.
In the sequel, this result is verified with &RCWA;. Checking that the
union of the images of the residue class 1(16) under powers of the Collatz
mapping&nbsp;<M>T</M> contains <M>\mathbb{Z} \setminus 0(3)</M> is obviously
sufficient. Thus we proceed by setting <M>S := 1(16)</M> and successively
uniting the set <M>S</M> with its image under&nbsp;<M>T</M>:

<Example>
<![CDATA[
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
]]>
</Example>

Further similar computations are shown in
Section&nbsp;<Ref Label="sec:CollatzImagesAndPreImages"/>.

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:MatthewsLeighExamples">
<Heading>Two examples by Matthews and Leigh</Heading>

In <Cite Key="MatthewsLeigh87"/>, K.&nbsp;R.&nbsp;Matthews and
G.&nbsp;M.&nbsp;Leigh have shown that two trajectories of the following
(surjective, but not injective) mappings are acyclic (mod&nbsp;<M>x</M>)
and divergent:

<Example>
<![CDATA[
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,"length");
[ 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,"length");
[ 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 ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

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&nbsp;mod&nbsp;<M>x</M> and
1&nbsp;mod&nbsp;<M>x</M>:

<Example>
<![CDATA[
gap> traj1modx := Trajectory(ML1,One(R),400,"length") mod x;;
gap> traj2modx := Trajectory(ML2,(x^3+x+1)*One(R),600,"length") mod x;;
gap> List(traj1modx{[1..200]},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, 
  1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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 ]
gap> List(traj2modx{[1..200]},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, 
  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 ]
]]>
</Example>

What is important here are the lengths of the intervals between two changes
from one state to the other:

<Example>
<![CDATA[
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 ]
]]>
</Example>

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.

</Section>

<!-- #################################################################### -->

<Section Label="sec:StructureOfWildGroup">
<Heading>Exploring the structure of a wild rcwa group</Heading>

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 computationally
seems to be a very hard task. First of all, the group in question
has to be defined:

<Example>
<![CDATA[
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 := RcwaMapping([[1,1,1]]);
Rcwa mapping of Z: n -> n + 1
gap> SetName(nu,"nu");
gap> G := Group(u,nu);
<rcwa group over Z with 2 generators>
gap> IsTame(G);
false
]]>
</Example>

Now we would like to know which orders torsion elements of&nbsp;<C>G</C>
can have -- taking a look at the above generators it seems to make sense
to try commutators:

<Example>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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> orbs := ShortOrbits(Group(u2nu17),[-100..100],100);;
gap> List(orbs,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> orbs := ShortOrbits(Group(u2nu18),[-100..100],100);;
gap> List(orbs,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
]]>
</Example>

Thus even this rather simple-minded approach reveals various different
orders of torsion elements, and the involved primes are also not all
quite <Q>small</Q>.

</Section>

<!-- #################################################################### -->

<Section Label="sec:WildButFiniteCycles">
<Heading>A wild rcwa mapping which has only finite cycles</Heading>

Some wild rcwa mappings of <M>\mathbb{Z}</M> 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 <Q>minimal</Q> example.
<P/>

Over <M>R</M> = GF(<M>q</M>)[<M>x</M>], constructing such mappings is easy
since the degree function gives rise to a partition of <M>R</M> into
finite sets which is left invariant by suitable wild rcwa mappings.
Over <M>R = \mathbb{Z}</M> however the situation looks different --
there is no such <Q>natural</Q> partition into finite sets which can be
fixed by a wild rcwa mapping.

<Example>
<![CDATA[
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> lengthstatistics := Collected(List(ShortOrbits(Group(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 ] ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

We would like to determine a partition of&nbsp;<M>\Z</M> into unions of
cycles of equal length:

<Example>
<![CDATA[
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>

<Example>
<![CDATA[
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 ]
]]>
</Example>

Finally, the permutation <C>kappa</C> should be factored into involutions
(this time <Q>by hand</Q>, for purposes of illustration):

<Example>
<![CDATA[
gap> elm1 := kappa;
kappa
gap> Multpk(elm1,2,1)^elm1;
8(12)
gap> Multpk(elm1,2,-1)^elm1;
4(6)
gap> Multpk(elm1,3,1)^elm1;
4(6)
gap> Multpk(elm1,3,-1)^elm1;
3(4)
gap> fact1 := RcwaMapping([[rc(4,6),rc(8,12)]]);
<rcwa mapping of Z with modulus 12>
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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 := RcwaMapping([[rc(3,4),rc(8,12)]]);
<rcwa mapping of Z with modulus 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 := RcwaMapping([[rc(2,4),rc(3,4)]]);
<rcwa mapping of Z with modulus 4>
gap> elm4 := elm3/fact3;
IdentityMapping( Integers )
gap> kappafacts := [ fact3, fact2, fact1 ];
[ <bijective rcwa mapping of Z with modulus 4>, 
  <bijective rcwa mapping of Z with modulus 12>, 
  <bijective rcwa mapping of Z with modulus 12> ]
gap> List(kappafacts,Order);
[ 2, 2, 2 ]
gap> kappa = Product(kappafacts);
true
]]>
</Example>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:AbelianModularGroup">
<Heading>An abelian rcwa group over a polynomial ring</Heading>

In this section, a wild rcwa group over GF(4)[<M>x</M>] 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>
<![CDATA[
gap> x := Indeterminate(GF(4),1);; SetName(x,"x");
gap> R := PolynomialRing(GF(4),1);
GF(4)[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(4)[x] with modulus x^2+Z(2)^0>
gap> h := RcwaMapping( R, s, ch );
<rcwa mapping of GF(4)[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(4)[x] with 2 generators>
gap> IsAbelian(G);
true
]]>
</Example>

Now we compute the action of the group <C>G</C> on one of its orbits, and
make some statistics of the orbits of <C>G</C> containing polynomials of
degree less than&nbsp;4:

<Example>
<![CDATA[
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 ] ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

Changing the generators a little causes the group structure to change a lot:

<Example>
<![CDATA[
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(4)[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) ])
]]>
</Example>

Thus the modified group has a quotient isomorphic to the alternating group
of degree&nbsp;87, and a quotient isomorphic to some wreath product or a
subgroup thereof acting transitively, but not primitively on 512 points.

</Section>

<!-- #################################################################### -->

<Section Label="sec:SubgroupOfS9">
<Heading>An rcwa representation of a small group</Heading>

In the sequel, an rcwa representation of the 3-Sylow-subgroup of the
symmetric group on 9&nbsp;points is given. Of course this group has a very
nice permutation representation, hence for computational purposes one does
not gain anything here.

<Example>
<![CDATA[
gap> r := RcwaMapping([[1,0,1],[1,1,1],[3,-3,1],
>                      [1,0,3],[1,1,1],[3,-3,1],
>                      [1,0,1],[1,1,1],[3,-3,1]]);;
gap> s := RcwaMapping([[1,0,1],[1,1,1],[3,6,1],
>                      [1,0,3],[1,1,1],[3,6,1],
>                      [1,0,1],[1,1,1],[3,-21,1]]);;
gap> SetName(r,"r"); SetName(s,"s");
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
gap> Display(r);

Rcwa mapping of Z with modulus 9

                n mod 9                |                 n^r
---------------------------------------+--------------------------------------
  0 6                                  | n
  1 4 7                                | n + 1
  2 5 8                                | 3n - 3
  3                                    | n/3

gap> Display(s);

Rcwa mapping of Z with modulus 9

                n mod 9                |                 n^s
---------------------------------------+--------------------------------------
  0 6                                  | n
  1 4 7                                | n + 1
  2 5                                  | 3n + 6
  3                                    | n/3
  8                                    | 3n - 21

gap> G := Group(r,s);
<rcwa group over Z with 2 generators>
gap> H := SylowSubgroup(SymmetricGroup(9),3);
Group([ (1,2,3), (4,5,6), (7,8,9), (1,4,7)(2,5,8)(3,6,9) ])
gap> phi := InverseGeneralMapping(IsomorphismGroups(G,H));;
gap> (1,2,3)^phi;
<bijective rcwa mapping of Z with modulus 27>
]]>
</Example>

</Section>

<!-- #################################################################### -->

<Section Label="sec:RcwaRepresentationOfS10">
<Heading>
  An rcwa representation of the symmetric group on 10 points
</Heading>

In this section, an rcwa representation of the symmetric group on
10&nbsp;points should be investigated. We start by defining some
bijections of infinite order and computing commutators:

<Example>
<![CDATA[
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],Order);
[ infinity, infinity, infinity ]
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 ]
]]>
</Example>

Now we would like to have a look at [<A>a</A>,<A>b</A>] ...

<Example>
<![CDATA[
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

]]>
</Example>

... form the group generated by [<A>a</A>,<A>b</A>]
and [<A>a</A>,<A>c</A>] and compute its action on one of its orbits:

<Example>
<![CDATA[
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 faithful on orb.
3628800
]]>
</Example>

Hence the group <A>G</A> is isomorphic to the symmetric group on
10&nbsp;points and acts faithfully on the orbit containing&nbsp;1.

Another question is which groups arise if we take as generators
either <A>ab</A>, <A>ac</A> or <A>bc</A> and the mapping&nbsp;<A>t</A>,
which maps each integer to its additive inverse:

<Example>
<![CDATA[
gap> t := RcwaMapping([[-1,0,1]]);
Rcwa mapping of Z: n -> -n
gap> Order(t);
2
gap> G := Group(ab,t);
<rcwa group over Z with 2 generators>
gap> Size(G);
7257600
gap> H := Image(IsomorphismPermGroup(G));;
gap> H2 := Group((1,2),(1,2,3,4,5,6,7,8,9,10),(11,12));;
gap> IsomorphismGroups(H,H2) <> fail; # H = C2 x S10
true
]]>
</Example>

Thus the group generated by <A>ab</A> and <A>t</A> is isomorphic to 
<Alt Only="LaTeX"><M>{\rm C}_2 \times {\rm S}_{10}</M></Alt>
<Alt Not="LaTeX"><M>C_2 x S_{10}</M></Alt>.
The next group is an extension of a perfect group of order&nbsp;960:

<Example>
<![CDATA[
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'
]]>
</Example>

The last group is infinite:

<Example>
<![CDATA[
gap> G := Group(bc,t);;
gap> Size(G);
infinity
gap> Order(bc*t);
infinity
gap> Modulus(G);
18
gap> ResidueClassUnionViewingFormat("short");
gap> RespectedPartition(G);
[ 0(18), 1(18), 2(18), 4(18), 5(18), 7(18), 8(18), 9(18), 10(18), 11(18), 
  13(18), 14(18), 16(18), 17(18), 3(36), 6(36), 12(36), 15(36), 21(36), 
  24(36), 30(36), 33(36) ]
gap> D := DerivedSubgroup(ActionOnRespectedPartition(G));;
gap> DegreeAction(D);
20
gap> IsPerfect(D);
true
gap> Size(D);
928972800
gap> RankOfKernelOfActionOnRespectedPartition(G:ProperSubgroupAllowed);
9
]]>
</Example>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:CheckingForSolvability">
<Heading>Checking for solvability</Heading>

Is the group generated by the mappings <A>a</A> and <A>b</A> from the last
paragraph solvable? <P/>

This group is wild. Presently there is no general method available for
testing wild rcwa groups for solvability. But nevertheless, for the given
group this question can be decided to the negative. The idea is to find a
subgroup <A>U</A> which acts on a finite set <A>S</A> of integers,
and induces on <A>S</A> a non-solvable finite permutation group:

<Example>
<![CDATA[
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
]]>
</Example>

Thus, the subgroup <A>U</A> induces on <A>S</A> a natural symmetric group
of degree&nbsp;6. Hence the group&nbsp;<A>G</A> is not solvable, as claimed.
We finish this example by factoring the group element <A>elm</A> into
generators:

<Example>
<![CDATA[
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
]]>
</Example>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:LocalExample">
<Heading>Some examples over (semi)localizations of the integers</Heading>

We start with something one can observe when trying to <Q>transfer</Q> an
rcwa mapping from the ring of integers to one of its localizations (we take
the mapping <C>a</C> from the previous examples):

<Example>
<![CDATA[
gap> a2 := RcwaMapping(Z_pi(2),ShallowCopy(Coefficients(a)));
<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
]]>
</Example>

The above can also be explained easily by pointing out that the modulus
of the inverse of <C>a</C> is 3, and that 3 is a unit of
<M>\mathbb{Z}_{(2)}</M>.
Moving to <M>\mathbb{Z}_{(2,3)}</M> solves this problem:

<Example>
<![CDATA[
gap> a23 := RcwaMapping(Z_pi([2,3]),ShallowCopy(Coefficients(a)));
<rcwa mapping of Z_( 2, 3 ) with modulus 4>
gap> IsBijective(a23);
true
]]>
</Example>

We get additional finite cycles, e.g.:

<Example>
<![CDATA[
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 ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

But the group structure remains invariant under the <Q>transfer</Q> of
a group with prime set <M>\{2,3\}</M> from <M>\Z</M> to <M>\Z_{(2,3)}</M>:

<Example>
<![CDATA[
gap> b23 := RcwaMapping(Z_pi([2,3]),ShallowCopy(Coefficients(b)));;
gap> c23 := RcwaMapping(Z_pi([2,3]),ShallowCopy(Coefficients(c)));;
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..200]},Z_pi([2,3]));
[ -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -12/5, -11/5, -2, -9/5, -12/7, 
  -8/5, -11/7, -10/7, -7/5, -9/7, -6/5, -8/7, -12/11, -1, -10/11, -6/7, 
  -9/11, -4/5, -8/11, -5/7, -7/11, -3/5, -4/7, -6/11, -5/11, -3/7, -2/5, 
  -4/11, -2/7, -3/11, -1/5, -2/11, -1/7, -1/11, 0, 1/13, 1/11, 1/7, 2/13, 
  2/11, 1/5, 3/13, 3/11, 2/7, 4/13, 4/11, 5/13, 2/5, 3/7, 5/11, 6/13, 7/13, 
  6/11, 4/7, 3/5, 8/13, 7/11, 9/13, 5/7, 8/11, 10/13, 4/5, 9/11, 11/13, 6/7, 
  10/11, 12/13, 1, 12/11, 8/7, 13/11, 6/5, 9/7, 7/5, 10/7, 11/7, 8/5, 12/7, 
  9/5, 2, 11/5, 12/5, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]
gap> orbs := ShortOrbits(G,S,50);;
gap> List(orbs,Length);
[ 10, 10, 1, 10, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 10, 10, 10, 
  10, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 
  10, 1, 10, 10, 10, 1, 1, 10, 1, 10 ]
gap> ForAll(orbs,orb->IsNaturalSymmetricGroup(Action(G,orb)));
true
]]>
</Example>

<Q>Transferring</Q> 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>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
gap> IsInjective(v);
true
gap> IsSurjective(v);
false
gap> Image(v);
1(2) U 2(4) U 0(12)
gap> Difference(Integers,last);
4(12) U 8(12)
gap> v2 := RcwaMapping(Z_pi(2),ShallowCopy(Coefficients(v)));
<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

]]>
</Example>

Again, viewed as an rcwa mapping of the integers the commutator given at
the end of the example would not be surjective.

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:Twisting257CyclesToModulus32">
<Heading>
  Twisting 257-cycles into an rcwa mapping with modulus 32
</Heading>

We define an rcwa mapping <A>x</A> of order&nbsp;257 with modulus&nbsp;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>
<![CDATA[
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"); Display(x);

Rcwa mapping of Z with modulus 32

               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> Order(x);
257
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
]]>
</Example>

</Section>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<!-- #################################################################### -->

<Section Label="sec:ModuliOfPowers">
<Heading> The behaviour of the moduli of powers </Heading>

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>
<![CDATA[
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> List([0..3],i->Modulus(r^i));
[ 1, 9, 9, 1 ]
gap> List([0..9],i->Modulus(s^i));
[ 1, 9, 9, 27, 27, 27, 27, 27, 27, 1 ]
gap> g := RcwaMapping([[2,2,1],[1,4,1],[1,0,2],[2,2,1],[1,-4,1],[1,-2,1]]);;
gap> List([0..7],i->Modulus(g^i));
[ 1, 6, 12, 12, 12, 12, 6, 1 ]
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>

<Example>
<![CDATA[
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");
gap> 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
]]>
</Example>

</Section>

<!-- #################################################################### -->

<Section Label="sec:CollatzImagesAndPreImages">
<Heading> Images and preimages under the Collatz mapping </Heading>

We have a look at the images of the residue class 1(2)
under powers of the Collatz mapping.

<Example>
<![CDATA[
gap> T := RcwaMapping([[1,0,2],[3,1,2]]);; 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;
1(3) U 2(9) U 8(9)
gap> S5 := S4^T;
2(3) U 1(9) U 4(9)
gap> S6 := S5^T;
1(3) U 2(3)
gap> S7 := S6^T;
1(3) U 2(3)
]]>
</Example>

Thus the image gets stable after applying the mapping <M>T</M> for
the 6th time. Hence <M>T^6</M> maps the residue class 1(2) surjectively
onto the union of the residue classes 1(3) and 2(3), which is setwisely
stabilized by <M>T</M>.
Now we would like to determine the preimages of 1(3) resp. 2(3) in 1(2)
under <M>T^6</M>. The residue class 1(2) has to be the disjoint union of
these sets.

<Example>
<![CDATA[
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
]]>
</Example>

The images of the residue class 0(3) under powers of&nbsp;<M>T</M> look
as follows:

<Example>
<![CDATA[
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;
<union of 79 residue classes (mod 81)>
gap> S6 := S5^T;
Integers
gap> S7 := S6^T;
Integers
]]>
</Example>

Thus, every integer is the image of a multiple of&nbsp;3
under&nbsp;<M>T^6</M>. This means that it would be sufficient to prove the
Collatz conjecture for multiples of&nbsp;3.
We can obtain the corresponding result for multiples of&nbsp;5 as follows:

<Example>
<![CDATA[
gap> S := [ResidueClass(Integers,5,0)];
[ 0(5) ]
gap> for i in [1..12] do Add(S,S[i]^T); od;
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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 ]
]]>
</Example>

</Section>

<!-- #################################################################### -->

<Section Label="sec:FourTransitiveGroup">
<Heading>
  A group which acts 4-transitively on the positive integers
</Heading>

In this section, we would like to show that the group <M>G</M> generated
by the two wild mappings

<Example>
<![CDATA[
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);;
]]>
</Example>

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>
<![CDATA[
gap> List([a,a^-1,u,u^-1],DecreasingOn);
[ 1(2), 0(3), 0(5) U 2(5), 2(3) ]
gap> Union(last);
<union of 27 residue classes (mod 30)>
]]>
</Example>

We see that we cannot always choose such a group element from the set of
generators and their inverses -- otherwise the union would be
<C>Integers</C>.

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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 ...
<union of 87 residue classes (mod 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
]]>
</Example>

Finally, we have to deal with <Q>small</Q> integers. We use the notation for
the coefficients of rcwa mappings introduced at the beginning of this manual.
Let <M>c_{r(m)} &gt; a_{r(m)}</M>. Then we easily see that
<M>(a_{r(m)}n+b_{r(m)})/c_{r(m)} &gt; n</M> implies
<M>n &lt; b_{r(m)}/(c_{r(m)}-a_{r(m)})</M>.
Thus we can restrict our considerations to integers
<M>n &lt; b_{\rm max}</M>, where <M>b_{\rm max}</M> is the largest
second entry of a coefficient triple of one of the group elements
in our list:

<Example>
<![CDATA[
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
]]>
</Example>

Thus this upper bound is 56. The rest is easy -- all we have to do is
to check that the orbit containing&nbsp;1 contains also all other positive
integers less than or equal to&nbsp;56:

<Example>
<![CDATA[
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
]]>
</Example>

Checking 2-transitivity is computationally harder, and in the sequel we
will omit some steps which are in practice needed to find out
<Q>what&nbsp;to&nbsp;do</Q>.

The approach taken here is to show that the stabilizer of&nbsp;1
in&nbsp;<M>G</M> acts transitively on the set of positive integers greater
than&nbsp;1. We do this by similar means as used above for showing the
transitivity of the action of <M>G</M> on the positive integers.

We start by determining all products of at most 5 generators and their
inverses, which stabilize&nbsp;1 (taking at most 4-generator products would
not suffice!):

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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
]]>
</Example>

The resulting products have various different not quite small moduli:

<Example>
<![CDATA[
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 ] ]
]]>
</Example>

Similar as before, we determine for any of the above mappings the
residue classes whose elements larger than the largest <M>b_{r(m)}</M>
- coefficient of the respective mapping are mapped to smaller integers:

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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
]]>
</Example>

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>
<![CDATA[
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)>
<union of 6 residue classes (mod 777600)>
[  ]
]]>
</Example>

Similar as above, it remains to check that the <Q>small</Q> integers all
lie in the orbit containing&nbsp;2. Obviously, it is sufficient to check
that any integer greater than&nbsp;2 is mapped to a smaller one by some
suitably chosen element of the stabilizer under consideration:

<Example>
<![CDATA[
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 ]
]]>
</Example>

We have to treat 4 separately:

<Example>
<![CDATA[
gap> 1^(u*a*u^2*a^-1*u);
1
gap> 4^(u*a*u^2*a^-1*u);
3
]]>
</Example>

Now we know that any positive integer greater than&nbsp;1 lies in the same
orbit under the action of the stabilizer of&nbsp;1 in&nbsp;<M>G</M>
as&nbsp;2, thus that this stabilizer acts transitively on
<M>\mathbb{N} \setminus \{1\}</M>. But this means that we have established
the 2-transitivity of the action of <M>G</M> on&nbsp;<M>\mathbb{N}</M>. <P/>

In the following, we essentially repeat the above steps to show that
this action is indeed 3-transitive:

<Example>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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 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 break; fi;
>    od;
0(2) U 3(8) U 5(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)>
2164(259200) U 13414(259200) U 66964(259200) U 143014(259200) U 228964(259200)
2164(259200) U 66964(259200) U 228964(259200)
[  ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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;
[  ]
]]>
</Example>

The same for 4-transitivity:

<Example>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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) U 3(8) U 5(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)>
<union of 6 residue classes (mod 259200)>
<union of 14 residue classes (mod 777600)>
57406(259200) U 187006(259200) U 192676(259200) U 250276(259200)
<union of 8 residue classes (mod 777600)>
316606(777600) U 451876(777600) U 509476(777600) U 705406(777600) U 768676(
777600)
<union of 18 residue classes (mod 3110400)>
<union of 17 residue classes (mod 3110400)>
<union of 13 residue classes (mod 3110400)>
<union of 9 residue classes (mod 3110400)>
<union of 7 residue classes (mod 3110400)>
<union of 14 residue classes (mod 9331200)>
<union of 7 residue classes (mod 9331200)>
<union of 7 residue classes (mod 27993600)>
<union of 14 residue classes (mod 83980800)>
<union of 7 residue classes (mod 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;
[  ]
]]>
</Example>

There is even some evidence that the degree of transitivity of the action of
<M>G</M> on the positive integers is higher than&nbsp;4:

<Example>
<![CDATA[
gap> phi := EpimorphismFromFreeGroup(G);
[ a, u ] -> [ a, u ]
gap> F := Source(phi);
<free group on the generators [ a, u ]>
gap> words := 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 ]
]]>
</Example>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

</Section>

<!-- #################################################################### -->

<Section Label="sec:ThreeButNotFourTransitiveGroup">
<Heading>
  A group which acts 3-transitively, but not 4-transitively on Z
</Heading>

In this section, we would like to show that the wild group <M>G</M> generated
by the two tame mappings <M>n \mapsto n + 1</M> and <M>\tau_{1(2),0(4)}</M>
acts 3-transitively, but not 4-transitively on the set of integers.

<Example>
<![CDATA[
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 is not 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

]

]]>
</Example>

This group acts transitively on <M>\mathbb{Z}</M>, 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&nbsp;0
acts transitively on <M>\mathbb{Z} \setminus \{0\}</M>.

<Example>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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
]]>
</Example>

Similar as in the previous section, it remains to check that the integers
with <Q>small</Q> absolute value all lie in the orbit containing&nbsp;1 under
the action of the stabilizer of&nbsp;0:

<Example>
<![CDATA[
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
]]>
</Example>

Now we have to check for 3-transitivity. Since we cannot find for every
residue class an element of the pointwise stabilizer of <M>\{0,1\}</M>
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>
<![CDATA[
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>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

<Example>
<![CDATA[
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
]]>
</Example>

At this point we have established 3-transitivity.
It remains to check that the group <M>G</M> does not act 4-transitively.
We do this by checking that it is not transitive on 4-tuples (mod&nbsp;4).
Since <M>n</M>&nbsp;mod&nbsp;8 determines the image of <M>n</M> under
a generator of <M>G</M> (mod&nbsp;4), it suffices to compute (mod&nbsp;8):

<Example>
<![CDATA[
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
]]>
</Example>

This shows that <M>G</M> is not 4-transitive on <M>\mathbb{Z}</M>.
The corresponding calculation for 3-tuples looks as follows:

<Example>
<![CDATA[
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
]]>
</Example>

Needless to say that the latter kind of argumentation is not suitable
for proving, but only for disproving <M>k</M>-transitivity. 

</Section>

<!-- #################################################################### -->

<Section Label="sec:GrigorchukGroups">
<Heading>
  Grigorchuk groups
</Heading>

In this section, we show how construct finite quotients of the two infinite
periodic groups introduced by Rostislav Grigorchuk
in&nbsp;<Cite Key="Grigorchuk80"/> with the help of &RCWA;.

The first of these, nowadays known as <Q>Grigorchuk group</Q>, is
investigated in an example given on the &GAP; website -- see
<URL>http://www.gap-system.org/Doc/Examples/grigorchuk.html</URL>.

The &RCWA; package permits a simpler and more elegant construction
of the finite quotients of this group: The function <C>TopElement</C>
given on the mentioned webpage gets unnecessary, and the function
<C>SequenceElement</C> can be simplified as follows:

<Listing>
<![CDATA[
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;
]]>
</Listing>

<Alt Only="LaTeX">\pagebreak[4]</Alt>

The actual constructors for the generators are modified as follows:

<Listing>
<![CDATA[
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);
]]>
</Listing>

All computations given on the webpage can now be done just as with the
<Q>original</Q> construction of the quotients of the Grigorchuk group.
In the sequel, finite quotients of the second group introduced
in&nbsp;<Cite Key="Grigorchuk80"/> are constructed:

<Example>
<![CDATA[
gap> FourCycle := RcwaMapping((4,5,6,7),[4..7]);
<rcwa mapping of Z with modulus 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));;
]]>
</Example>

We can do similar things as shown in the example on the &GAP; webpage
for the <Q>first</Q> Grigorchuk group:

<Example>
<![CDATA[
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])); # Isomorphic 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 ]
]]>
</Example>

<Alt Only="HTML">&nbsp;</Alt>

</Section>

<!-- #################################################################### -->

</Chapter>

<!-- #################################################################### -->
