chap3.txt

  
  3 Residue-Class-Wise Affine Groups
  
  In  this  chapter,  we  describe  how to construct residue-class-wise affine
  groups and how to compute with them.
  
  
  3.1 Constructing residue-class-wise affine groups
  
  As  any other groups in GAP, residue-class-wise affine (rcwa-) groups can be
  constructed by Group, GroupByGenerators or GroupWithGenerators.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5));
    <rcwa group over Z with 2 generators>
    gap> IsTame(G); Size(G); IsSolvable(G); IsPerfect(G);
    true
    infinity
    false
    false
    
  
  
  An  rcwa  group  isomorphic  to  a given group can be obtained by taking the
  image of a faithful rcwa representation:
  
  3.1-1 IsomorphismRcwaGroup
  
  IsomorphismRcwaGroup( G, R )  attribute
  IsomorphismRcwaGroup( G )  attribute
  Returns:  a   monomorphism  from  the  group  G  to RCWA(R)  or  to RCWA(ℤ),
            respectively.
  
  The  best-supported case is R = ℤ. Currently there are methods available for
  finite  groups,  for free products of finite groups and for free groups. The
  method  for  free products of finite groups uses the Table-Tennis Lemma (cf.
  e.g.  Section II.B.  in [dlH00]),  and  the  method  for free groups uses an
  adaptation  of the construction given on page 27 in [dlH00] from PSL(2,ℂ) to
  RCWA(ℤ).
  
    Example  
    
    gap> F := FreeProduct(Group((1,2)(3,4),(1,3)(2,4)),Group((1,2,3)),
    >                     SymmetricGroup(3));
    <fp group on the generators [ f1, f2, f3, f4, f5 ]>
    gap> IsomorphismRcwaGroup(F);
    [ f1, f2, f3, f4, f5 ] -> [ <rcwa permutation of Z with modulus 12>,
      <rcwa permutation of Z with modulus 24>,
      <rcwa permutation of Z with modulus 12>,
      <rcwa permutation of Z with modulus 72>,
      <rcwa permutation of Z with modulus 36> ]
    gap> IsomorphismRcwaGroup(FreeGroup(2));
    [ f1, f2 ] -> [ <wild rcwa permutation of Z with modulus 8>,
      <wild rcwa permutation of Z with modulus 8> ]
    gap> F2 := Image(last);
    <wild rcwa group over Z with 2 generators>
    
  
  
  Further, new rcwa groups can be constructed from given ones by taking direct
  products  and  by  taking  wreath  products  with  finite groups or with the
  infinite cyclic group:
  
  3.1-2 DirectProduct
  
  DirectProduct( G1, G2, ... )  method
  Returns:  an  rcwa group isomorphic to the direct product of the rcwa groups
            over ℤ given as arguments.
  
  There  is  certainly no unique or canonical way to embed a direct product of
  rcwa  groups  into  RCWA(ℤ). This method chooses to embed the groups G1, G2,
  G3 ...  via  restrictions  by  n ↦ mn, n ↦ mn+1, n ↦ mn+2 ... (→ Restriction
  (3.1-6)), where m denotes the number of groups given as arguments.
  
    Example  
    
    gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;
    gap> F2xF2 := DirectProduct(F2,F2);
    <wild rcwa group over Z with 4 generators>
    gap> Image(Projection(F2xF2,1)) = F2;
    true
    
  
  
  
  3.1-3  WreathProduct  (for an rcwa group over Z, with a permutation group or
  (ℤ,+))
  
  WreathProduct( G, P )  method
  WreathProduct( G, Z )  method
  Returns:  an rcwa group isomorphic to the wreath product of the rcwa group G
            over ℤ  with  the  finite permutation group P or with the infinite
            cyclic group Z, respectively.
  
  The  first-mentioned  method embeds the NrMovedPoints(P)th direct power of G
  using  the  method  for  DirectProduct, and lets the permutation group P act
  naturally  on  the  set  of  residue  classes  modulo  NrMovedPoints(P). The
  second-mentioned method restricts (→ Restriction (3.1-6)) the group G to the
  residue class 3(4), and maps the generator of the infinite cyclic group Z to
  ClassTransposition(0,2,1,2) * ClassTransposition(0,2,1,4).
  
    Example  
    
    gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;
    gap> F2wrA5 := WreathProduct(F2,AlternatingGroup(5));;
    gap> Embedding(F2wrA5,1);
    [ <wild rcwa permutation of Z with modulus 8>,
      <wild rcwa permutation of Z with modulus 8> ] ->
    [ <wild rcwa permutation of Z with modulus 40>,
      <wild rcwa permutation of Z with modulus 40> ]
    gap> Embedding(F2wrA5,2);
    [ (1,2,3,4,5), (3,4,5) ] -> [ ( 0(5), 1(5), 2(5), 3(5), 4(5) ), 
      ( 2(5), 3(5), 4(5) ) ]
    gap> ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1)));
    <wild rcwa group over Z with 2 generators>
    gap> Embedding(ZwrZ,1);
    [ ClassShift( Z ) ] ->
    [ <tame rcwa permutation of Z with modulus 4, of order infinity> ]
    gap> Embedding(ZwrZ,2);
    [ ClassShift( Z ) ] -> [ <wild rcwa permutation of Z with modulus 4> ]
    
  
  
  Also,  rcwa  groups  can  be  obtained  as  particular  extensions of finite
  permutation groups:
  
  3.1-4 MergerExtension
  
  MergerExtension( G, points, point )  operation
  Returns:  roughly  spoken,  an  extension of G by an involution which merges
            points into point.
  
  The  arguments  of  this  operation  are a finite permutation group G, a set
  points of points moved by G and a single point point moved by G which is not
  in points.
  
  Let  n  be  the  largest moved point of G, and let H be the tame subgroup of
  CT(ℤ)  which  respects  the partition mathcalP of ℤ into the residue classes
  (mod n),  and  which  acts  on  mathcalP  as G acts on {1, dots, n}. Further
  assume that points = {p_1, dots, p_k} and point = p, and put r_i := p_i-1, i
  =  1,  dots,  k  and  r  :=  p-1.  Now  let  σ  be  the product of the class
  transpositions  τ_r_i(n),r+(i-1)n(kn), i = 1, dots, k. The group returned by
  this  operation  is  the  extension  of  H  by the involution σ. -- On first
  reading,  this  may  look  a  little complicated, but really the code of the
  method is only about half as long as this description.
  
    Example  
    
    gap> # First example -- a group isomorphic to PSL(2,Z):
    gap> G := MergerExtension(Group((1,2,3)),[1,2],3);
    <rcwa group over Z with 2 generators>
    gap> Size(G); 
    infinity
    gap> GeneratorsOfGroup(G);
    [ ( 0(3), 1(3), 2(3) ), ( 0(3), 2(6) ) ( 1(3), 5(6) ) ]
    gap> B := Ball(G,One(G),6:Spheres);;
    gap> List(B,Length);
    [ 1, 3, 4, 6, 8, 12, 16 ]
    gap> #
    gap> # Second example -- a group isomorphic to Thompson's group V:
    gap> G := MergerExtension(Group((1,2,3,4),(1,2)),[1,2],3);
    <rcwa group over Z with 3 generators>
    gap> Size(G);
    infinity
    gap> GeneratorsOfGroup(G);
    [ ( 0(4), 1(4), 2(4), 3(4) ), ( 0(4), 1(4) ),
      ( 0(4), 2(8) ) ( 1(4), 6(8) ) ]
    gap> B := Ball(G,One(G),6:Spheres);;
    gap> List(B,Length);
    [ 1, 4, 11, 28, 69, 170, 413 ]
    gap> G = Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],
    >                   ClassTransposition));
    true
    
  
  
  It is also possible to build an rcwa group from a list of residue classes:
  
  3.1-5 GroupByResidueClasses
  
  GroupByResidueClasses( classes )  function
  Returns:  the  group  which  is  generated by all class transpositions which
            interchange disjoint residue classes in classes.
  
  The argument classes must be a list of residue classes.
  
  If  the  residue classes in classes are pairwise disjoint, then the returned
  group  is  the  symmetric  group  on  classes. If any two residue classes in
  classes intersect non-trivially, then the returned group is trivial. In many
  other cases, the returned group is infinite.
  
    Example  
    
    gap> G := GroupByResidueClasses(List([[0,2],[0,4],[1,4],[2,4],[3,4]],
    >                                    ResidueClass));
    <rcwa group over Z with 8 generators>
    gap> H := Group(List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],
    >                    ClassTransposition)); # Thompson's group V
    <(0(2),1(2)),(1(2),2(4)),(0(2),1(4)),(1(4),2(4))>
    gap> G = H;
    true
    
  
  
  Various  ways  to  construct  rcwa groups are based on certain monomorphisms
  from the group RCWA(R) into itself. Examples are the constructions of direct
  products  and  wreath  products described above. The support of the image of
  such a monomorphism is the image of a given injective rcwa mapping. For this
  reason,  these  monomorphisms  are  called  restriction  monomorphisms.  The
  following operation computes images of rcwa mappings and -groups under these
  embeddings of RCWA(R) into itself:
  
  
  3.1-6  Restriction  (of  an  rcwa  mapping  or  -group, by an injective rcwa
  mapping)
  
  Restriction( g, f )  operation
  Restriction( G, f )  operation
  Returns:  the restriction of the rcwa mapping g (respectively the rcwa group
            G) by the injective rcwa mapping f.
  
  By definition, the restriction g_f of an rcwa mapping g by an injective rcwa
  mapping f  is the unique rcwa mapping which satisfies the equation f ⋅ g_f =
  g  ⋅  f  and which fixes the complement of the image of f pointwise. If f is
  bijective, the restriction of g by f is just the conjugate of g under f.
  
  The restriction of an rcwa group G by an injective rcwa mapping f is defined
  as  the group whose elements are the restrictions of the elements of G by f.
  The  restriction  of G  by f acts on the image of f and fixes its complement
  pointwise.
  
    Example  
    
    gap> F2tilde := Restriction(F2,RcwaMapping([[5,3,1]]));
    <wild rcwa group over Z with 2 generators>
    gap> Support(F2tilde);
    3(5)
    
  
  
  
  3.1-7 Induction (of an rcwa mapping or -group, by an injective rcwa mapping)
  
  Induction( g, f )  operation
  Induction( G, f )  operation
  Returns:  the  induction  of the rcwa mapping g (respectively the rcwa group
            G) by the injective rcwa mapping f.
  
  Induction    is   the   right   inverse   of   restriction,   i.e.   it   is
  Induction(Restriction(g,f),f) = g and Induction(Restriction(G,f),f) = G. The
  mapping g  respectively  the  group G must not move points outside the image
  of f.
  
    Example  
    
    gap> Induction(F2tilde,RcwaMapping([[5,3,1]])) = F2;
    true
    
  
  
  Once  having constructed an rcwa group, it is sometimes possible to obtain a
  smaller generating set by the operation SmallGeneratingSet.
  
  There  are  methods for the operations View, Display, Print and String which
  are applicable to rcwa groups.
  
  Basic attributes of an rcwa group which are derived from the coefficients of
  its  elements  are Modulus, Multiplier, Divisor and PrimeSet. The modulus of
  an  rcwa  group  is  the  lcm  of  the moduli of its elements if such an lcm
  exists,  i.e.  if  the  group  is  tame,  and  0  otherwise.  The multiplier
  respectively  divisor  of  an  rcwa  group  is  the  lcm  of the multipliers
  respectively  divisors  of  its  elements  in  case such an lcm exists and ∞
  otherwise.  The prime set of an rcwa group is the union of the prime sets of
  its  elements.  There  are shorthands Mod, Mult and Div defined for Modulus,
  Multiplier  and  Divisor,  respectively.  An rcwa group is called class-wise
  translating,  integral or class-wise order-preserving if all of its elements
  are     so.     There    are    corresponding    methods    available    for
  IsClassWiseTranslating,  IsIntegral and IsClassWiseOrderPreserving. There is
  a  property  IsSignPreserving,  which  indicates  whether a given rcwa group
  over ℤ  acts  on  the  set of nonnegative integers. The latter holds for any
  subgroup of CT(ℤ) (cf. below).
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,6),
    >               ClassReflection(2,4));
    <rcwa group over Z with 3 generators>
    gap> List([Modulus,Multiplier,Divisor,PrimeSet,IsClassWiseTranslating,
    >          IsIntegral,IsClassWiseOrderPreserving,IsSignPreserving],f->f(G));
    [ 24, 2, 2, [ 2, 3 ], false, false, false, false ]
    
  
  
  All  rcwa  groups  over a ring R are subgroups of RCWA(R). The group RCWA(R)
  itself  is  not  finitely generated, thus cannot be constructed as described
  above. It is handled as a special case:
  
  3.1-8 RCWA
  
  RCWA( R )  function
  Returns:  the group RCWA(R) of all residue-class-wise affine permutations of
            the ring R.
  
    Example  
    
    gap> RCWA_Z := RCWA(Integers);
    RCWA(Z)
    gap> IsSubgroup(RCWA_Z,G);
    true
    
  
  
  Examples  of  rcwa  permutations  can  be  obtained via Random(RCWA(R)), see
  Section 3.5. The number of conjugacy classes of RCWA(ℤ) of elements of given
  order  is known, cf. Corollary 2.7.1 (b) in [Koh05]. It can be determined by
  the function NrConjugacyClassesOfRCWAZOfOrder:
  
    Example  
    
    gap> List([2,105],NrConjugacyClassesOfRCWAZOfOrder);
    [ infinity, 218 ]
    
  
  
  We  denote  the  group which is generated by all class transpositions of the
  ring R by CT(R). This group is handled as a special case as well:
  
  3.1-9 CT
  
  CT( R )  function
  CT( P, Integers )  function
  Returns:  the  group CT(R) which is generated by all class transpositions of
            the  ring R, respectively, the group CT(P,ℤ) which is generated by
            all  class  transpositions  of ℤ which interchange residue classes
            whose moduli have only prime factors in the finite set P.
  
    Example  
    
    gap> CT_Z := CT(Integers);
    CT(Z)
    gap> IsSimple(CT_Z); # One of a number of stored attributes/properties.
    true
    gap> V := CT([2],Integers);
    CT_[ 2 ](Z)
    gap> GeneratorsOfGroup(V);
    [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 0(2), 1(4) ), ( 1(4), 2(4) ) ]
    gap> G := CT([2,3],Integers); 
    CT_[ 2, 3 ](Z)
    gap> GeneratorsOfGroup(G);
    [ ( 0(2), 1(2) ), ( 0(3), 1(3) ), ( 1(3), 2(3) ), ( 0(2), 1(4) ), 
      ( 0(2), 5(6) ), ( 0(3), 1(6) ) ]
    
  
  
  The group CT(ℤ) has an outer automorphism which is given by conjugation with
  n  ↦  -n - 1. This automorphism can be applied to an rcwa mapping of ℤ or to
  an  rcwa  group over ℤ by the operation Mirrored. The group Mirrored(G) acts
  on  the  nonnegative  integers  as G acts on the negative integers, and vice
  versa.
  
    Example  
    
    gap> ct := ClassTransposition(0,2,1,6);
    ( 0(2), 1(6) )
    gap> Mirrored(ct);
    ( 1(2), 4(6) )
    gap> G := Group(List([[0,2,1,2],[0,3,2,3],[2,4,1,6]],ClassTransposition));;
    gap> ShortOrbits(G,[-100..100],100);
    [ [ 0, 1, 2, 3, 4, 5 ] ]
    gap> ShortOrbits(Mirrored(G),[-100..100],100);
    [ [ -6, -5, -4, -3, -2, -1 ] ]
    
  
  
  Under the hypothesis that CT(ℤ) is the setwise stabilizer of ℕ_0 in RCWA(ℤ),
  the  elements  of CT(ℤ) with modulus dividing a given positive integer m are
  parametrized by the ordered partitions of ℤ into m residue classes. The list
  of   these   elements   for   given  m  can  be  obtained  by  the  function
  AllElementsOfCTZWithGivenModulus,  and  the numbers of such elements for m ≤
  24 are stored in the list NrElementsOfCTZWithGivenModulus.
  
    Example  
    
    gap> NrElementsOfCTZWithGivenModulus{[1..8]};
    [ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680 ]
    
  
  
  The  number of conjugacy classes of CT(ℤ) of elements of given order is also
  known  under  the  hypothesis that CT(ℤ) is the setwise stabilizer of ℕ_0 in
  RCWA(ℤ).      It      can      be     determined     by     the     function
  NrConjugacyClassesOfCTZOfOrder.
  
  
  3.2 Basic routines for investigating residue-class-wise affine groups
  
  In  the  previous  section  we  have  seen how to construct rcwa groups. The
  purpose  of  this  section  is  to describe how to obtain information on the
  structure  of  an  rcwa  group and on its action on the underlying ring. The
  easiest  way to get a little (but really only a very little!) information on
  the   group   structure   is   a   dedicated   method   for   the  operation
  StructureDescription:
  
  3.2-1 StructureDescription
  
  StructureDescription( G )  method
  Returns:  a  string  which sometimes gives a little glimpse of the structure
            of the rcwa group G.
  
  The  attribute  StructureDescription  for finite groups is documented in the
  GAP  Reference  Manual.  Therefore  we  describe  here only issues which are
  specific to infinite groups, and in particular to rcwa groups.
  
  Wreath  products  are denoted by wr, and free products are denoted by *. The
  infinite  cyclic group (ℤ,+) is denoted by Z, the infinite dihedral group is
  denoted  by D0  and  free  groups  of rank 2,3,4,dots are denoted by F2, F3,
  F4, dots. While for finite groups the symbol . is used to denote a non-split
  extension,  for  rcwa groups in general it stands for an extension which may
  be  split  or  not. For wild groups in most cases it happens that there is a
  large  section  on  which  no  structural  information can be obtained. Such
  sections  of  the  group with unknown structure are denoted by <unknown>. In
  general,  the  structure  of  a  section  denoted  by  <unknown> can be very
  complicated and very difficult to exhibit.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(0,5));;
    gap> StructureDescription(G);
    "(Z x Z x Z x Z x Z x Z x Z) . (C2 x S7)"
    gap> G := Group(ClassTransposition(0,2,1,4),
    >               ClassShift(2,4),ClassReflection(1,2));;
    gap> StructureDescription(G:short);
    "Z^2.((S3xS3):2)"
    gap> F2 := Image(IsomorphismRcwaGroup(FreeGroup(2)));;
    gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(3),
    >                                                    CyclicGroup(2))));;
    gap> G := DirectProduct(PSL2Z,F2);
    <wild rcwa group over Z with 4 generators>
    gap> StructureDescription(G);
    "(C3 * C2) x F2"
    gap> G := WreathProduct(G,CyclicGroup(IsRcwaGroupOverZ,infinity));
    <wild rcwa group over Z with 5 generators>
    gap> StructureDescription(G);
    "((C3 * C2) x F2) wr Z"
    gap> Collatz := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);;
    gap> G := Group(Collatz,ClassShift(0,1));;
    gap> StructureDescription(G:short);
    "<unknown>.Z"
    
  
  
  The  extent  to  which  the  structure  of  an  rcwa  group can be exhibited
  automatically  is  severely  limited. In general, one can find out much more
  about  the  structure  of a given rcwa group in an interactive session using
  the  functionality  described  in  the rest of this section and elsewhere in
  this manual.
  
  The  order  of  an rcwa group can be computed by the operation Size. An rcwa
  group  is  finite  if  and  only  if it is tame and its action on a suitably
  chosen  respected  partition  (see RespectedPartition  (3.4-1)) is faithful.
  Hence  the  problem  of  computing the order of an rcwa group reduces to the
  problem  of  deciding whether it is tame, the problem of deciding whether it
  acts  faithfully  on  a respected partition and the problem of computing the
  order of the finite permutation group induced on the respected partition.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,3,2,3),
    >               ClassReflection(0,5));
    <rcwa group over Z with 3 generators>
    gap> Size(G);
    46080
    
  
  
  For  a  finite  rcwa  group,  an  isomorphism  to a permutation group can be
  computed by IsomorphismPermGroup:
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,3,1,3));;
    gap> IsomorphismPermGroup(G);
    [ ( 0(2), 1(2) ), ( 0(3), 1(3) ) ] -> [ (1,2)(3,4)(5,6), (1,2)(4,5) ]
    
  
  
  In  general  the  membership  problem  for  rcwa  groups  is algorithmically
  unsolvable,  see  Corollary 4.5  in [Koh10]. A consequence of this is that a
  membership test g in G may run into an infinite loop if the rcwa permutation
  g  is  not  an  element  of  the  rcwa group G. For tame rcwa groups however
  membership  can always be decided. For wild rcwa groups, membership can very
  often  be decided quite quick as well, but -- as said -- not always. Anyway,
  if  g  is  contained in G, the membership test will eventually always return
  true,  provided  that  there  are  sufficient  computing resources available
  (memory etc.).
  
  On  Info  level 2  of  InfoRCWA  the membership test provides information on
  reasons why the given rcwa permutation is an element of the given rcwa group
  or not.
  
  The  membership  test  g in G recognizes an option OrbitLengthBound. If this
  option is set, it returns false once it has computed balls of size exceeding
  OrbitLengthBound  about  1  and  g in G, and these balls are still disjoint.
  Note  however  that  due  to the algorithmic unsolvability of the membership
  problem, RCWA has no means to check the correctness of such bound in a given
  case.  So  the  correct  use  of  this  option has to remain within the full
  responsibility of the user.
  
    Example  
    
    gap> G := Group(ClassShift(0,3),ClassTransposition(0,3,2,6));;
    gap>  ClassShift(2,6)^7 * ClassTransposition(0,3,2,6)
    >   * ClassShift(0,3)^-3 in G;
    true
    gap> ClassShift(0,1) in G;
    false
    
  
  
  The  conjugacy  problem for rcwa groups is difficult, and RCWA provides only
  methods to solve it in some reasonably easy cases.
  
    Example  
    
    gap> IsConjugate(RCWA(Integers),
    >                ClassTransposition(0,2,1,4),ClassShift(0,1));
    false
    gap> IsConjugate(CT(Integers),ClassTransposition(0,2,1,6),
    >                             ClassTransposition(1,4,0,8));
    true
    gap> g := RepresentativeAction(CT(Integers),ClassTransposition(0,2,1,6),
    >                                           ClassTransposition(1,4,0,8));
    <rcwa permutation of Z with modulus 48>
    gap> ClassTransposition(0,2,1,6)^g = ClassTransposition(1,4,0,8);
    true
    
  
  
  There  is a property IsTame which indicates whether an rcwa group is tame or
  not:
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(1,3));;
    gap> H := Group(ClassTransposition(0,2,1,6),ClassShift(1,3));;
    gap> IsTame(G);
    true
    gap> IsTame(H);
    false
    
  
  
  For  tame  rcwa  groups,  there  are  methods  for  IsSolvable and IsPerfect
  available,  and  usually  derived  subgroups  and  subgroup  indices  can be
  computed  as  well. Linear representations of tame groups over the rationals
  can  be  determined  by the operation IsomorphismMatrixGroup. Testing a wild
  group  for  solvability or perfectness is currently not always feasible, and
  wild   groups   have   in  general  no  faithful  finite-dimensional  linear
  representations.  There  is  a  method  for  Exponent available, which works
  basically for any rcwa group.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,4),ClassShift(1,2));;
    gap> IsPerfect(G);
    false
    gap> IsSolvable(G);
    true
    gap> D1 := DerivedSubgroup(G);; D2 := DerivedSubgroup(D1);;
    gap> IsAbelian(D2);
    true
    gap> Index(G,D1); Index(D1,D2);
    infinity
    9
    gap> StructureDescription(G); StructureDescription(D1);
    "(Z x Z x Z) . S3"
    "(Z x Z) . C3"
    gap> Q := D1/D2;
    Group([ (), (1,2,4)(3,5,7)(6,8,9), (1,3,6)(2,5,8)(4,7,9) ])
    gap> StructureDescription(Q); 
    "C3 x C3"
    gap> Exponent(G);
    infinity
    gap> phi := IsomorphismMatrixGroup(G);;
    gap> Display(Image(phi,ClassTransposition(0,2,1,4)));
    [ [     0,     0,   1/2,  -1/2,     0,     0 ], 
      [     0,     0,     0,     1,     0,     0 ], 
      [     2,     1,     0,     0,     0,     0 ], 
      [     0,     1,     0,     0,     0,     0 ], 
      [     0,     0,     0,     0,     1,     0 ], 
      [     0,     0,     0,     0,     0,     1 ] ]
    
  
  
  When  investigating  a  group,  a  basic task is to find relations among the
  generators:
  
  3.2-2 EpimorphismFromFpGroup
  
  EpimorphismFromFpGroup( G, r )  method
  EpimorphismFromFpGroup( G, r, maxparts )  method
  Returns:  an  epimorphism  from  a  finitely  presented  group  to  the rcwa
            group G.
  
  The  argument  r  is the search radius, i.e. the radius of the ball around 1
  which  is  scanned  for  relations.  In  general, the larger r is chosen the
  smaller the kernel of the returned epimorphism is. If the group G has finite
  presentations,  the  kernel will in principle get trivial provided that r is
  chosen  large  enough. If the optional argument maxparts is given, it limits
  the search space to elements with at most maxparts affine parts.
  
    Example  
    
    gap> a := ClassTransposition(2,4,3,4);;
    gap> b := ClassTransposition(4,6,8,12);;
    gap> c := ClassTransposition(3,4,4,6);;
    gap> G := SparseRep(Group(a,b,c));
    <(2(4),3(4)),(4(6),8(12)),(3(4),4(6))>
    gap> phi := EpimorphismFromFpGroup(G,6);
    #I  there are 3 generators and 12 relators of total length 330
    #I  there are 3 generators and 11 relators of total length 312
    [ a, b, c ] -> [ ( 2(4), 3(4) ), ( 4(6), 8(12) ), ( 3(4), 4(6) ) ]
    gap> RelatorsOfFpGroup(Source(phi));
    [ a^2, b^2, c^2, (b*c)^3, (a*b)^6, (a*b*c*b)^3, (a*c*b*c)^3, 
      (a*b*a*c)^12, ((a*b)^2*a*c)^12, (a*b*(a*c)^2)^12, (a*b*c*a*c*b)^12 ]
    
  
  
  A related very common task is to factor group elements into generators:
  
  3.2-3 PreImagesRepresentative
  
  PreImagesRepresentative( phi, g )  method
  Returns:  a   representative   of  the  set  of  preimages  of g  under  the
            epimorphism phi from a free group to an rcwa group.
  
  The  epimorphism  phi  must  map  the  generators  of  the free group to the
  generators of the rcwa group one-by-one.
  
  This  method  can  be  used  for  factoring  elements  of  rcwa  groups into
  generators. The implementation is based on RepresentativeActionPreImage, see
  RepresentativeAction (3.3-10).
  
  Quite  frequently,  computing several preimages is not harder than computing
  just  one,  i.e.  often  several  preimages  are  found  simultaneously. The
  operation  PreImagesRepresentatives  takes  care  of this. It takes the same
  arguments  as  PreImagesRepresentative  and  returns a list of preimages. If
  multiple  preimages  are  found,  their  quotients  give  rise to nontrivial
  relations among the generators of the image of phi.
  
    Example  
    
    gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a");
    gap> b := ClassShift(0,1);; SetName(b,"b");
    gap> G := Group(a,b);; # G = <<Collatz permutation>, n -> n + 1>
    gap> phi := EpimorphismFromFreeGroup(G);;
    gap> g := Comm(a^2*b^4,a*b^3); # a sample element to be factored
    <rcwa permutation of Z with modulus 8>
    gap> PreImagesRepresentative(phi,g); # -> a factorization of g
    b^-3*(b^-1*a^-1)^2*b^3*a*b^-1*a*b^3
    gap> g = b^-4*a^-1*b^-1*a^-1*b^3*a*b^-1*a*b^3; # check
    true
    gap> g := Comm(a*b,Comm(a,b^3));
    <rcwa permutation of Z with modulus 8>
    gap> pre := PreImagesRepresentatives(phi,g);
    [ (b^-1*a^-1)^2*b^2*(b*a)^2*b^-2, b^-1*(a^-1*b)^2*b^2*(a*b^-1)^2*b^-1 ]
    gap> rel := pre[1]/pre[2]; # -> a nontrivial relation
    (b^-1*a^-1)^2*b^3*a*b^2*a^-1*b^-2*(b^-1*a)^2*b
    gap> rel^phi;
    IdentityMapping( Integers )
    
  
  
  
  3.3 The natural action of an rcwa group on the underlying ring
  
  Knowing  a  natural  permutation  representation  of  a  group usually helps
  significantly  in computing in it and in obtaining results on its structure.
  This  holds  particularly  for  the  natural  action of an rcwa group on its
  underlying ring. In this section we describe RCWA's functionality related to
  this action.
  
  The  support,  i.e.  the  set  of  moved  points,  of  an  rcwa group can be
  determined  by  Support  or  MovedPoints  (these  are synonyms). Testing for
  transitivity on the underlying ring or on a union of residue classes thereof
  is often feasible:
  
    Example  
    
    gap> G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));;
    gap> IsTransitive(G,Integers);
    true
    
  
  
  Groups  generated  by class transpositions of the integers act on the set of
  nonnegative        integers.        There        is        a        property
  IsTransitiveOnNonnegativeIntegersInSupport(G)  which  indicates whether such
  group  acts  transitively on the set of nonnegative integers in its support.
  Since  such transitivity test is a computationally hard problem, methods may
  fail.   If   IsTransitiveOnNonnegativeIntegersInSupport   returns  true,  an
  attribute  TransitivityCertificate  is  set;  this  is  a  record containing
  components  phi,  words,  classes,  smallpointbound,  status and complete as
  follows:
  
  phi
        is  an  epimorphism  from  a  free group to G which maps generators to
        generators.
  
  words, classes
        two  lists.  --  words[i]  is  a preimage under phi of an element of G
        which  maps  all  sufficiently  large positive integers in the residue
        classes classes[i] to smaller nonnegative integers.
  
  smallpointbound
        in  addition to finding a list of group elements g_i such that for any
        large enough integer n in the support of G there is some g_i such that
        n^g_i  <  n, for verifying transitivity it was necessary to check that
        all integers less than or equal to smallpointbound in the support of G
        lie in the same orbit.
  
  status
        the  string  "transitive"  in  case  all  checks  have  been completed
        successfully.
  
  complete
        true in case all checks have been completed successfully.
  
  Parts  of  this information for possibly intransitive groups can be obtained
  by  the  operation TryToComputeTransitivityCertificate(G,searchlimit), where
  searchlimit  is the maximum radius about a point within which smaller points
  are  searched  and  taken  into  consideration. This operation interprets an
  option  abortdensity  --  if set, the operation returns the data computed so
  far once the density of the set of positive integers in the support of G for
  which  no group element is found which maps them to smaller integers reaches
  or  drops  below  abortdensity. A simplified certificate can be obtained via
  SimplifiedCertificate(cert).
  
    Example  
    
    gap> G := Group(List([[0,2,1,2],[0,3,2,3],[1,2,2,4]],
    >                    ClassTransposition));
    <(0(2),1(2)),(0(3),2(3)),(1(2),2(4))>
    gap> IsTransitiveOnNonnegativeIntegersInSupport(G);
    true
    gap> TransitivityCertificate(G);
    rec( 
      classes := [ [ 1(2) ], [ 2(6) ], [ 6(12), 10(12) ], [ 0(12) ], 
          [ 4(12) ] ], complete := true, 
      phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) 
         ], smallpointbound := 4, status := "transitive", 
      words := [ a, b, c, b*c, a*b ] )
    gap> SimplifiedCertificate(last);
    rec( classes := [ [ 1(2) ], [ 2(4) ], [ 4(12) ], [ 0(12), 8(12) ] ], 
      complete := true, 
      phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 0(3), 2(3) ), ( 1(2), 2(4) ) 
         ], smallpointbound := 4, status := "transitive", 
      words := [ a, c, a*b, b*c ] )
    gap> G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],
    >                    ClassTransposition));              # '3n+1 group'
    <(0(2),1(2)),(1(2),2(4)),(1(4),2(6))>
    gap> cert := TryToComputeTransitivityCertificate(G,10);
    rec(
      classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], 
          [ 0(24), 16(24) ] ], complete := false, 
      phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) 
         ], remaining := [ 12(48), 28(48), 52(96), 84(96) ], 
      smallpointbound := 42, status := "unclear", 
      words := [ a, b, (a*c)^2*b*a*b, c, a*c*b ] )
    gap> Union(Flat(cert.classes));
    <union of 90 residue classes (mod 96) (6 classes)>
    gap> Difference(Integers,Union(Flat(cert.classes)));
    12(48) U 28(48) U 52(96) U 84(96)
    gap> cert := TryToComputeTransitivityCertificate(G,20); # try larger bound
    rec(
      classes := [ [ 1(2) ], [ 2(4) ], [ 4(32) ], [ 8(24), 44(48), 20(96) ], 
          [ 0(24), 16(24) ], [ 12(768), 268(768) ], [ 28(768), 540(768) ] ], 
      complete := false, 
      phi := [ a, b, c ] -> [ ( 0(2), 1(2) ), ( 1(2), 2(4) ), ( 1(4), 2(6) ) 
         ], 
      remaining := [ 52(96), 84(96), 60(192), 108(192), 124(192), 172(192), 
          76(384), 204(384), 220(384), 348(384), 156(768), 396(768), 
          412(768), 652(768) ], smallpointbound := 1074, status := "unclear", 
      words := [ a, b, (a*c)^2*b*a*b, c, a*c*b, (a*c)^3*b*c*b*a*b, 
          (a*c)^4*b*a*b*a*b ] )
    gap> Difference(Integers,Union(Flat(cert.classes)));
    <union of 44 residue classes (mod 768) (14 classes)>
    gap> Intersection([0..100],last);
    [ 52, 60, 76, 84 ]
    
  
  
  Further,  there  are  methods  to compute orbits under the action of an rcwa
  group:
  
  
  3.3-1 Orbit (for an rcwa group and either a point or a set)
  
  Orbit( G, point )  method
  Orbit( G, set )  method
  Returns:  the  orbit  of  the point point respectively the set set under the
            natural action of the rcwa group G on its underlying ring.
  
  The  second  argument can either be an element or a subset of the underlying
  ring  of  the rcwa group G. Since orbits under the action of rcwa groups can
  be finite or infinite, and since infinite orbits are not necessarily residue
  class unions, the orbit may either be returned in the form of a list, in the
  form  of  a  residue  class  union  or in the form of an orbit object. It is
  possible to loop over orbits returned as orbit objects, they can be compared
  and  there  is  a  membership  test for them. However note that equality and
  membership for such orbits cannot always be decided.
  
    Example  
    
    gap> G := Group(ClassShift(0,2),ClassTransposition(0,3,1,3));
    <rcwa group over Z with 2 generators>
    gap> Orbit(G,0);
    Z \ 5(6)
    gap> Orbit(G,5);
    [ 5 ]
    gap> Orbit(G,ResidueClass(0,2));
    [ 0(2), 1(6) U 2(6) U 3(6), 1(3) U 3(6), 0(3) U 1(6), 0(3) U 4(6), 
      1(3) U 0(6), 0(3) U 2(6), 0(6) U 1(6) U 2(6), 2(6) U 3(6) U 4(6), 
      1(3) U 2(6) ]
    gap> Length(Orbit(G,ResidueClass(0,4)));
    80
    gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(0,2,1,4),
    >               ClassReflection(0,3));
    <rcwa group over Z with 3 generators>
    gap> orb := Orbit(G,2);
    <orbit of 2 under <wild rcwa group over Z with 3 generators>>
    gap> 1015808 in orb;
    true
    gap> First(orb,n->ForAll([n,n+2,n+6,n+8,n+30,n+32,n+36,n+38],IsPrime));
    -19
    
  
  
  3.3-2 GrowthFunctionOfOrbit
  
  GrowthFunctionOfOrbit( G, n, r_max, size_max )  operation
  GrowthFunctionOfOrbit( orb, r_max, size_max )  method
  Returns:  a  list whose (r+1)-th entry is the size of the sphere of radius r
            about  n under the action of the group G, where the argument r_max
            is   the  largest  possible  radius  to  be  considered,  and  the
            computation stops once the sphere size exceeds size_max.
  
  An option "small" is interpreted -- see example below. In place of the group
  G  and  the point n, one can pass as first argument also an rcwa group orbit
  object orb.
  
    Example  
    
    gap> G := Group(List([[0,4,1,4],[0,3,5,6],[0,4,5,6]],ClassTransposition));
    <(0(4),1(4)),(0(3),5(6)),(0(4),5(6))>
    gap> GrowthFunctionOfOrbit(G,18,100,20);
    [ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 5, 6, 8, 6, 5, 
      5, 4, 3, 3, 4, 4, 4, 3, 3, 5, 4, 5, 6, 5, 2, 3, 3, 2, 3, 3, 4, 5, 4, 
      4, 4, 6, 5, 5, 3, 4, 2, 3, 4, 4, 2, 3, 4, 4, 2, 3, 3, 4, 3, 5, 3, 5, 
      4, 5, 6, 5, 3, 4, 5, 6, 5, 4, 3, 5, 4, 5, 5, 4, 4, 5, 5, 3, 4, 5, 3, 
      3, 4, 5, 4, 2, 3, 4, 4, 4 ]
    gap> last = GrowthFunctionOfOrbit(Orbit(G,18),100,20);
    true
    gap> GrowthFunctionOfOrbit(G,18,20,20:small:=[0..100]);
    rec( smallpoints := [ 18, 24, 25, 27, 30, 32, 33, 36, 37, 39, 40, 41, 
          42, 44, 45, 48, 49, 51, 52, 53, 56, 57, 59, 60, 61, 64, 65, 66, 
          68, 69, 71, 75, 76, 77, 80, 81, 83, 88, 89, 92, 93, 95, 100 ], 
      spheresizes := [ 1, 1, 2, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 5, 
          5, 6, 8 ] )
    gap> G := Group(List([[0,2,1,2],[1,2,2,4],[1,4,2,6]],ClassTransposition));
    <(0(2),1(2)),(1(2),2(4)),(1(4),2(6))>
    gap> GrowthFunctionOfOrbit(G,0,100,10000);
    [ 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5, 7, 6, 7, 9, 12, 14, 19, 21, 28, 
      29, 37, 42, 55, 57, 72, 78, 99, 113, 148, 164, 215, 226, 288, 344, 
      462, 478, 612, 686, 894, 985, 1284, 1416, 1847, 2018, 2620, 2902, 
      3786, 4167, 5432, 5958, 7749, 8568, 11178 ]
    
  
  
  Given    an    rcwa    group    G    over    ℤ    and    an    integer    n,
  DistanceToNextSmallerPointInOrbit(G,n)  computes  the smallest number d such
  that  there  is  a  product g of d generators or inverses of generators of G
  which  maps n to an integer with absolute value less than |n|, provided that
  the  orbit  of  n  contains  such  integer. RCWA provides a function to draw
  pictures  of orbits of rcwa groups on ℤ^2. The pictures are written to files
  in  bitmap-  (bmp-)  format. The author has successfully tested this feature
  both  under  Linux  and  under  Windows,  and  the generated pictures can be
  processed further with many common graphics programs:
  
  3.3-3 DrawOrbitPicture
  
  DrawOrbitPicture( G, p0, bound, h, w, colored, palette, filename )  function
  Returns:  nothing.
  
  Draws  a  picture of the orbit(s) of the point(s) p0 under the action of the
  group G on ℤ^2. The argument p0 is either one point or a list of points. The
  argument  bound  denotes  the  bound  to  which  the  ball about p0 is to be
  computed,  in  terms  of  absolute  values  of  coordinates. The size of the
  generated  picture  is h x w pixels. The argument colored is a boolean which
  indicates whether a 24-bit true color picture or a monochrome picture should
  be  generated.  In  the  former  case,  palette must be a list of triples of
  integers in the range 0, dots, 255, denoting the RGB values of the colors to
  be  used.  In  the  latter  case,  palette is not used, and any value can be
  passed.  The  picture  is  written  in bitmap- (bmp-) format to a file named
  filename.  This  is done using the utility function SaveAsBitmapPicture from
  ResClasses.
  
    Example  
    
    gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2),
    >                                                    CyclicGroup(3))));;
    gap> DrawOrbitPicture(PSL2Z,[0,1],2000,512,512,false,fail,"example1.bmp");
    gap> DrawOrbitPicture(PSL2Z,Combinations([1..4],2),2000,512,512,true,
    >                     [[255,0,0],[0,255,0],[0,0,255]],"example2.bmp");
    
  
  
  The pictures drawn in the examples are shown on RCWA's webpage.
  
  Finite  orbits  give  rise to finite quotients of a group, and finite cycles
  can  help  to  check  for conjugacy. Therefore it is important to be able to
  determine them:
  
  
  3.3-4 ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations)
  
  ShortOrbits( G, S, maxlng )  operation
  ShortOrbits( G, S, maxlng, maxn )  operation
  ShortCycles( g, S, maxlng )  operation
  ShortCycles( g, S, maxlng, maxn )  operation
  ShortCycles( g, maxlng )  operation
  Returns:  in  the  first  form  a  list of all orbits of the rcwa group G of
            length  at  most  maxlng  which  intersect  non-trivially with the
            set S. In the second form a list of all orbits of the rcwa group G
            of  length  at  most maxlng which intersect non-trivially with the
            set S  and  which, in terms of euclidean norm, do not exceed maxn.
            In  the  third form a list of all cycles of the rcwa permutation g
            of  length  at  most maxlng which intersect non-trivially with the
            set S.  In  the  fourth  form  a  list  of  all cycles of the rcwa
            permutation   g   of   length   at   most maxlng  which  intersect
            non-trivially  with  the  set S  and  which, in terms of euclidean
            norm,  do  not exceed maxn. In the fifth form a list of all cycles
            of  the  rcwa  permutation g of length at most maxlng which do not
            correspond to cycles consisting of residue classes.
  
  The  operation  ShortOrbits  recognizes  an option finite. If this option is
  set,  it  is  assumed  that  all orbits are finite, in order to speed up the
  computation.  If  furthermore maxlng is negative, a list of all orbits which
  intersect non-trivially with S is returned.
  
  There is an operation CyclesOnFiniteOrbit(G,g,n) which returns a list of all
  cycles  of  the  rcwa  permutation  g  on the orbit of the point n under the
  action of the rcwa group G. Here g is assumed to be an element of G, and the
  orbit of n is assumed to be finite.
  
    Example  
    
    gap> G := Group(ClassTransposition(1,4,2,4)*ClassTransposition(1,4,3,4),
    >               ClassTransposition(3,9,6,18)*ClassTransposition(1,6,3,9));;
    gap> List(ShortOrbits(G,[-15..15],100),
    >         orb->StructureDescription(Action(G,orb)));
    [ "A15", "A4", "1", "1", "C3", "1", "((C2 x C2 x C2) : C7) : C3", "1", 
      "1", "C3", "A19" ]
    gap> ShortCycles(mKnot(7),[1..100],20);
    [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7, 8 ], [ 9, 10 ], 
      [ 11, 12 ], [ 13, 14, 16, 18, 20, 22, 19, 17, 15 ], [ 21, 24 ], 
      [ 23, 26 ], [ 25, 28, 32, 36, 31, 27, 30, 34, 38, 33, 29 ], 
      [ 35, 40 ], [ 37, 42, 48, 54, 47, 41, 46, 52, 45, 39, 44, 50, 43 ], 
      [ 77, 88, 100, 114, 130, 148, 127, 109, 124, 107, 122, 105, 120, 103, 
          89 ] ]
    gap> G := Group(List([[0,2,1,2],[0,5,4,5],[1,4,0,6]],ClassTransposition));;
    gap> CyclesOnFiniteOrbit(G,G.1*G.2,0);
    [ [ 0, 1, 4, 9, 8, 5 ], [ 6, 7 ], [ 10, 11, 14, 19, 18, 15 ], [ 12, 13 ] ]
    gap> List(CyclesOnFiniteOrbit(G,G.1*G.2*G.3*G.1*G.3*G.2,32),Length);
    [ 3148, 3148 ]
    
  
  
  
  3.3-5 ShortResidueClassOrbits & ShortResidueClassCycles
  
  ShortResidueClassOrbits( G, modulusbound, maxlng )  operation
  ShortResidueClassCycles( g, modulusbound, maxlng )  operation
  Returns:  in  the  first  form a list of all orbits of residue classes under
            the  action of the rcwa group G which contain a residue class r(m)
            such  that  m  divides  modulusbound and which are not longer than
            maxlng. In the second form a list of all cycles of residue classes
            of  the rcwa permutation g which contain a residue class r(m) such
            that m divides modulusbound and which are not longer than maxlng.
  
  We  are only talking about a cycle of residue classes of an rcwa permutation
  g  if  the  restrictions  of  g to all contained residue classes are affine.
  Similarly  we  are  only talking about an orbit of residue classes under the
  action  of  an  rcwa group G if the restrictions of all elements of G to all
  residue classes in the orbit are affine.
  
  The  returned  lists  may contain additional cycles, resp., orbits, which do
  not contain a residue class r(m) such that m divides modulusbound, but which
  happen to be found without additional efforts.
  
    Example  
    
    gap> g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6);
    <rcwa permutation of Z with modulus 12>
    gap> ShortResidueClassCycles(g,Mod(g)^2,20);
    [ [ 2(12), 3(12) ], [ 10(12), 11(12) ], [ 4(24), 5(24), 7(36), 6(36) ], 
      [ 20(24), 21(24), 31(36), 30(36) ], 
      [ 8(48), 9(48), 13(72), 19(108), 18(108), 12(72) ], 
      [ 40(48), 41(48), 61(72), 91(108), 90(108), 60(72) ], 
      [ 16(96), 17(96), 25(144), 37(216), 55(324), 54(324), 36(216), 24(144) 
         ], 
      [ 80(96), 81(96), 121(144), 181(216), 271(324), 270(324), 180(216), 
          120(144) ] ]
    gap> G := Group(List([[0,6,5,6],[1,4,4,6],[2,4,3,6]],ClassTransposition));
    <(0(6),5(6)),(1(4),4(6)),(2(4),3(6))>
    gap> ShortResidueClassOrbits(G,48,10);
    [ [ 7(12) ], [ 8(12) ], [ 1(24), 4(36) ], [ 2(24), 3(36) ], 
      [ 12(24), 17(24), 28(36) ], [ 18(24), 23(24), 27(36) ], 
      [ 37(48), 58(72), 87(108) ], [ 38(48), 57(72), 88(108) ], 
      [ 0(48), 5(48), 10(72), 15(108) ], [ 6(48), 11(48), 9(72), 16(108) ] ]
    
  
  
  3.3-6 ComputeCycleLength
  
  ComputeCycleLength( g, n )  function
  Returns:  a record containing the length, the largest point and the position
            of  the largest point of the cycle of the rcwa permutation g which
            contains the point n, provided that this cycle is finite.
  
  If the cycle is infinite, the function will run into an infinite loop unless
  the  option  "abortat"  is set to the maximum number of iterates to be tried
  before  aborting.  Iterates  are  not  stored,  to save memory. The function
  interprets  an  option  "notify",  which  defaults  to  10000;  every notify
  iterations,  the  number  of binary digits of the latest iterate is printed.
  This  output  can  be  suppressed  by  the  option  quiet. The function also
  interprets an option "small", which may be set to a range within which small
  points are recorded and returned in a component smallpoints.
  
    Example  
    
    gap> g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]],
    >                      ClassTransposition));
    <rcwa permutation of Z with modulus 180>
    gap> ComputeCycleLength(g,20:small:=[0..1000]);
    n = 20: after 10000 steps, the iterate has 1919 binary digits.
    n = 20: after 20000 steps, the iterate has 2908 binary digits.
    n = 20: after 30000 steps, the iterate has 1531 binary digits.
    n = 20: after 40000 steps, the iterate has 708 binary digits.
    rec( aborted := false, g := <rcwa permutation of Z with modulus 180>, 
      length := 45961, 
      maximum := 180479928411509527091314790144929480041473309862957394384783\
    0525935437431021442346166422201250935268553945158085769924448388724679753\
    5271669245363980744610119632280105994423399614803956244808653465492205657\
    8650363041608376587943180444494842094693691286183613056599672737336761093\
    3101035841077322874883200384115281051837032147150147712534199292886436789\
    7520389780289517825203780151058517520194926468391308525704499649905091899\
    9667529835495635671154681958992898010506577172313321500572646883756736685\
    0158653917532084531267455434808219032998691038943070902228427549279555530\
    6429870190316109419051531138721361826083376315737131067799731181096142797\
    4868525347003646887454985757711743327946232372385342293662007684758208408\
    8635715976464060647431260835037213863991037813998261883899050447111540742\
    5857187943077255493709629738212709349458790098815926920248565399938335540\
    8092502449690267365120996852, maxpos := 19825, n := 20, 
      smallpoints := [ 20, 23, 66, 99, 294, 295, 298, 441, 447, 882, 890, 
          893 ] )
    
  
  
  3.3-7 CycleRepresentativesAndLengths
  
  CycleRepresentativesAndLengths( g, S )  operation
  Returns:  a  list  of  pairs (cycle representative, length of cycle) for all
            cycles   of  the  rcwa  permutation  g  which  have  a  nontrivial
            intersection with the set S, where fixed points are omitted.
  
  The  rcwa  permutation  g is assumed to have only finite cycles. If g has an
  infinite  cycle  which  intersects  non-trivially  with S, this may cause an
  infinite loop unless a cycle length limit is set via the option abortat. The
  output can be suppressed by the option quiet.
  
    Example  
    
    gap> g := ClassTransposition(0,2,1,2)*ClassTransposition(0,4,1,6);;
    gap> CycleRepresentativesAndLengths(g,[0..50]);
    [ [ 2, 2 ], [ 4, 4 ], [ 8, 6 ], [ 10, 2 ], [ 14, 2 ], [ 16, 8 ], 
      [ 20, 4 ], [ 22, 2 ], [ 26, 2 ], [ 28, 4 ], [ 32, 10 ], [ 34, 2 ], 
      [ 38, 2 ], [ 40, 6 ], [ 44, 4 ], [ 46, 2 ], [ 50, 2 ] ]
    gap> g := Product(List([[0,5,3,5],[1,2,0,6],[2,4,3,6]],
    >                      ClassTransposition));
    <rcwa permutation of Z with modulus 180>
    gap> CycleRepresentativesAndLengths(g,[0..100]:abortat:=100000);
    n = 20: after 10000 steps, the iterate has 1919 binary digits.
    n = 20: after 20000 steps, the iterate has 2908 binary digits.
    n = 20: after 30000 steps, the iterate has 1531 binary digits.
    n = 20: after 40000 steps, the iterate has 708 binary digits.
    n = 79: after 10000 steps, the iterate has 1679 binary digits.
    n = 100: after 10000 steps, the iterate has 712 binary digits.
    n = 100: after 20000 steps, the iterate has 2507 binary digits.
    n = 100: after 30000 steps, the iterate has 3311 binary digits.
    n = 100: after 40000 steps, the iterate has 3168 binary digits.
    n = 100: after 50000 steps, the iterate has 3947 binary digits.
    n = 100: after 60000 steps, the iterate has 4793 binary digits.
    n = 100: after 70000 steps, the iterate has 5325 binary digits.
    n = 100: after 80000 steps, the iterate has 6408 binary digits.
    n = 100: after 90000 steps, the iterate has 7265 binary digits.
    n = 100: after 100000 steps, the iterate has 7918 binary digits.
    [ [ 0, 7 ], [ 5, 3 ], [ 7, 7159 ], [ 11, 9 ], [ 19, 342 ],
      [ 20, 45961 ], [ 25, 3 ], [ 26, 21 ], [ 29, 2 ], [ 31, 3941 ],
      [ 34, 19 ], [ 37, 7 ], [ 40, 5 ], [ 41, 7 ], [ 46, 3 ], [ 49, 2 ],
      [ 59, 564 ], [ 61, 577 ], [ 65, 3 ], [ 67, 23 ], [ 71, 41 ],
      [ 79, 16984 ], [ 80, 5 ], [ 85, 3 ], [ 86, 3 ], [ 89, 2 ], [ 91, 9 ],
      [ 94, 1355 ], [ 97, 7 ], [ 100, fail ] ]
    
  
  
  Often  one  also  wants  to know which residue classes an rcwa mapping or an
  rcwa group fixes setwise:
  
  3.3-8 FixedResidueClasses
  
  FixedResidueClasses( g, maxmod )  operation
  FixedResidueClasses( G, maxmod )  operation
  Returns:  the  set  of  residue classes with modulus greater than 1 and less
            than or equal to maxmod which the rcwa mapping g, respectively the
            rcwa group G, fixes setwise.
  
    Example  
    
    gap> FixedResidueClasses(ClassTransposition(0,2,1,4),8);
    [ 2(3), 3(4), 4(5), 6(7), 3(8), 7(8) ]
    gap> FixedResidueClasses(Group(ClassTransposition(0,2,1,4),
    >                              ClassTransposition(0,3,1,3)),12);
    [ 2(3), 8(9), 11(12) ]
    
  
  
  Frequently  one  needs  to  compute balls of certain radius around points or
  group elements, be it to estimate the growth of a group, be it to see how an
  orbit  looks  like,  be  it  to  search  for  a  group  element with certain
  properties or be it for other purposes:
  
  
  3.3-9  Ball  (for  group,  element  and  radius  or group, point, radius and
  action)
  
  Ball( G, g, r )  method
  Ball( G, p, r, action )  method
  Ball( G, p, r )  method
  Returns:  the  ball  of  radius r  around  the  element g  in  the  group G,
            respectively  the  ball  of  radius r around the point p under the
            action action  of  the  group G, respectively the ball of radius r
            around the point p under the action OnPoints of the group G,
  
  All balls are understood with respect to GeneratorsOfGroup(G). As membership
  tests can be expensive, the former method does not check whether g is indeed
  an  element  of G. The methods require that element- / point comparisons are
  cheap. They are not only applicable to rcwa groups. If the option Spheres is
  set,  the  ball  is  split  up and returned as a list of spheres. There is a
  related  operation  RestrictedBall(G,g,r,modulusbound) specifically for rcwa
  groups  which  computes  only those elements of the ball whose moduli do not
  exceed  modulusbound,  and  which  can  be  reached from g without computing
  intermediate  elements  whose  moduli  do  exceed  modulusbound.  The latter
  operation  interprets an option "boundaffineparts". -- If this option is set
  and  the  group  G  and  the  element  g  are in sparse representation, then
  modulusbound  is  actually taken to be a bound on the number of affine parts
  rather than a bound on the modulus.
  
    Example  
    
    gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2),
    >                                                    CyclicGroup(3))));;
    gap> List([1..10],k->Length(Ball(PSL2Z,[0,1],k,OnTuples)));
    [ 4, 8, 14, 22, 34, 50, 74, 106, 154, 218 ]
    gap> Ball(Group((1,2),(2,3),(3,4)),(),2:Spheres);
    [ [ () ], [ (3,4), (2,3), (1,2) ],
      [ (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,3,2) ] ]
    gap> G := Group(List([[1,2,4,6],[1,3,2,6],[2,3,4,6]],ClassTransposition));;
    gap> B := RestrictedBall(G,One(G),20,36:Spheres);; # try replacing 36 by 72
    gap> List(B,Length);
    [ 1, 3, 6, 12, 4, 6, 6, 4, 4, 4, 6, 6, 3, 3, 2, 0, 0, 0, 0, 0, 0 ]
    
  
  
  It  is  possible  to  determine  group  elements  which map a given tuple of
  elements  of  the  underlying  ring to a given other tuple, if such elements
  exist:
  
  3.3-10 RepresentativeAction
  
  RepresentativeAction( G, source, destination, action )  method
  Returns:  an  element of G which maps source to destination under the action
            given by action.
  
  If  an  element satisfying this condition does not exist, this method either
  returns  fail  or runs into an infinite loop. The problem whether source and
  destination  lie in the same orbit under the action action of G is hard, and
  in its general form most likely computationally undecidable.
  
  In  cases  where  rather a word in the generators of G than the actual group
  element is needed, one should use the operation RepresentativeActionPreImage
  instead. This operation takes five arguments. The first four are the same as
  those  of  RepresentativeAction,  and  the  fifth  is  a  free  group  whose
  generators  are  to  be  used  as  letters  of  the returned word. Note that
  RepresentativeAction  calls  RepresentativeActionPreImage  and evaluates the
  returned  word.  The  evaluation  of the word can very well take most of the
  time if G is wild and coefficient explosion occurs.
  
  The algorithm is based on computing balls of increasing radius around source
  and destination until they intersect non-trivially.
  
    Example  
    
    gap> a := RcwaMapping([[2,0,3],[4,-1,3],[4,1,3]]);; SetName(a,"a");
    gap> b := ClassShift(1,4:Name:="b");; G := Group(a,b);;
    gap> elm := RepresentativeAction(G,[7,4,9],[4,5,13],OnTuples);;
    gap> Display(elm);
    
    Rcwa permutation of Z with modulus 12
    
            /
            | n-3 if n in 1(6) U 10(12)
            | n+4 if n in 5(12) U 9(12)
     n |-> <  n+1 if n in 4(12)
            | n   if n in 0(6) U 2(6) U 3(12) U 11(12)
            |
            \
    
    gap> List([7,4,9],n->n^elm);
    [ 4, 5, 13 ]
    gap> elm := RepresentativeAction(G,[6,-3,8],[-9,4,11],OnPoints);;
    gap> Display(elm);
    
    Rcwa permutation of Z with modulus 12
    
            /
            | 2n/3      if n in 0(6) U 3(12)
            | (4n+1)/3  if n in 2(6) U 11(12)
            | (4n-1)/3  if n in 4(6) U 7(12)
     n |-> <  (2n-8)/3  if n in 1(12)
            | (4n-17)/3 if n in 5(12)
            | (4n-15)/3 if n in 9(12)
            |
            \
    
    gap> [6,-3,8]^elm; List([6,-3,8],n->n^elm); # `OnPoints' allows reordering
    [ -9, 4, 11 ]
    [ 4, -9, 11 ]
    gap> F := FreeGroup("a","b");; phi := EpimorphismByGenerators(F,G);;
    gap> w := RepresentativeActionPreImage(G,[10,-4,9,5],[4,5,13,-8],
    >                                      OnTuples,F);
    a*b^-1*a^-1*(b^-1*a)^2*b*a*b^-2*a*b*a^-1*b
    gap> elm := w^phi;
    <rcwa permutation of Z with modulus 324>
    gap> List([10,-4,9,5],n->n^elm);
    [ 4, 5, 13, -8 ]
    
  
  
  Sometimes  an  rcwa  group  fixes a certain partition of the underlying ring
  into unions of residue classes. If this happens, then any orbit is clearly a
  subset  of exactly one of these parts. Further, such a partition often gives
  rise to proper quotients of the group:
  
  3.3-11 ProjectionsToInvariantUnionsOfResidueClasses
  
  ProjectionsToInvariantUnionsOfResidueClasses( G, m )  operation
  Returns:  the  projections  of  the  rcwa  group G  to the unions of residue
            classes (mod m) which it fixes setwise.
  
  The  corresponding  partition  of  a  set of representatives for the residue
  classes (mod m) can be obtained by the operation OrbitsModulo(G,m).
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,2),ClassShift(3,4));;
    gap> ProjectionsToInvariantUnionsOfResidueClasses(G,4);
    [ [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> 
        [ ( 0(4), 1(4) ), IdentityMapping( Integers ) ], 
      [ ( 0(2), 1(2) ), ClassShift( 3(4) ) ] -> 
        [ ( 2(4), 3(4) ), <rcwa permutation of Z with modulus 4> ] ]
    gap> List(last,phi->Support(Image(phi)));
    [ 0(4) U 1(4), 2(4) U 3(4) ]
    
  
  
  Given  two  partitions of the underlying ring into the same number of unions
  of  residue  classes, there is always an rcwa permutation which maps the one
  to the other:
  
  3.3-12 RepresentativeAction
  
  RepresentativeAction( RCWA(R), P1, P2 )  method
  Returns:  an element of RCWA(R) which maps the partition P1 to P2.
  
  The arguments P1 and P2 must be partitions of the underlying ring R into the
  same  number  of  unions of residue classes. The method for R = ℤ recognizes
  the option IsTame, which can be used to demand a tame result. If this option
  is set and there is no tame rcwa permutation which maps P1 to P2, the method
  runs  into  an infinite loop. This happens if the condition in Theorem 2.8.9
  in [Koh05]  is  not  satisfied.  If  the  option  IsTame  is not set and the
  partitions  P1  and P2 both consist entirely of single residue classes, then
  the returned mapping is affine on any residue class in P1.
  
    Example  
    
    gap> P1 := AllResidueClassesModulo(3);
    [ 0(3), 1(3), 2(3) ]
    gap> P2 := List([[0,2],[1,4],[3,4]],ResidueClass);
    [ 0(2), 1(4), 3(4) ]
    gap> elm := RepresentativeAction(RCWA(Integers),P1,P2);
    <rcwa permutation of Z with modulus 3>
    gap> P1^elm = P2;
    true
    gap> IsTame(elm);
    false
    gap> elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame);
    <tame rcwa permutation of Z with modulus 24>
    gap> P1^elm = P2;
    true
    gap> elm := RepresentativeAction(RCWA(Integers),
    >             [ResidueClass(1,3),
    >              ResidueClassUnion(Integers,3,[0,2])],
    >             [ResidueClassUnion(Integers,5,[2,4]),
    >              ResidueClassUnion(Integers,5,[0,1,3])]);
    <rcwa permutation of Z with modulus 6>
    gap> [ResidueClass(1,3),ResidueClassUnion(Integers,3,[0,2])]^elm;
    [ 2(5) U 4(5), Z \ 2(5) U 4(5) ]
    
  
  
  3.3-13 CollatzLikeMappingByOrbitTree
  
  CollatzLikeMappingByOrbitTree( G, n, min_r, max_r )  operation
  Returns:  either an rcwa mapping f which maps the sphere of radius r about n
            under  the  action  of G into the sphere of radius r-1 about n for
            every r ranging from min_r to max_r, or fail.
  
  Obviously  not  for  every  rcwa group and every root point a mapping f with
  these  properties exists, and if it exists, it usually depends on the choice
  of generators of the group.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,2,1,2),ClassTransposition(1,2,2,4),
    >               ClassTransposition(1,4,2,6));;
    gap> G := SparseRep(G);;
    gap> f := CollatzLikeMappingByOrbitTree(G,0,4,10);
    <rcwa mapping of Z with modulus 4 and 4 affine parts>
    gap> Display(f);
    
    Rcwa mapping of Z with modulus 4 and 4 affine parts
    
            /
            | n+1      if n in 0(4)
            | (3n+1)/2 if n in 1(4)
     n |-> <  n/2      if n in 2(4)
            | n-1      if n in 3(4)
            |
            \
    
    gap> B := Ball(G,0,15:Spheres);
    [ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 6 ], [ 7 ], [ 14 ], [ 9, 15 ], [ 8, 18, 30 ], 
      [ 5, 19, 31 ], [ 4, 10, 38, 62 ], [ 11, 25, 39, 41, 63 ], 
      [ 22, 24, 40, 50, 78, 82, 126 ], [ 23, 33, 51, 79, 83, 127 ], 
      [ 32, 46, 66, 102, 158, 166, 254 ], 
      [ 21, 47, 67, 103, 105, 159, 167, 169, 255 ] ]
    gap> List([3..15],i->IsSubset(B[i-1],B[i]^f));
    [ true, true, true, true, true, true, true, true, true, true, true, true,
      true ]
    gap> Trajectory(f,52,[0,1]);
    [ 52, 53, 80, 81, 122, 61, 92, 93, 140, 141, 212, 213, 320, 321, 482, 241, 
      362, 181, 272, 273, 410, 205, 308, 309, 464, 465, 698, 349, 524, 525, 788, 
      789, 1184, 1185, 1778, 889, 1334, 667, 666, 333, 500, 501, 752, 753, 1130, 
      565, 848, 849, 1274, 637, 956, 957, 1436, 1437, 2156, 2157, 3236, 3237, 
      4856, 4857, 7286, 3643, 3642, 1821, 2732, 2733, 4100, 4101, 6152, 6153, 
      9230, 4615, 4614, 2307, 2306, 1153, 1730, 865, 1298, 649, 974, 487, 486, 
      243, 242, 121, 182, 91, 90, 45, 68, 69, 104, 105, 158, 79, 78, 39, 38, 19, 
      18, 9, 14, 7, 6, 3, 2, 1 ]
    
  
  
  
  3.4 Special attributes of tame residue-class-wise affine groups
  
  There  are  a  couple  of attributes which a priori make only sense for tame
  rcwa  groups.  With their help, various structural information about a given
  such  group  can  be obtained. We have already seen above that there are for
  example  methods for IsSolvable, IsPerfect and DerivedSubgroup available for
  tame  rcwa  groups, while testing wild groups for solvability or perfectness
  is currently not always feasible. The purpose of this section is to describe
  the   specific  attributes  of  tame  groups  which  are  needed  for  these
  computations.
  
  
  3.4-1 RespectedPartition (of a tame rcwa group or -permutation)
  
  RespectedPartition( G )  attribute
  RespectedPartition( g )  attribute
  Returns:  a  shortest  and coarsest possible respected partition of the rcwa
            group G / of the rcwa permutation g.
  
  A  tame  element  g ∈ RCWA(R)  permutes  a partition of R into finitely many
  residue  classes  on  all  of  which  it  is  affine.  Given  a  tame  group
  G < RCWA(R), there is a common such partition for all elements of G. We call
  the mentioned partitions respected partitions of g or G, respectively.
  
  An  rcwa  group or an rcwa permutation has a respected partition if and only
  if  it  is  tame.  This  holds  either  by  definition  or  by Theorem 2.5.8
  in [Koh05], depending on how one introduces the notion of tameness.
  
  There is an operation RespectsPartition(G,P) / RespectsPartition(g,P), which
  tests  whether  G or g respects a given partition P. The permutation induced
  by g on P can be computed efficiently by PermutationOpNC(g,P,OnPoints).
  
    Example  
    
    gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));
    <rcwa group over Z with 2 generators>
    gap> IsTame(G);
    true
    gap> Size(G);
    infinity
    gap> P := RespectedPartition(G);
    [ 0(4), 2(4), 1(6), 3(6), 5(6) ]
    
  
  
  
  3.4-2 ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
  
  ActionOnRespectedPartition( G )  attribute
  KernelOfActionOnRespectedPartition( G )  attribute
  RankOfKernelOfActionOnRespectedPartition( G )  attribute
  Returns:  the  action of the tame rcwa group G on RespectedPartition(G), the
            kernel of this action or the rank of the latter, respectively.
  
  The   method   for   KernelOfActionOnRespectedPartition   uses  the  package
  Polycyclic [EHN13].  The  rank  of  the largest free abelian subgroup of the
  kernel   of   the   action   of G  on  its  stored  respected  partition  is
  RankOfKernelOfActionOnRespectedPartition(G).
  
    Example  
    
    gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));;
    gap> H := ActionOnRespectedPartition(G);
    Group([ (1,3), (1,2) ])
    gap> H = Action(G,P);
    true
    gap> Size(H);
    6
    gap> K := KernelOfActionOnRespectedPartition(G);
    <rcwa group over Z with 3 generators>
    gap> RankOfKernelOfActionOnRespectedPartition(G);
    3
    gap> Index(G,K);
    6
    gap> List(GeneratorsOfGroup(K),Factorization);
    [ [ ClassShift( 0(4) ) ], [ ClassShift( 2(4) ) ], [ ClassShift( 1(6) ) ] ]
    gap> Image(IsomorphismPcpGroup(K));
    Pcp-group with orders [ 0, 0, 0 ]
    
  
  
  Let  G  be  a  tame rcwa group over ℤ, let mathcalP be a respected partition
  of G and put m := |mathcalP|. Then there is an rcwa permutation g which maps
  mathcalP  to  the  partition  of ℤ into the residue classes (mod m), and the
  conjugate  G^g  of G  under  such  a  permutation  is integral (cf. [Koh05],
  Theorem 2.5.14).
  
  The  conjugate G^g can be determined by the operation IntegralConjugate, and
  the   conjugating   permutation g   can   be  determined  by  the  operation
  IntegralizingConjugator. Both operations are applicable to rcwa permutations
  as  well.  Note  that  a  tame  rcwa  group  does not determine its integral
  conjugate uniquely.
  
    Example  
    
    gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));;
    gap> G^IntegralizingConjugator(G) = IntegralConjugate(G);
    true
    gap> RespectedPartition(G);
    [ 0(4), 2(4), 1(6), 3(6), 5(6) ]
    gap> RespectedPartition(G)^IntegralizingConjugator(G);
    [ 0(5), 1(5), 2(5), 3(5), 4(5) ]
    gap> last = RespectedPartition(IntegralConjugate(G));
    true
    
  
  
  
  3.5 Generating pseudo-random elements of RCWA(R) and CT(R)
  
  There  are  methods  for  the  operation Random for RCWA(R) and CT(R). These
  methods  are designed to be suitable for generating interesting examples. No
  particular distribution is guaranteed.
  
    Example  
    
    gap> elm := Random(RCWA(Integers));;
    gap> Display(elm);
    
    Rcwa permutation of Z with modulus 180
    
            /
            | 6n+12     if n in 2(10) U 4(10) U 6(10) U 8(10)
            | 3n+3      if n in 1(20) U 5(20) U 9(20) U 17(20)
            | 6n+10     if n in 0(10)
            | (n+1)/2   if n in 15(60) U 27(60) U 39(60) U 51(60)
            | (n+7)/2   if n in 19(60) U 31(60) U 43(60) U 55(60)
            | 3n+1      if n in 13(20)
            | (-n+17)/6 if n in 23(180) U 35(180) U 59(180) U 71(180) U 
     n |-> <                    95(180) U 131(180) U 143(180) U 179(180)
            | (-n-1)/6  if n in 11(180) U 47(180) U 83(180) U 155(180)
            | (-n+7)/2  if n in 3(60)
            | (n+3)/2   if n in 7(60)
            | (n-17)/6  if n in 107(180)
            | (-n+11)/6 if n in 119(180)
            | (-n+29)/6 if n in 167(180)
            |
            \
    
  
  
  The  elements  which are returned by this method are obtained by multiplying
  class    shifts   (see   ClassShift   (2.2-1)),   class   reflections   (see
  ClassReflection  (2.2-2))  and  class transpositions (see ClassTransposition
  (2.2-3)). These factors can be retrieved by factoring:
  
    Example  
    
    gap> Factorization(elm);
    [ ClassTransposition(0,2,3,4), ClassTransposition(1,2,4,6), ClassShift(0,2), 
      ClassShift(1,3), ClassReflection(2,5), ClassReflection(1,3), 
      ClassReflection(1,2) ]
    
  
  
  
  3.6 The categories of residue-class-wise affine groups
  
  3.6-1 IsRcwaGroup
  
  IsRcwaGroup( G )  filter
  IsRcwaGroupOverZ( G )  filter
  IsRcwaGroupOverZ_pi( G )  filter
  IsRcwaGroupOverGFqx( G )  filter
  Returns:  true  if  G  is  an  rcwa  group,  an  rcwa group over the ring of
            integers,  an  rcwa  group  over a semilocalization of the ring of
            integers  or  an rcwa group over a polynomial ring in one variable
            over a finite field, respectively, and false otherwise.
  
  Often the same methods can be used for rcwa groups over the ring of integers
  and  over  its  semilocalizations.  For  this  reason  there  is  a category
  IsRcwaGroupOverZOrZ_pi   which   is   the   union  of  IsRcwaGroupOverZ  and
  IsRcwaGroupOverZ_pi.
  
  To  allow distinguishing the groups RCWA(R) and CT(R) from others, they have
  the characteristic property IsNaturalRCWA or IsNaturalCT, respectively.