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  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
    
  ------------------------------------------------------------------
  
  There  are  methods for the operations View, Display, Print and String which
  are  applicable  to rcwa groups. 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-1 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.
  
  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-2 CT
  
  > CT( R ) __________________________________________________________function
  Returns:  The  group CT(R) which is generated by all class transpositions of
            the ring R.
  
  ---------------------------  Example  ----------------------------
    
    gap> CT_Z := CT(Integers);
    CT(Z)
    gap> IsSimple(CT_Z); # One of a longer list of stored attributes/properties.
    true
    gap> IsSubgroup(CT_Z,G);
    false
    
  ------------------------------------------------------------------
  
  Another  way  of  constructing  an rcwa group is taking the image of an rcwa
  representation:
  
  3.1-3 IsomorphismRcwaGroup
  
  > IsomorphismRcwaGroup( G, R ) ____________________________________attribute
  > IsomorphismRcwaGroup( G ) _______________________________________attribute
  Returns:  A   monomorphism  from  the  group  G  to RCWA(R)  or  to RCWA(Z),
            respectively.
  
  The  best-supported case is R = Z. 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,C) to
  RCWA(Z).
  
  ---------------------------  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 ] ->
    [ <bijective rcwa mapping of Z with modulus 12>,
      <bijective rcwa mapping of Z with modulus 24>,
      <bijective rcwa mapping of Z with modulus 12>,
      <bijective rcwa mapping of Z with modulus 72>,
      <bijective rcwa mapping of Z with modulus 36> ]
    gap> IsomorphismRcwaGroup(FreeGroup(2));
    [ f1, f2 ] -> [ <wild bijective rcwa mapping of Z with modulus 8>,
      <wild bijective rcwa mapping of Z with modulus 8> ]
    gap> F2 := Image(last);
    <wild rcwa group over Z with 2 generators>
    
  ------------------------------------------------------------------
  
  The  class of groups which can faithfully be represented as rcwa groups over
  the  integers  is  closed  under taking direct products, under taking wreath
  products  with  finite  groups  and  under  taking  wreath products with the
  infinite cyclic group (Z,+). Therefore these operations can be used to build
  rcwa groups as well:
  
  3.1-4 DirectProduct
  
  > DirectProduct( G1, G2, ... ) _______________________________________method
  Returns:  An  rcwa group isomorphic to the direct product of the rcwa groups
            over Z given as arguments.
  
  There  is  certainly no unique or canonical way to embed a direct product of
  rcwa  groups  into  RCWA(Z). 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-5  WreathProduct  (for an rcwa group over Z, with a permutation group or
  (Z,+))
  
  > WreathProduct( G, P ) ______________________________________________method
  > WreathProduct( G, Z ) ______________________________________________method
  Returns:  An rcwa group isomorphic to the wreath product of the rcwa group G
            over Z  with  the  finite permutation group P or with the infinite
            cyclic group Z, respectively.
  
  The  first-mentioned  method  embeds the DegreeAction(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  DegreeAction(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 bijective rcwa mapping of Z with modulus 8>,
      <wild bijective rcwa mapping of Z with modulus 8> ] ->
    [ <wild bijective rcwa mapping of Z with modulus 40>,
      <wild bijective rcwa mapping of Z with modulus 40> ]
    gap> Embedding(F2wrA5,2);
    [ (1,2,3,4,5), (3,4,5) ] ->
    [ <bijective rcwa mapping of Z with modulus 5, of order 5>,
      <bijective rcwa mapping of Z with modulus 5, of order 3> ]
    gap> ZwrZ := WreathProduct(Group(ClassShift(0,1)),Group(ClassShift(0,1)));
    <wild rcwa group over Z with 2 generators>
    gap> Embedding(ZwrZ,1);
    [ ClassShift(0,1) ] ->
    [ <tame bijective rcwa mapping of Z with modulus 4, of order infinity> ]
    gap> Embedding(ZwrZ,2);
    [ ClassShift(0,1) ] ->
    [ <wild bijective rcwa mapping of Z with modulus 4> ]
    
  ------------------------------------------------------------------
  
  Many  of  the  above  group constructions are based on certain monomorphisms
  from  the  group  RCWA(R)  into  itself.  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 them:
  
  
  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
    
  ------------------------------------------------------------------
  
  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 infty
  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 integral
  respectively  class-wise  order-preserving  if  all  of its elements are so.
  There    are    corresponding   methods   available   for   IsIntegral   and
  IsClassWiseOrderPreserving.  There  is  a  property  IsSignPreserving, which
  indicates  whether  a given rcwa group over Z acts on the set of nonnegative
  integers. The latter holds for any subgroup of CT(Z).
  
  ---------------------------  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,IsIntegral,
    >          IsClassWiseOrderPreserving,IsSignPreserving],f->f(G));
    [ 24, 2, 2, [ 2, 3 ], false, false, false ]
    
  ------------------------------------------------------------------
  
  
  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 some information on the group structure is a dedicated
  method for the operation StructureDescription:
  
  3.2-1 StructureDescription
  
  > StructureDescription( G ) __________________________________________method
  Returns:  A string which describes the structure of the rcwa group G to some
            extent.
  
  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 (Z,+) 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.  While for isomorphic finite
  groups  always  the  same  structure description is computed, this cannot be
  guaranteed for isomorphic rcwa groups.
  
  ---------------------------  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"
    
  ------------------------------------------------------------------
  
  However  the extent to which the structure of an rcwa group can be exhibited
  automatically  is  certainly 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);
    [ ClassTransposition(0,2,1,2), ClassTransposition(0,3,1,3) ] -> 
    [ (1,2)(3,4)(5,6), (1,2)(4,5) ]
    
  ------------------------------------------------------------------
  
  Next  we say a few words about the membership test for rcwa groups. For tame
  rcwa  groups,  membership  or non-membership can always be decided. For wild
  groups,  membership  or non-membership can very often be decided quite quick
  as  well,  but  not  always. 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  direct  product  of  two  free  groups  of  rank 2  can  faithfully  be
  represented  as  an  rcwa  group.  According to [Mih58] this implies that in
  general   the   membership   problem  for  rcwa  groups  is  algorithmically
  undecidable.
  
  ---------------------------  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));
    <bijective rcwa mapping of Z with modulus 48>
    gap> ClassTransposition(0,2,1,6)^g = ClassTransposition(1,4,0,8);
    true
    
  ------------------------------------------------------------------
  
  The  number  of  conjugacy  classes of RCWA(Z) 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 ]
    
  ------------------------------------------------------------------
  
  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
  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.
  
  Both  the  performance  and  the  returned epimorphism depend on whether the
  package FR [Bar07] is present or not.
  
  ---------------------------  Example  ----------------------------
    
    gap> a := ClassTransposition(2,4,3,4 :Name:="a");;
    gap> b := ClassTransposition(4,6,8,12:Name:="b");;
    gap> c := ClassTransposition(3,4,4,6 :Name:="c");;
    gap> G := Group(a,b,c);
    <rcwa group over Z with 3 generators>
    gap> phi := EpimorphismFromFpGroup(G,6);
    [ a, b, c ] -> [ a, b, c ]
    gap> RelatorsOfFpGroup(Source(phi));
    [ a^2, b^2, c^2, c*b*c*b*c*b, c*b*c*a*c*b*c*a*c*b*c*a, 
      b*a*b*a*b*a*b*a*b*a*b*a ]
    
  ------------------------------------------------------------------
  
  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-5).
  
  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:Name:="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
    <bijective rcwa mapping of Z with modulus 8>
    gap> PreImagesRepresentative(phi,g); # -> a factorization of g
    b^-4*a^-1*b^-1*a^-1*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));
    <bijective rcwa mapping of Z with modulus 8>
    gap> pre := PreImagesRepresentatives(phi,g);
    [ b^-1*a^-1*b^-1*a^-1*b^3*a*b*a*b^-2, b^-1*a^-1*b*a^-1*b^3*a*b^-1*a*b^-2 ]
    gap> rel := CyclicallyReducedWord(pre[1]/pre[2]); # -> a nontriv. relation
    b^-1*a^-1*b^3*a*b^2*a^-1*b^-3*a*b^-1
    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 is often feasible:
  
  ---------------------------  Example  ----------------------------
    
    gap> G := Group(ClassTransposition(1,2,0,4),ClassShift(0,2));;
    gap> IsTransitive(G,Integers);
    true
    
  ------------------------------------------------------------------
  
  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> 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
    
  ------------------------------------------------------------------
  
  RCWA  permits drawing pictures of orbits of rcwa groups on Z^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 produced
  pictures can be processed further with many common graphics programs:
  
  3.3-2 DrawOrbitPicture
  
  > DrawOrbitPicture( G, p0, r, 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 Z^2. The argument p0 is either one point or a list of points. The
  argument r denotes the radius of the ball around p0 to be computed. The size
  of  the  created  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  drawn.  In the former case, palette must be a list of triples of
  integers  in the range 0, dots, 255, denoting the RGB values of 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 (7.6-1).
  
  -----------------------------  Log  ------------------------------
    
    gap> PSL2Z := Image(IsomorphismRcwaGroup(FreeProduct(CyclicGroup(2),
    >                                                    CyclicGroup(3))));;
    gap> DrawOrbitPicture(PSL2Z,[0,1],20,512,512,false,fail,"example1.bmp");
    gap> DrawOrbitPicture(PSL2Z,Combinations([1..4],2),20,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-3 ShortOrbits (for rcwa groups) & ShortCycles (for rcwa permutations)
  
  > ShortOrbits( G, S, maxlng ) _____________________________________operation
  > ShortCycles( g, S, maxlng ) _____________________________________operation
  > ShortCycles( g, maxlng ) ________________________________________operation
  Returns:  In  the first form a list of all finite orbits of the rcwa group G
            of  length  at  most  maxlng which intersect nontrivially with the
            set S.
  
            In  the second form a list of all cycles of the rcwa permutation g
            of  length  at  most maxlng  which intersect nontrivially with the
            set S.
  
            In  the  third 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.
  
  ---------------------------  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 ] ]
    
  ------------------------------------------------------------------
  
  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-4  Ball  (for  group,  element  and  radius  or group, point, radius and
  action)
  
  > Ball( G, g, r ) ____________________________________________________method
  > Ball( G, p, r, action ) ____________________________________________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.
  
  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 splitted up and returned as a list of spheres.
  
  ---------------------------  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) ] ]
    
  ------------------------------------------------------------------
  
  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-5 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 nontrivially.
  
  ---------------------------  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);
    
    Bijective rcwa mapping of Z with modulus 12
    
                  n mod 12              |                n^f
    ------------------------------------+------------------------------------
       0  2  3  6  8 11                 | n
       1  7 10                          | n - 3
       4                                | n + 1
       5  9                             | n + 4
    
    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);
    
    Bijective rcwa mapping of Z with modulus 12
    
                  n mod 12              |                n^f
    ------------------------------------+------------------------------------
       0  3  6                          | 2n/3
       1                                | (2n - 8)/3
       2  8 11                          | (4n + 1)/3
       4  7 10                          | (4n - 1)/3
       5                                | (4n - 17)/3
       9                                | (4n - 15)/3
    
    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*b^-1*a*b*a*b^-2*a*b*a^-1*b
    gap> elm := w^phi;
    <bijective rcwa mapping 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-6 Projections
  
  > Projections( 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> Projections(G,4);
    [ [ ClassTransposition(0,2,1,2), ClassShift(3,4) ] ->
        [ <bijective rcwa mapping of Z with modulus 4>,
          IdentityMapping( Integers ) ],
      [ ClassTransposition(0,2,1,2), ClassShift(3,4) ] ->
        [ <bijective rcwa mapping of Z with modulus 4>,
          <bijective rcwa mapping 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-7 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 = Z 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);
    <bijective rcwa mapping of Z with modulus 3>
    gap> P1^elm = P2;
    true
    gap> IsTame(elm);
    false
    gap> elm := RepresentativeAction(RCWA(Integers),P1,P2:IsTame);
    <tame bijective rcwa mapping 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])]);
    <bijective rcwa mapping 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.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  respected  partition  of  the  rcwa  group  G  /  of  the  rcwa
            permutation g.
  
  A  tame  element  g in 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.
  
  Related  attributes  are RespectedPartitionShort and RespectedPartitionLong.
  The  first  of  these  denotes  a  respected partition consisting of residue
  classes r(m) where m divides the modulus of G or g, respectively. The second
  denotes  a  respected partition consisting of residue classes r(m) where the
  modulus of G (respectively g) divides m.
  
  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);
    [ 3(6), 5(6), 0(8), 2(8), 4(8), 6(8), 1(12), 7(12) ]
    
  ------------------------------------------------------------------
  
  
  3.4-2 ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
  
  > ActionOnRespectedPartition( G ) _________________________________attribute
  > KernelOfActionOnRespectedPartition( G ) _________________________attribute
  Returns:  The  action  of  the tame rcwa group G on RespectedPartition(G) or
            the kernel of this action, respectively.
  
  The   method   for   KernelOfActionOnRespectedPartition   uses  the  package
  Polycyclic [EN06].  The  rank  of  the  largest free abelian subgroup of the
  kernel  of the action of G on its stored respected partition can be computed
  by RankOfKernelOfActionOnRespectedPartition(G).
  
  ---------------------------  Example  ----------------------------
    
    gap> G := Group(ClassTransposition(0,4,1,6),ClassShift(0,2));;
    gap> H := ActionOnRespectedPartition(G);
    Group([ (3,7)(5,8), (3,4,5,6) ])
    gap> H = Action(G,P);
    true
    gap> Size(H);
    48
    gap> K := KernelOfActionOnRespectedPartition(G);
    <rcwa group over Z with 3 generators>
    gap> RankOfKernelOfActionOnRespectedPartition(G);
    3
    gap> Index(G,K);
    48
    gap> List(GeneratorsOfGroup(K),Factorization);
    [ [ ClassShift(0,4)^2 ], [ ClassShift(2,4)^2 ], [ ClassShift(1,6)^2 ] ]
    gap> Image(IsomorphismPcpGroup(K));
    Pcp-group with orders [ 0, 0, 0 ]
    
  ------------------------------------------------------------------
  
  Let  G  be  a  tame rcwa group over Z, 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 Z 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);
    [ 3(6), 5(6), 0(8), 2(8), 4(8), 6(8), 1(12), 7(12) ]
    gap> RespectedPartition(G)^IntegralizingConjugator(G);
    [ 0(8), 1(8), 2(8), 3(8), 4(8), 5(8), 6(8), 7(8) ]
    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.
  
  -----------------------------  Log  ------------------------------
    
    gap> elm := Random(RCWA(Integers));;
    gap> Display(elm);
    
    Bijective rcwa mapping of Z with modulus 12
    
                  n mod 12              |                n^f
    ------------------------------------+------------------------------------
       0  2  4  6  8 10                 | 3n + 2
       1  5  9                          | -n + 2
       3  7                             | (n - 7)/2
      11                                | (-n + 20)/3
    
    
  ------------------------------------------------------------------
  
  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:
  
  -----------------------------  Log  ------------------------------
    
    gap> Factorization(elm);
    [ ClassTransposition(0,2,3,4), ClassTransposition(3,4,4,6),
      ClassShift(0,2)^-1, ClassReflection(3,4), ClassReflection(1,4) ]
    
  ------------------------------------------------------------------
  
  There  is  an  auxiliary  function ClassPairs([R,] m), which is used in this
  context.  In its one-argument form, this function returns a list of 4-tuples
  (r_1,m_1,r_2,m_2)  of  integers  corresponding  to  the  unordered  pairs of
  disjoint  residue  classes  r_1(m_1) and r_2(m_2) with m_1, m_2 <= m. In its
  two-argument form, it does "the equivalent" for the ring R.
  
  ---------------------------  Example  ----------------------------
    
    gap> List(ClassPairs(4),ClassTransposition);
    [ ClassTransposition(0,2,1,2), ClassTransposition(0,2,1,4),
      ClassTransposition(0,2,3,4), ClassTransposition(0,3,1,3),
      ClassTransposition(0,3,2,3), ClassTransposition(0,4,1,4),
      ClassTransposition(0,4,2,4), ClassTransposition(0,4,3,4),
      ClassTransposition(1,2,0,4), ClassTransposition(1,2,2,4),
      ClassTransposition(1,3,2,3), ClassTransposition(1,4,2,4),
      ClassTransposition(1,4,3,4), ClassTransposition(2,4,3,4) ]
    gap> List(last,TransposedClasses);
    [ [ 0(2), 1(2) ], [ 0(2), 1(4) ], [ 0(2), 3(4) ], [ 0(3), 1(3) ],
      [ 0(3), 2(3) ], [ 0(4), 1(4) ], [ 0(4), 2(4) ], [ 0(4), 3(4) ],
      [ 1(2), 0(4) ], [ 1(2), 2(4) ], [ 1(3), 2(3) ], [ 1(4), 2(4) ],
      [ 1(4), 3(4) ], [ 2(4), 3(4) ] ]
    
  ------------------------------------------------------------------
  
  
  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.