Bilddatei rcwagrp.gi   Sprache: unbekannt

#############################################################################
##
#W  rcwagrp.gi                GAP4 Package `RCWA'                 Stefan Kohl
##
##  This file contains implementations of methods and functions for computing
##  with rcwa groups over
##
##    - the ring Z of the integers, over
##    - the ring Z^2, over
##    - the semilocalizations Z_(pi) of the ring of integers, and over
##    - the polynomial rings GF(q)[x] in one variable over a finite field.
##
##  See the definitions given in the file rcwamap.gd.
##
#############################################################################

#############################################################################
##
#S  Implications between the categories of rcwa groups. /////////////////////
##
#############################################################################

InstallTrueMethod( IsGroup,     IsRcwaGroup );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverZOrZ_pi );
InstallTrueMethod( IsRcwaGroupOverZOrZ_pi, IsRcwaGroupOverZ );
InstallTrueMethod( IsRcwaGroupOverZOrZ_pi, IsRcwaGroupOverZ_pi );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverZxZ );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverGFqx );

#############################################################################
##
#S  Implications of `IsRcwaGroup'. //////////////////////////////////////////
##
#############################################################################

InstallTrueMethod( CanComputeSizeAnySubgroup, IsRcwaGroup );
InstallTrueMethod( KnowsHowToDecompose,
                   IsRcwaGroup and HasGeneratorsOfGroup );

#############################################################################
##
#M  IsWholeFamily . . . . . . . . . . . . . for an rcwa group -- return false
##
InstallMethod( IsWholeFamily,
               "for an rcwa group -- return false (RCWA)", true,
               [ IsRcwaGroup ], 0, ReturnFalse );

#############################################################################
##
#S  Rcwa groups and lists of generators. ////////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  IsGeneratorsOfMagmaWithInverses( <l> ) . . .  for a list of rcwa mappings
##
##  Tests whether all rcwa mappings in the list <l> belong to the same
##  family and are bijective, hence generate a group.
##
InstallMethod( IsGeneratorsOfMagmaWithInverses,
               "for lists of rcwa mappings (RCWA)", true,
               [ IsListOrCollection ], 0,

  function ( l )
    if   ForAll(l,IsRcwaMapping)
    then return     Length(Set(List(l,FamilyObj))) = 1
                and ForAll(l,IsBijective); 
    else TryNextMethod(); fi;
  end );

#############################################################################
##
#M  AssignGeneratorVariables( <G> ) . .  for rcwa groups with at most 8 gen's
##
##  This method assigns the generators of <G> to global variables a, b, ... .
##  As all functions which assign anything one-letter global variables, it is
##  for interactive use only, and should not be called from inside code.
##
InstallMethod( AssignGeneratorVariables,
               "for rcwa groups with at most 8 generators (RCWA)",
               true, [ IsRcwaGroup ], 0,

  function ( G )

    local  gens, names, name, i;

    gens := GeneratorsOfGroup(G);
    if Length(gens) > 8 then TryNextMethod(); fi;
    names := "abcdefgh";
    for i in [1..Length(gens)] do
      name := names{[i]};
      if IsBoundGlobal(name) then
        if   IsReadOnlyGlobal(name)
        then Error("variable ",name," is read-only"); fi;
        UnbindGlobal(name);
        Info(InfoWarning,1,"The global variable ",name,
                           " has been overwritten.");
      fi;
      BindGlobal(name,gens[i]);
      MakeReadWriteGlobal(name);
    od;
    Print("The following global variables have been assigned: ");
    for i in [1..Length(gens)] do
      Print(names{[i]});
      if i < Length(gens) then Print(", "); fi;
    od;
    Print("\n");
  end );

#############################################################################
##
#S  Conversion of rcwa groups between standard and sparse representation. ///
##
#############################################################################

#############################################################################
##
#M  SparseRepresentation( <G> ) . . . . . . . . . . .  for rcwa groups over Z
##
InstallMethod( SparseRepresentation,
               "for rcwa groups over Z (RCWA)",
               true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,

  function ( G )

    local  G_sparse;

    G_sparse := GroupByGenerators(List(GeneratorsOfGroup(G),SparseRep));
    if HasIsTame(G) then SetIsTame(G_sparse,IsTame(G)); fi;
    if   HasModulusOfRcwaMonoid(G)
    then SetModulusOfRcwaMonoid(G_sparse,ModulusOfRcwaMonoid(G)); fi;
    if HasSize(G) then SetSize(G_sparse,Size(G)); fi;
    if HasIsAbelian(G) then SetIsAbelian(G_sparse,IsAbelian(G)); fi;
    if HasIsPGroup(G) then
      SetIsPGroup(G_sparse,IsPGroup(G));
      if HasPrimePGroup(G) then SetPrimePGroup(G_sparse,PrimePGroup(G)); fi;
    fi;
    if   HasIsSolvableGroup(G)
    then SetIsSolvableGroup(G_sparse,IsSolvableGroup(G)); fi;
    if   HasIsPerfectGroup(G)
    then SetIsPerfectGroup(G_sparse,IsPerfectGroup(G)); fi;
    if   HasIsSimpleGroup(G)
    then SetIsSimpleGroup(G_sparse,IsSimpleGroup(G)); fi;
    if   IsNaturalCTP_Z(G)
    then SetFilterObj(G_sparse,IsNaturalCTP_Z); fi;
    return G_sparse;
  end );

#############################################################################
##
#M  StandardRepresentation( <G> ) . . . . . . . . . .  for rcwa groups over Z
##
InstallMethod( StandardRepresentation,
               "for rcwa groups over Z (RCWA)",
               true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,

  function ( G )

    local  G_standard;

    G_standard := GroupByGenerators(List(GeneratorsOfGroup(G),StandardRep));
    if HasIsTame(G) then SetIsTame(G_standard,IsTame(G)); fi;
    if   HasModulusOfRcwaMonoid(G)
    then SetModulusOfRcwaMonoid(G_standard,ModulusOfRcwaMonoid(G)); fi;
    if HasSize(G) then SetSize(G_standard,Size(G)); fi;
    if HasIsAbelian(G) then SetIsAbelian(G_standard,IsAbelian(G)); fi;
    if HasIsPGroup(G) then
      SetIsPGroup(G_standard,IsPGroup(G));
      if HasPrimePGroup(G) then SetPrimePGroup(G_standard,PrimePGroup(G)); fi;
    fi;
    if   HasIsSolvableGroup(G)
    then SetIsSolvableGroup(G_standard,IsSolvableGroup(G)); fi;
    if   HasIsPerfectGroup(G)
    then SetIsPerfectGroup(G_standard,IsPerfectGroup(G)); fi;
    if   HasIsSimpleGroup(G)
    then SetIsSimpleGroup(G_standard,IsSimpleGroup(G)); fi;
    if   IsNaturalCTP_Z(G)
    then SetFilterObj(G_standard,IsNaturalCTP_Z); fi;
    return G_standard;
  end );

#############################################################################
##
#S  Methods for `View', `Print', `Display' etc. /////////////////////////////
##
#############################################################################

#############################################################################
##
#M  ViewObj( <G> ) . . . . . . . . . . . . . . . . . . . . .  for rcwa groups
##
InstallMethod( ViewObj,
               "for rcwa groups (RCWA)", true,
               [ IsRcwaGroup and HasGeneratorsOfGroup ], 0,

  function ( G )

    local  NrGens, RingString, gens, g, cl, i;

    RingString := RingToString(Source(One(G)));
    if IsTrivial(G) then
      Print("Trivial rcwa group over ",RingString);
    elif     IsRcwaGroupOverZ(G) and Length(GeneratorsOfGroup(G)) <=6
         and ForAll(GeneratorsOfGroup(G),IsClassTransposition)
    then
      gens := GeneratorsOfGroup(G);
      Print("<");
      for i in [1..Length(gens)] do
        g  := gens[i];
        cl := TransposedClasses(g);
        Print("(",Residue(cl[1]),"(",Mod(cl[1]),"),",
                  Residue(cl[2]),"(",Mod(cl[2]),"))");
        if i < Length(gens) then Print(","); fi;
      od;
      Print(">");
    else
      Print("<");
      if   HasIsTame(G) and not (HasSize(G) and IsInt(Size(G)))
      then if IsTame(G) then Print("tame "); else Print("wild "); fi; fi;
      NrGens := Length(GeneratorsOfGroup(G));
      Print("rcwa group over ",RingString," with ",NrGens," generator");
      if NrGens > 1 then Print("s"); fi;
      if not (HasIsTame(G) and not IsTame(G)) then
        if   HasIdGroup(G)
        then Print(", of isomorphism type ",IdGroup(G));
        elif HasSize(G)
        then Print(", of order ",Size(G)); fi;
      fi;
      Print(">");
    fi;
  end );

#############################################################################
##
#M  ViewObj( <G> ) . . . . . . . . . for rcwa groups without known generators
##
InstallMethod( ViewObj,
               "for rcwa groups without known generators (RCWA)",
               true, [ IsRcwaGroup ], 0,

  function ( G )
    Print("<");
    if   HasIsTame(G)
    then if IsTame(G) then Print("tame "); else Print("wild "); fi; fi;
    Print("rcwa group over ",RingToString(Source(One(G))));
    if   HasElementTestFunction(G)
    then Print(", with membership test"); fi;
    if   not HasGeneratorsOfGroup(G)
    then Print(", without known generators"); fi;
    Print(">");
  end );

#############################################################################
##
#M  ViewString( <G> ) . . . for groups generated by class transpositions of Z
##
InstallMethod( ViewString,
               "for a group generated by class transpositions of Z",
               true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,

  function ( G )

    local  gens, s, g, gs, cl;

    gens := GeneratorsOfGroup(G);
    if not ForAll(gens,IsClassTransposition) then TryNextMethod(); fi;
    s := "<";
    for g in gens do
      cl := TransposedClasses(g);
      gs := Concatenation(List(["(",Residue(cl[1]),"(",Mod(cl[1]),"),",
                                    Residue(cl[2]),"(",Mod(cl[2]),"))"],
                               String));
      if s <> "<" then s := Concatenation(s,","); fi;
      s := Concatenation(s,gs);
    od;
    s := Concatenation(s,">");
    return s;
  end );

#############################################################################
##
#M  ViewObj( <RG> ) . . . . . . . . . . . . .  for group rings of rcwa groups
##
InstallMethod( ViewObj,
               "for group rings of rcwa groups (RCWA)",
               ReturnTrue, [ IsGroupRing ], 100,

  function ( RG )

    local  R, G;

    R := LeftActingDomain(RG); G := UnderlyingMagma(RG);
    if not IsRcwaGroup(G) or R <> Source(One(G)) then TryNextMethod(); fi;
    Print(RingToString(R)," "); ViewObj(G);
  end );

#############################################################################
##
#M  Print( <G> ) . . . . . . . . . . . . . . . . . . . . . .  for rcwa groups
##
InstallMethod( PrintObj,
               "for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,

  function ( G )
    Print( "Group( ", GeneratorsOfGroup( G ), " )" );
  end );

#############################################################################
##
#M  Display( <G> ) . . . . . . . . . . . . . . . . . . . . .  for rcwa groups
##
InstallMethod( Display,
               "for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,

  function ( G )

    local  RingString, g, prefix;

    RingString := RingToString(Source(One(G)));
    if   IsTrivial(G) 
    then Print("Trivial rcwa group over ",RingString);
         if ValueOption("NoLineFeed") <> true then Print("\n"); fi;
    else prefix := false;
         if HasIsTame(G) and not (HasSize(G) and IsInt(Size(G))) then
           if IsTame(G) then Print("\nTame "); else Print("\nWild "); fi;
           prefix := true;
         fi;
         if prefix then Print("rcwa "); else Print("\nRcwa "); fi;
         Print("group over ",RingString);
         if not (HasIsTame(G) and not IsTame(G)) then
           if   HasIdGroup(G) then Print(" of isomorphism type ",IdGroup(G));
           elif HasSize(G)    then Print(" of order ",Size(G)); fi;
         fi;
         Print(", generated by\n\n[\n");
         for g in GeneratorsOfGroup(G) do Display(g); od;
         Print("]\n\n");
    fi;
  end );

#############################################################################
##
#M  LaTeXStringRcwaGroup( <G> ) . . . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( LaTeXStringRcwaGroup,
               "for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,

  function ( G )

    local  s, g;

    s := "\\langle ";
    for g in GeneratorsOfGroup(G) do
      if s <> "\\langle " then Append(s,", "); fi;
      Append(s,LaTeXStringRcwaMapping(g));
    od;
    Append(s," \\rangle");
    return s;
  end );

#############################################################################
##
#S  The trivial rcwa groups. ////////////////////////////////////////////////
##
#############################################################################

#############################################################################
##
#V  TrivialRcwaGroupOverZ . . . . . . . . . . . . . trivial rcwa group over Z
#V  TrivialRcwaGroupOverZxZ . . . . . . . . . . . trivial rcwa group over Z^2
##
BindGlobal( "TrivialRcwaGroupOverZ", Group( IdentityRcwaMappingOfZ ) );
BindGlobal( "TrivialRcwaGroupOverZxZ", Group( IdentityRcwaMappingOfZxZ ) );

#############################################################################
##
#M  TrivialSubmagmaWithOne( <G> ). . . . . . . . . . . . . .  for rcwa groups
##
InstallMethod( TrivialSubmagmaWithOne,
               "for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,

  function ( G )

    local  triv;

    triv := Group(One(G));
    SetParentAttr(triv,G);
    return triv;
  end );

#############################################################################
##
#S  The construction of the groups RCWA(R) of all rcwa permutations of R. ///
##
#############################################################################

#############################################################################
##
#M  RCWACons( IsRcwaGroup, Integers ) . . . . . . . . . . . . . . . RCWA( Z )
##
##  Returns the group which is formed by all bijective rcwa mappings of Z.
##
InstallMethod( RCWACons,
               "natural RCWA(Z) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsIntegers ], 0,

  function ( filter, R )

    local  G, id;

    id := IdentityRcwaMappingOfZ;
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                              IsRcwaGroupOverZ and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, IdentityRcwaMappingOfZ );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalRCWA );
    SetFilterObj( G, IsNaturalRCWA_Z );
    SetModulusOfRcwaMonoid( G, 0 );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, TrivialRcwaGroupOverZ );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    SetIsPerfectGroup( G, false );
    SetIsSimpleGroup( G, false );
    SetRepresentative( G, RcwaMapping( [ [ -1, 0, 1 ] ] ) );
    SetName( G, "RCWA(Z)" );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  RCWACons( IsRcwaGroup, Integers^2 ) . . . . . . . . . . . . . RCWA( Z^2 )
##
##  Returns the group which is formed by all bijective rcwa mappings of Z^2.
##
InstallMethod( RCWACons,
               "natural RCWA(Z^2) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsRowModule ], 0,

  function ( filter, R )

    local  G, id;

    if not IsZxZ( R ) then TryNextMethod( ); fi;

    id := IdentityRcwaMappingOfZxZ;
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                              IsRcwaGroupOverZxZ and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, id );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalRCWA );
    SetFilterObj( G, IsNaturalRCWA_ZxZ );
    SetModulusOfRcwaMonoid( G, [ [ 0, 0 ], [ 0, 0 ] ] );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, TrivialRcwaGroupOverZxZ );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    SetRepresentative( G, RcwaMapping( R, [ [ 1, 0 ], [ 0, 1 ] ],
      [ [ [ 0, 0 ], [ [ [ -1, 0 ], [ 0, -1 ] ], [ 0, 0 ], 1 ] ] ] ) );
    SetName( G, "RCWA(Z^2)" );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  RCWACons( IsRcwaGroup, Z_pi( <pi> ) ) . . . . . . . . . .  RCWA( Z_(pi) )
##
##  Returns the group which is formed by all bijective rcwa mappings
##  of Z_(pi).
##
InstallMethod( RCWACons,
               "natural RCWA(Z_(pi)) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsZ_pi ], 0,

  function ( filter, R )

    local  G, pi, id;

    pi := NoninvertiblePrimes( R );
    id := RcwaMapping( pi, [ [1,0,1] ] ); IsOne( id );
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                                  IsRcwaGroupOverZ_pi
                              and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, id );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalRCWA );
    SetFilterObj( G, IsNaturalRCWA_Z_pi );
    SetModulusOfRcwaMonoid( G, 0 );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetCentre( G, Group( id ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    SetRepresentative( G, -id );
    SetName( G, Concatenation( "RCWA(", ViewString(R), ")" ) );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  RCWACons( IsRcwaGroup, PolynomialRing( GF( <q> ), 1 ) )  RCWA( GF(q)[x] )
##
##  Returns the group which is formed by all bijective rcwa mappings
##  of GF(q)[x].
##
InstallMethod( RCWACons,
               "natural RCWA(GF(q)[x]) (RCWA)", ReturnTrue, 
               [ IsRcwaGroup, IsUnivariatePolynomialRing ], 0,

  function ( filter, R )

    local  G, q, id, rep;

    q  := Size( CoefficientsRing( R ) );
    id := RcwaMapping( q, One(R), [ [1,0,1] * One(R) ] ); IsOne( id );
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                                  IsRcwaGroupOverGFqx
                              and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, id );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalRCWA );
    SetFilterObj( G, IsNaturalRCWA_GFqx );
    SetModulusOfRcwaMonoid( G, Zero( R ) );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, Group( id ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    rep := ClassTransposition(SplittedClass(R,q){[1..2]});
    SetRepresentative( G, rep );
    SetName( G, Concatenation( "RCWA(GF(", String(q), ")[",
                String(IndeterminatesOfPolynomialRing(R)[1]),"])" ) );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#F  RCWA( <R> ) . . . . . . . . . . . . . . . . . . . . . . . . . . RCWA( R )
##
InstallGlobalFunction( RCWA, R -> RCWACons( IsRcwaGroup, R ) );

#############################################################################
##
#S  The construction of the groups CT(R) ////////////////////////////////////
#S  generated by all class transpositions. //////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  CTCons( IsRcwaGroup, Integers ) . . . . . . . . . . . . . . . . . CT( Z )
##
##  Returns the simple group which is generated
##  by the set of all class transpositions of Z.
##
InstallMethod( CTCons,
               "natural CT(Z) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsIntegers ], 0,

  function ( filter, R )

    local  G, id;

    id := IdentityRcwaMappingOfZ;
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                              IsRcwaGroupOverZ and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, SparseRep( IdentityRcwaMappingOfZ ) );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalCT );
    SetFilterObj( G, IsNaturalCT_Z );
    SetModulusOfRcwaMonoid( G, 0 );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, SparseRep( TrivialRcwaGroupOverZ ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    SetIsPerfectGroup( G, true );
    SetIsSimpleGroup( G, true );
    SetRepresentative( G, SparseRep( ClassTransposition(0,2,1,2) ) );
    SetSupport( G, Integers );
    SetName( G, "CT(Z)" );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  CTCons( IsRcwaGroup, <P>, Integers ) . . . . . . . . . . . . . CT( P, Z )
##
##  Returns the group which is generated by the set of all
##  class transpositions of Z which interchange residue classes whose
##  moduli have only prime factors in the finite set <P>.
##  In case 2 is an element of <P>, this group is simple.
##
InstallMethod( CTCons,
               "natural CT(Z) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsList, IsIntegers ], 0,

  function ( filter, P, R )

    local  G, id;

    if   not ForAll(P,IsPosInt) or not ForAll(P,IsPrimeInt)
    then TryNextMethod(); fi;

    if P = [] then return TrivialRcwaGroupOverZ; fi;

    id := IdentityRcwaMappingOfZ;
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                              IsRcwaGroupOverZ and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, SparseRep( IdentityRcwaMappingOfZ ) );
    SetFilterObj( G, IsNaturalCTP_Z );
    SetModulusOfRcwaMonoid( G, 0 );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetPrimeSet( G, P );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, true );
    SetCentre( G, SparseRep( TrivialRcwaGroupOverZ ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    if 2 in P then
      SetIsPerfectGroup( G, true );
      SetIsSimpleGroup( G, true );
    fi;
    SetRepresentative( G, SparseRep(ClassTransposition(0,P[1],1,P[1])) );
    SetSupport( G, Integers );
    SetName( G, Concatenation( "CT_", String(P), "(Z)" ) );
    SetStructureDescription( G, Name( G ) );
    if P = [2] then # Higman-Thompson group / Thompson's group V
      SetGeneratorsOfGroup(G,List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],
                                  c->SparseRep(ClassTransposition(c))));
    elif P = [3] then
      SetGeneratorsOfGroup(G,List([[0,3,1,3],[1,3,2,3],[2,9,3,9],[5,9,6,9],
                                   [2,3,3,9]],
                                  c->SparseRep(ClassTransposition(c))));
    elif P = [2,3] then
      SetGeneratorsOfGroup(G,List([[0,2,1,2],[0,3,1,3],[1,3,2,3],
                                   [0,2,1,4],[0,2,5,6],[0,3,1,6]],
                                  c->SparseRep(ClassTransposition(c))));
    fi;
    return G;
  end );

#############################################################################
##
#M  CTCons( IsRcwaGroup, Integers^2 ) . . . . . . . . . . . . . . . CT( Z^2 )
##
##  Returns the group which is generated by
##  the set of all class transpositions of Z^2.
##
InstallMethod( CTCons,
               "natural CT(Z^2) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsRowModule ], 0,

  function ( filter, R )

    local  G, id;

    if not IsZxZ(R) then TryNextMethod(); fi;

    id := IdentityRcwaMappingOfZxZ;
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                              IsRcwaGroupOverZxZ and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, IdentityRcwaMappingOfZxZ );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalCT );
    SetFilterObj( G, IsNaturalCT_ZxZ );
    SetModulusOfRcwaMonoid( G, [ [ 0, 0 ], [ 0, 0 ] ] );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, TrivialRcwaGroupOverZxZ );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    SetIsPerfectGroup( G, true );
    SetIsSimpleGroup( G, true );
    SetRepresentative( G, ClassTransposition([0,0],[[1,0],[0,2]],
                                             [0,1],[[1,0],[0,2]]) );
    SetSupport( G, R );
    SetName( G, "CT(Z^2)" );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  CTCons( IsRcwaGroup, Z_pi( <pi> ) ) . . . . . . . . . . . .  CT( Z_(pi) )
##
##  Returns the group which is generated by
##  the set of all class transpositions of Z_(pi).
##
InstallMethod( CTCons,
               "natural CT(Z_(pi)) (RCWA)", ReturnTrue,
               [ IsRcwaGroup, IsZ_pi ], 0,

  function ( filter, R )

    local  G, pi, id, rep;

    pi := NoninvertiblePrimes( R );
    id := RcwaMapping( pi, [ [1,0,1] ] ); IsOne( id );
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                                  IsRcwaGroupOverZ_pi
                              and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, id );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalCT );
    SetFilterObj( G, IsNaturalCT_Z_pi );
    SetModulusOfRcwaMonoid( G, 0 );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetCentre( G, Group( id ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    rep := ClassTransposition(AllResidueClassesModulo(R,pi[1]){[1..2]});
    SetRepresentative( G, rep );
    SetSupport( G, R );
    SetName( G, Concatenation( "CT(", ViewString(R), ")" ) );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#M  CTCons( IsRcwaGroup, PolynomialRing( GF( <q> ), 1 ) ) . .  CT( GF(q)[x] )
##
##  Returns the group which is generated by
##  the set of all class transpositions of GF(q)[x].
##
InstallMethod( CTCons,
               "natural CT(GF(q)[x]) (RCWA)", true, 
               [ IsRcwaGroup, IsUnivariatePolynomialRing ], 0,

  function ( filter, R )

    local  G, q, id, rep;

    q  := Size( CoefficientsRing( R ) );
    id := RcwaMapping( q, One(R), [ [1,0,1] * One(R) ] ); IsOne( id );
    G  := Objectify( NewType( FamilyObj( Group( id ) ),
                                  IsRcwaGroupOverGFqx
                              and IsAttributeStoringRep ),
                     rec( ) );
    SetIsTrivial( G, false );
    SetOne( G, id );
    SetFilterObj( G, IsNaturalRCWA_OR_CT );
    SetFilterObj( G, IsNaturalCT );
    SetFilterObj( G, IsNaturalCT_GFqx );
    SetModulusOfRcwaMonoid( G, Zero( R ) );
    SetMultiplier( G, infinity );
    SetDivisor( G, infinity );
    SetIsFinite( G, false );
    SetSize( G, infinity );
    SetIsFinitelyGeneratedGroup( G, false );
    SetCentre( G, Group( id ) );
    SetIsAbelian( G, false );
    SetIsSolvableGroup( G, false );
    rep := ClassTransposition(SplittedClass(R,q){[1..2]});
    SetRepresentative( G, rep );
    SetSupport( G, R );
    SetName( G, Concatenation( "CT(GF(", String(q), ")[",
                String(IndeterminatesOfPolynomialRing(R)[1]),"])" ) );
    SetStructureDescription( G, Name( G ) );
    return G;
  end );

#############################################################################
##
#F  CT( <R> ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CT(R)
##
InstallGlobalFunction( CT, 

  function ( arg )

    local  P, R;

    if Length(arg) = 1 then
      R := arg[1];
      return CTCons( IsRcwaGroup, R );
    elif Length(arg) = 2 then
      P := arg[1];
      R := arg[2];
      return CTCons( IsRcwaGroup, P, R );
    else Error("usage: CT( [ <P>, ], <R> )"); fi;
  end );

#############################################################################
##
#M  Display( <G> ) . . . . . . . . . . . . . . . . . .  for RCWA(R) and CT(R)
##
InstallMethod( Display,
               "for RCWA(R) and CT(R) (RCWA)", true,
               [ IsNaturalRCWA_OR_CT ], 0,
               function ( G ) Print( Name( G ), "\n" ); end );

#############################################################################
##
#S  The membership- / subgroup test for RCWA(R) and CT(R). //////////////////
##
#############################################################################

#############################################################################
##
#M  \in( <g>, RCWA( <R> ) ) . . . . . . . . . for an rcwa mapping and RCWA(R)
##
InstallMethod( \in,
               "for an rcwa mapping and RCWA(R) (RCWA)", ReturnTrue,
               [ IsRcwaMapping, IsNaturalRCWA ], 100,

  function ( g, RCWA_R )
    return FamilyObj(g) = FamilyObj(One(RCWA_R)) and IsBijective(g);
  end );

#############################################################################
##
#M  \in( <g>, CT( <R> ) ) . . . . . . . . . . . for an rcwa mapping and CT(R)
##
InstallMethod( \in,
               "for an rcwa mapping and CT(R) (RCWA)", ReturnTrue,
               [ IsRcwaMapping, IsNaturalCT ], 100,

  function ( g, CT_R )

    local  R, numres;

    if   FamilyObj(g) <> FamilyObj(One(CT_R)) or not IsBijective(g)
    then return false; elif IsOne(g) then return true; fi;
    R := Support(CT_R);
    if IsIntegers(R) or IsZ_pi(R) then 
      if not IsClassWiseOrderPreserving(g) then return false; fi;
      if IsIntegers(R) and not IsSignPreserving(g) then return false; fi;
      if   Minimum([0..Mod(g)-1]^g) < 0
        or Maximum([-Mod(g)..-1]^g) >= 0
      then return false; fi;
    elif IsZxZ(R) then
      numres := AbsInt(DeterminantMat(Modulus(g)));
      if   not IsClassWiseOrderPreserving(g)
        or not ForAll(Coefficients(g),c->IsUpperTriangularMat(c[1]))
        or not ForAll(Coefficients(g),c->c[1][1][1] > 0)
        or not ForAll(Cartesian([0..numres-1],[-numres..numres]),
                      t->t^g*[1,0]>=0)
      then return false; fi;
    fi;
    if   ForAll(FactorizationIntoCSCRCT(g),
                gi ->    IsClassTransposition(gi)
                      or IsPrimeSwitch(gi) or IsPrimeSwitch(gi^-1))
    then return true; fi;
    TryNextMethod();
  end );

#############################################################################
##
#M  \in( <g>, CT( <P>, Integers ) ) . .  for an rcwa mapping of Z and CT_P(Z)
##
InstallMethod( \in,
               "for an rcwa mapping and CT_P(Z) (RCWA)", ReturnTrue,
               [ IsRcwaMappingOfZ, IsNaturalCTP_Z ], 100,

  function ( g, CTP_Z )

    local  R, numres;

    if not IsClassWiseOrderPreserving(g) or not IsSignPreserving(g)
      or not IsSubset(PrimeSet(CTP_Z),PrimeSet(g))
    then return false; fi;
    if   ForAll( FactorizationIntoCSCRCT(g),
                 gi -> (   IsClassTransposition(gi)
                        or IsPrimeSwitch(gi) or IsPrimeSwitch(gi^-1) )
                    and IsSubset( PrimeSet(CTP_Z), PrimeSet(gi) ) )
    then return true; fi;
    TryNextMethod();
  end );

#############################################################################
## 
#M  IsSubset( RCWA( <R> ), G ) . . . . . . . .  for RCWA(R) and an rcwa group
## 
InstallMethod( IsSubset,
               "for RCWA(R) and an rcwa group (RCWA)", ReturnTrue,
               [ IsNaturalRCWA, IsRcwaGroup ], SUM_FLAGS,

  function ( RCWA_R, G )
    return FamilyObj(One(RCWA_R)) = FamilyObj(One(G));
  end );

#############################################################################
## 
#M  IsSubset( CT( Integers ), G ) . . . .  for CT(Z) and an rcwa group over Z
## 
InstallMethod( IsSubset,
               "for CT(Z) and an rcwa group over Z (RCWA)", ReturnTrue,
               [ IsNaturalCT_Z, IsRcwaGroupOverZ and HasGeneratorsOfGroup ], SUM_FLAGS,

  function ( CT_Z, G )
    if not IsClassWiseOrderPreserving(G)
      or ForAny(GeneratorsOfGroup(G),g->Determinant(g)<>0)
      or Minimum(Ball(G,0,4,OnPoints)) < 0
    then return false; fi;
    return ForAll(GeneratorsOfGroup(G),g->g in CT_Z);
  end );

#############################################################################
## 
#M  IsSubset( CT( <R> ), G ) . . . . . . . . . .  for CT(R) and an rcwa group
## 
InstallMethod( IsSubset,
               "for CT(R) and an rcwa group (RCWA)", ReturnTrue,
               [ IsNaturalCT, IsRcwaGroup and HasGeneratorsOfGroup ], 100,

  function ( CT_R, G )
    if FamilyObj(One(G)) <> FamilyObj(One(CT_R)) then return false; fi;
    return ForAll(GeneratorsOfGroup(G),g->g in CT_R);
  end );

#############################################################################
## 
#M  IsSubset( CT( <R> ), RCWA( <R> ) ) . . . . . . . .  for CT(R) and RCWA(R)
## 
##  Note that it is currently not known e.g. whether
##  CT(GF(2)[x]) = RCWA(GF(2)[x]) or not.
##
InstallMethod( IsSubset,
               "for CT(R) and RCWA(R) (RCWA)", ReturnTrue,
               [ IsNaturalCT, IsNaturalRCWA ], SUM_FLAGS,

  function ( CT_R, RCWA_R )
    if FamilyObj(One(CT_R)) <> FamilyObj(One(RCWA_R)) then return false; fi;
    if IsRcwaGroupOverZOrZ_pi(RCWA_R) then return false; fi;
    if   not IsTrivial(Units(CoefficientsRing(Source(One(RCWA_R)))))
    then return false; fi;
    Error("sorry - this is still an open question!");
    return fail;
  end );

#############################################################################
##
#S  Counting / enumerating certain elements of RCWA(R) and CT(R). ///////////
##
#############################################################################

#############################################################################
##
#V  NrElementsOfCTZWithGivenModulus
##
##  The numbers of elements of CT(Z) of given order m <= 24, subject to the
##  conjecture that CT(Z) is the setwise stabilizer of N_0 in RCWA(Z).
##
BindGlobal( "NrElementsOfCTZWithGivenModulus",
[ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680, 5114793582, 238618996919, 
  12441866975999, 716985401817362, 45251629386163199, 3104281120750130159, 
  229987931693135611303, 18301127616460012222080, 1556718246822087917567999, 
  140958365897067252175843218, 13537012873511994353270783999, 
  1374314160482820530097944198162, 147065220260069766956421116517343, 
  16544413778663040175990602280223999, 1951982126641242370890486633922559999, 
  241014406219744996673035312579811441520 ] );

#############################################################################
## 
#F  AllElementsOfCTZWithGivenModulus( m ) .  elements of CT(Z) with modulus m
##
##  Assumes the conjecture that CT(Z) is the setwise stabilizer of the
##  nonnegative integers in RCWA(Z).
##
InstallGlobalFunction( AllElementsOfCTZWithGivenModulus,

  function ( m )

    local  elems, source, ranges, range, perms, g;

    if not IsPosInt(m) then
      Error("usage: AllElementsOfCTZWithGivenModulus( <m> ) ",
            "for a positive integer m\n");
    fi;
    if m = 1 then return [ IdentityRcwaMappingOfZ ]; fi;
    source := AllResidueClassesModulo(Integers,m);
    ranges := PartitionsIntoResidueClasses(Integers,m);
    perms  := AsList(SymmetricGroup(m));
    elems  := [];
    for range in ranges do
      for g in perms do
        Add(elems,RcwaMapping(source,Permuted(range,g)));
      od;
    od;
    return Filtered(Set(elems),elm->Mod(elm)=m);
  end );

#############################################################################
##
#S  Factoring elm's of RCWA(R) into class shifts/reflections/transpositions.
##
#############################################################################

#############################################################################
##
#M  Factorization( RCWA( <R> ), <g> ) .  for RCWA( R ) and an element thereof
##
InstallMethod( Factorization,
               "into class shifts / reflections / transpositions (RCWA)",
               IsCollsElms, [ IsNaturalRCWA, IsRcwaMapping ], 0,
               function(RCWA_R,g) return FactorizationIntoCSCRCT(g); end );

#############################################################################
##
#M  Factorization( CT( <R> ), <g> ) . . .  for CT( R ) and an element thereof
##
InstallMethod( Factorization,
               "into class shifts / reflections / transpositions (RCWA)",
               IsCollsElms, [ IsNaturalCT, IsRcwaMapping ], 0,

 function( CT_R, g )
   if g in CT_R then return FactorizationIntoCSCRCT(g);
                else return fail; fi;
 end );

#############################################################################
##
#S  Decomposing elements of CT(Z). //////////////////////////////////////////
##
#############################################################################

#############################################################################
## 
#A  DecompositionIntoPermutationalAndOrderPreservingElement( <g> )
##
InstallMethod( DecompositionIntoPermutationalAndOrderPreservingElement,
               "for elements of CT(Z) (RCWA)", true, [ IsRcwaMappingOfZ ], 0,

  function ( g )

  local  a, b, cls, P, q;

    if   not IsBijective(g) or not IsSignPreserving(g)
    then TryNextMethod(); fi;

    q := Product(PrimeSet(g));
    cls := AllResidueClassesModulo(Mod(g));
    SortParallel(List(cls,cl->CoefficientsQadic(Residue(cl),q)),cls);
    P := cls^g;
    SortParallel(List(P,cl->CoefficientsQadic(Residue(cl),q)),P);
    b := RcwaMapping(cls,P);
    a := g/b;
    return [ a, b ];
  end );

############################################################################
##
#S  The epimorphisms RCWA(Z) -> C2 and RCWA+(Z) -> (Z,+). ///////////////////
##
#############################################################################

#############################################################################
##
#M  Sign( <f> ) . . . . . . . . . . . for rcwa mappings of Z in standard rep.
##
InstallMethod( Sign,
               "for rcwa mappings of Z in standard rep. (RCWA)",
               true, [ IsRcwaMappingOfZInStandardRep ], 0,

  function ( f )

    local  m, c, sgn, r, ar, br, cr;

    if not IsBijective(f) then return fail; fi;
    m := Modulus(f); c := Coefficients(f);
    sgn := 0;
    for r in [0..m-1] do
      ar := c[r+1][1]; br := c[r+1][2]; cr := c[r+1][3];
      sgn := sgn + br/AbsInt(ar);
      if ar < 0 then sgn := sgn + (m - 2*r); fi;
    od;
    sgn := (-1)^(sgn/m);
    return sgn;
  end );

#############################################################################
##
#M  Sign( <f> ) . . . . . . . . . . . . for rcwa mappings of Z in sparse rep.
##
InstallMethod( Sign,
               "for rcwa mappings of Z in sparse rep. (RCWA)",
               true, [ IsRcwaMappingOfZInSparseRep ], 0,

  function ( f )

    local  sgn, c, r, m, a, b;

    if not IsBijective(f) then return fail; fi;
    sgn := 0;
    for c in f!.coeffs do
      r := c[1]; m := c[2]; a := c[3]; b := c[4];
      sgn := sgn + b/(m*AbsInt(a));
      if a < 0 then sgn := sgn + (m - 2*r)/m; fi;
    od;
    sgn := (-1)^sgn;
    return sgn;
  end );

#############################################################################
##
#M  Determinant( <f> ) . . . . . . .  for rcwa mappings of Z in standard rep.
##
InstallMethod( Determinant,
               "for rcwa mappings of Z in standard rep. (RCWA)",
               true, [ IsRcwaMappingOfZInStandardRep ], 0,

  function ( f )
    if Mult(f) = 0 then return fail; fi;
    return Sum(List(Coefficients(f),c->c[2]/AbsInt(c[1])))/Modulus(f);
  end );

#############################################################################
##
#M  Determinant( <f> ) . . . . . . . .  for rcwa mappings of Z in sparse rep.
##
InstallMethod( Determinant,
               "for rcwa mappings of Z in sparse rep. (RCWA)",
               true, [ IsRcwaMappingOfZInSparseRep ], 0,

  function ( f )
    if Mult(f) = 0 then return fail; fi;
    return Sum(List(Coefficients(f),c->c[4]/AbsInt(c[3]*c[2])));
  end );

#############################################################################
##
#M  Determinant( <f>, <S> ) .  for rcwa mappings on unions of residue classes
##
InstallOtherMethod( Determinant,
                    "for rcwa mappings on unions of residue classes (RCWA)",
                    true, [ IsRcwaMappingOfZInStandardRep,
                            IsResidueClassUnionOfZ ], 0,

  function ( f, S )

    local  m, c, r, cl;

    m := Modulus(f); c := Coefficients(f);
    return Sum(List([1..m],
                    r->Density(Intersection(S,ResidueClass(Integers,m,r-1)))
                      *c[r][2]/AbsInt(c[r][1])));
  end );

#############################################################################
##
#M  Determinant( <f>, <S> ) .  for rcwa mappings on unions of residue classes
##
InstallOtherMethod( Determinant,
                    "for rcwa mappings on unions of residue classes (RCWA)",
                    true, [ IsRcwaMappingOfZInSparseRep,
                            IsResidueClassUnionOfZ ], 0,

  function ( f, S )
    return Sum(List(f!.coeffs,
                    c -> Density(Intersection(S,ResidueClass(c[1],c[2])))
                       * c[4]/AbsInt(c[3])));
  end );

#############################################################################
##
#M  SignInOddCTPZ( <g> ) . . . . . . . .  for elements of CT_P(Z), 2 \notin P
##
InstallMethod( SignInOddCTPZ,
               "for elements of CT_P(Z) where P does not contain 2 (RCWA)",
               true, [ IsRcwaMappingOfZ ], 0,

  function ( g )

    local  factors;

    if   not IsBijective(g) or not IsSignPreserving(g) or 2 in PrimeSet(g)
    then TryNextMethod(); fi;
    factors := DecompositionIntoPermutationalAndOrderPreservingElement(g);
    return SignPerm(Permutation(factors[1],AllResidueClassesModulo(Mod(g))));
  end );

#############################################################################
##
#S  Generating random elements of RCWA(R), CT(R) and other rcwa groups. /////
##
#############################################################################

#############################################################################
##
#M  Random( RCWA( Integers ) ) . . . . . . . .  a `random' element of RCWA(Z)
##
InstallMethod( Random,
               "for RCWA(Z) (RCWA)", true, [ IsNaturalRCWA_Z ], SUM_FLAGS,

  function ( RCWA_Z )

    local  result, ClassTranspositions, ClassShifts, ClassReflections,
           maxmodct, maxmodcscr, noct, nocs, nocr, genfactors, classes,
           tame, integralpairs, g, i;

    tame       := ValueOption("IsTame") = true;
    noct       := GetOption("NumberOfCTs",Random([0..2]),IsInt);
    nocs       := GetOption("NumberOfCSs",Random([0..3]),IsInt);
    nocr       := GetOption("NumberOfCRs",Random([0..3]),IsInt);
    maxmodcscr := GetOption("ModulusBoundForCSCRs",6,IsPosInt);
    maxmodct   := GetOption("ModulusBoundForCTs",14,IsPosInt);
    if maxmodct <> CLASS_PAIRS_LARGE[1] then
      MakeReadWriteGlobal("CLASS_PAIRS_LARGE");
      CLASS_PAIRS_LARGE := [maxmodct,ClassPairs(maxmodct)];
      MakeReadOnlyGlobal("CLASS_PAIRS_LARGE");
    fi;
    classes             := Combinations([1..maxmodcscr],2)-1;
    ClassTranspositions := List([1..noct],i->Random(CLASS_PAIRS[2]));
    if   Random([1..4]) = 1 
    then Add(ClassTranspositions,Random(CLASS_PAIRS_LARGE[2])); fi;
    ClassShifts         := List([1..nocs],i->Random(classes));
    ClassReflections    := List([1..nocr],i->Random(classes));
    ClassTranspositions := List(ClassTranspositions,ClassTransposition);
    ClassShifts         := List(ClassShifts,t->ClassShift(t)^Random([-1,1]));
    ClassReflections    := List(ClassReflections,ClassReflection);
    genfactors          := Concatenation(ClassTranspositions,ClassShifts,
                                         ClassReflections);
    result              := Product(genfactors);
    if result = 1 then result := One(RCWA_Z); fi;
    if not tame then SetFactorizationIntoCSCRCT(result,genfactors); fi;
    if tame then
      integralpairs := Filtered(CLASS_PAIRS[2],t->t[2]=t[4]);
      g := One(RCWA_Z);
      for i in [1..Random([1..3])] do
        g := g * ClassTransposition(Random(integralpairs));
      od;
      result := g^result;
      SetIsTame(result,true);
      SetOrder(result,Order(g));
    fi;
    IsBijective(result);
    return result;
  end );

#############################################################################
##
#M  Random( RCWA( <R> ) ) . . . . . . . . . . . a `random' element of RCWA(R)
##
InstallMethod( Random,
               "for RCWA(R) (RCWA)", true, [ IsNaturalRCWA ], 0,

  function ( RCWA_R )
    return Random( CT( Support( RCWA_R ) ) );
  end );

#############################################################################
##
#M  Random( CT( Integers ) ) . . . . . . . . . .  a `random' element of CT(Z)
##
InstallMethod( Random,
               "for CT(Z) (RCWA)", true, [ IsNaturalCT_Z ], SUM_FLAGS,

  function ( CT_Z )

    local  noct;

    noct := GetOption("NumberOfCTs",RootInt(Random([0..125]),3),IsInt);
    return Random(RCWA(Integers):NumberOfCTs:=noct,NumberOfCSs:=0,
                                 NumberOfCRs:=0);
  end );

#############################################################################
##
#M  Random( CT( <R> ) ) . . . . . . . . . . . . . a `random' element of CT(R)
##
InstallMethod( Random,
               "for CT(R) (RCWA)", true, [ IsNaturalCT ], 0,

  function ( CT_R )

    local  result, R, tame, noct, ClassTranspositions,
           classpairs, integralpairs, maxm, x, g, i;

    if   IsNaturalCT_Z(CT_R)  # For CT(Z) there is a better method available.
    then TryNextMethod(); fi;
    R := Support(CT_R);
    tame := ValueOption("IsTame") = true;
    noct := ValueOption("NumberOfCTs");
    if noct = fail then if not tame then noct := RootInt(Random([0..100]),3);
                                    else noct := Random([0..2]); fi; fi;
    if IsZ_pi(R) then
      maxm := Maximum(NoninvertiblePrimes(R));
      maxm := Maximum(maxm,Minimum(NoninvertiblePrimes(R))^2);
      classpairs := List(ClassPairs(R,maxm),
                         t->[ResidueClass(R,t[2],t[1]),
                             ResidueClass(R,t[4],t[3])]);
    elif IsFiniteFieldPolynomialRing(R) then
      x          := IndeterminatesOfPolynomialRing(R)[1];
      classpairs := ClassPairs(R,x^3);
    fi;
    ClassTranspositions := List([1..noct],i->Random(classpairs));
    ClassTranspositions := List(ClassTranspositions,ClassTransposition);
    result              := Product(ClassTranspositions);
    if result = 1 then result := One(CT_R); fi;
    if   not tame
    then SetFactorizationIntoCSCRCT(result,ClassTranspositions); fi;
    if tame then
      integralpairs := Filtered(classpairs,t->t[2]=t[4]);
      g := One(CT_R);
      for i in [1..Random([1..3])] do
        g := g * ClassTransposition(Random(integralpairs));
      od;
      result := g^result;
      SetIsTame(result,true);
      SetOrder(result,Order(g));
    fi;
    IsBijective(result);
    return result;
  end );

#############################################################################
##
#M  Random( <G>, <n> ) . .  for finitely generated rcwa group and word length
##
InstallOtherMethod( Random,
                    "for rcwa group and word length (RCWA)",
                    ReturnTrue, [ IsRcwaGroup, IsPosInt ], 0,

  function ( G, n )

    local  gens, g, gi, last_gi, i;

    if   not HasGeneratorsOfGroup(G) or Length(GeneratorsOfGroup(G)) <= 1
    then TryNextMethod(); fi;
    if   ForAll(GeneratorsOfGroup(G),g->HasIsClassTransposition(g)
                                    and IsClassTransposition(g))
    then gens := GeneratorsOfGroup(G);
    else gens := Set(GeneratorsAndInverses(G)); fi;
    g := One(G); last_gi := One(G);
    for i in [1..n] do
      repeat gi := Random(gens); until gi <> last_gi^-1;
      g := g * gi;
      last_gi := gi;
    od;
    return g;
  end );

#############################################################################
##
#S  The action of RCWA(R) and CT(R) on R. ///////////////////////////////////
##
#############################################################################

#############################################################################
##
#M  RepresentativeActionOp( RCWA( <R> ), <n1>, <n2>, <act> )
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(Z) and two integers (RCWA)", ReturnTrue,
               [ IsNaturalRCWA, IsInt, IsInt, IsFunction ], 0,

  function ( RCWA_R, n1, n2, act )

    local  R;

    if act <> OnPoints then TryNextMethod(); fi;
    R := Support(RCWA_R);
    if   Characteristic(R) = 0
    then return ClassShift(R)^(n2-n1);
    else return RcwaMapping(R,One(R),[[One(R),n2-n1,One(R)]]); fi;
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA(Integers), <l1>, <l2>, <act> )
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(Z) and two k-tuples of integers (RCWA)", ReturnTrue,
               [ IsNaturalRCWA_Z, IsList, IsList, IsFunction ], 0,

  function ( RCWA_Z, l1, l2, act )

    local  g, range, perm, exp, points, n;

    points := Union(l1,l2);
    if not IsSubset(Integers,points) then return fail; fi;
    range := [1..Maximum(points)-Minimum(points)+1]; n := Length(range);
    exp := -Minimum(points)+1;
    perm := RepresentativeAction(SymmetricGroup(n),l1+exp,l2+exp,act);
    if perm = fail then return fail; fi;
    g := RcwaMapping(perm,range);
    return g^(ClassShift(0,1)^-exp);
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA( <R> ), <S1>, <S2>, <act> ) 
##
##  Returns an rcwa mapping <g> of <R> which maps <S1> to <S2>.
##  The sets <S1> and <S2> must be unions of residue classes of <R>.
##  The argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(R) and two residue class unions (RCWA)",
               ReturnTrue,
               [ IsNaturalRCWA, IsResidueClassUnion,
                 IsResidueClassUnion, IsFunction ], 0,

  function ( RCWA_R, S1, S2, act )

        local  Refine, Refinement, R, S, C, g;

    Refinement := function ( cls, lng )

      local  m, splitcl, parts;

      while Length(cls) <> lng do
        m       := Minimum(List(cls,Modulus));
        splitcl := First(cls,cl->Modulus(cl)=m); RemoveSet(cls,splitcl);
        parts := SplittedClass(splitcl,SizeOfSmallestResidueClassRing(R));
        if Length(parts) > lng - Length(cls) + 1 then return fail; fi;
        cls := Union(cls,parts);
      od;
      return cls;
    end;

    Refine := function ( S )
      if   Length(S[1]) > Length(S[2])
      then S[2] := Refinement(S[2],Length(S[1]));
      elif Length(S[2]) > Length(S[1])
      then S[1] := Refinement(S[1],Length(S[2])); fi;
    end;

    R := Support(RCWA_R);
    if not IsSubset(R,S1) or not IsSubset(R,S2) then return fail; fi;
    S := List([S1,S2],AsUnionOfFewClasses);
    C := List([S1,S2],Si->AsUnionOfFewClasses(Difference(R,Si)));
    Refine(S); Refine(C);
    if fail in S or fail in C then return fail; fi;
    g := RcwaMapping(Concatenation(S[1],C[1]),Concatenation(S[2],C[2]));
    return g;
  end );

#############################################################################
##
#M  RepresentativeActionOp( CT( <R> ), <S1>, <S2>, <act> ) 
##
##  Returns an element <g> of CT(<R>) which maps <S1> to <S2>.
##  The sets <S1> and <S2> must be unions of residue classes of <R>.
##  The argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
               "for CT(R) and two residue class unions (RCWA)",
               ReturnTrue,
               [ IsNaturalCT, IsResidueClassUnion,
                 IsResidueClassUnion, IsFunction ], 0,

  function ( CT_R, S1, S2, act )

        local  Refine, Refinement, R, S, D1, D2, length, factors, g;

    Refinement := function ( cls, lng )

      local  m, splitcl, parts;

      while Length(cls) <> lng do
        m       := Minimum(List(cls,Modulus));
        splitcl := First(cls,cl->Modulus(cl)=m); RemoveSet(cls,splitcl);
        parts := SplittedClass(splitcl,SizeOfSmallestResidueClassRing(R));
        if Length(parts) > lng - Length(cls) + 1 then return fail; fi;
        cls := Union(cls,parts);
      od;
      return cls;
    end;

    Refine := function ( S )

      local  maxlength, i;

      maxlength := Maximum(List(S,Length));
      for i in [1..Length(S)] do
        if   Length(S[i]) < maxlength
        then S[i] := Refinement(S[i],maxlength); fi;
      od;
    end;

    R := Support(CT_R);
    if not IsSubset(R,S1) or not IsSubset(R,S2) then return fail; fi;

    if IsSubset(S2,S1) then D1 := Difference(S2,S1);
                       else D1 := Difference(R,S1); fi;
    D2 := Difference(R,Union(D1,S2));

    S := List([S1,D1,D2,S2],AsUnionOfFewClasses);
    Refine(S); if fail in S then return fail; fi;
    length := Length(S[1]);

    factors := List([1..3],
                    i->List([1..length],
                            j->ClassTransposition(S[i][j],S[i+1][j])));
    factors := Flat(factors);

    g := Product(Flat(factors));
    SetFactorizationIntoCSCRCT(g,factors);

    return g;
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA( Integers ), <P1>, <P2>, <act> ) 
##
##  Returns an rcwa mapping <g> which maps the partition <P1> to the
##  partition <P2> and which is
##
##  - affine on the elements of <P1>, if the option `IsTame' is not set
##    and all elements of both partitions <P1> and <P2> are single residue
##    classes, and
##
##  - tame, if the option `IsTame' is set.
##
##  The arguments <P1> and <P2> must be partitions of Z into equally many
##  disjoint residue class unions, and the argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(Z) and two class partitions (RCWA)", true,
               [ IsNaturalRCWA_Z, IsList, IsList, IsFunction ], 100,

  function ( RCWA_Z, P1, P2, act )

    local  SplitClass, g, tame, m, c, P, min, minpos, Phat, Buckets, b,
           k, ri, mi, rtildei, mtildei, ar, br, cr, r, i, j;

    SplitClass := function ( i, j )

      local  mods, pos, m, r, mtilde, r1, r2, j2, pos2;

      mods := List(Buckets[i][j],Modulus);
      m    := Minimum(mods);
      pos  := Position(mods,m);
      r    := Residues(Buckets[i][j][pos])[1];
      mtilde := 2*m; r1 := r; r2 := r + m;
      Buckets[i][j] := Union(Difference(Buckets[i][j],[Buckets[i][j][pos]]),
                             [ResidueClass(Integers,mtilde,r1),
                              ResidueClass(Integers,mtilde,r2)]);
      j2  := Filtered([1..k],
                      j->Position(Buckets[3-i][j],
                                  ResidueClass(Integers,m,r))<>fail)[1];
      pos2 := Position(Buckets[3-i][j2],ResidueClass(Integers,m,r));
      Buckets[3-i][j2] := Union(Difference( Buckets[3-i][j2],
                                           [Buckets[3-i][j2][pos2]]),
                                [ResidueClass(Integers,mtilde,r1),
                                 ResidueClass(Integers,mtilde,r2)]);
    end;

    if   Length(P1) <> Length(P2)
      or not ForAll(P1,IsResidueClassUnionOfZ)
      or not ForAll(P2,IsResidueClassUnionOfZ)
      or [Union(List(P1,IncludedElements)),Union(List(P1,ExcludedElements)),
          Union(List(P2,IncludedElements)),Union(List(P2,ExcludedElements))]
         <> [[],[],[],[]]
      or Sum(List(P1,Density)) <> 1 or Sum(List(P2,Density)) <> 1
      or Union(P1) <> Integers or Union(P2) <> Integers
    then TryNextMethod(); fi;

    if not ForAll(P1,IsResidueClass) or not ForAll(P2,IsResidueClass) then
      P1 := List(P1,AsUnionOfFewClasses);
      P2 := List(P2,AsUnionOfFewClasses);
      P  := [P1,P2];
      for j in [1..Length(P1)] do
        if Length(P[1][j]) <> Length(P[2][j]) then
          if Length(P[1][j]) < Length(P[2][j]) then i := 1; else i := 2; fi;
          repeat
            min    := Minimum(List(P[i][j],Modulus));
            minpos := Position(List(P[i][j],Modulus),min);
            P[i][j][minpos] := SplittedClass(P[i][j][minpos],2);
            P[i][j] := Flat(P[i][j]);
          until Length(P[1][j]) = Length(P[2][j]);
        fi;
      od;
      P1 := Flat(P[1]); P2 := Flat(P[2]);
    fi;

    if ValueOption("IsTame") <> true then
      g := RcwaMapping(P1,P2);
    else
      k       := Length(P1);
      m       := Lcm(List(Union(P1,P2),Modulus));
      P       := [P1,P2];
      Phat    := List([0..m-1],r->ResidueClass(Integers,m,r));
      Buckets := List([1..2],i->List([1..k],j->Filtered(Phat,
                 cl->Residues(cl)[1] mod Modulus(P[i][j]) =
                 Residues(P[i][j])[1])));
      repeat
        for i in [1..k] do
          b := [Buckets[1][i],Buckets[2][i]];
          if Length(b[2]) > Length(b[1]) then
            for j in [1..Length(b[2])-Length(b[1])] do
              SplitClass(1,i);
            od;
          elif Length(b[1]) > Length(b[2]) then
            for j in [1..Length(b[1])-Length(b[2])] do
              SplitClass(2,i);
            od;
          fi;
        od;
      until ForAll([1..k],i->Length(Buckets[1][i]) = Length(Buckets[2][i]));
      g := RcwaMapping(Flat(Buckets[1]),Flat(Buckets[2]));
      SetIsTame(g,true); SetRespectedPartition(g,Set(Flat(Buckets[1])));
    fi;
    return g;
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA( <R> ), <P1>, <P2>, <act> ) 
##
##  Returns an rcwa mapping <g> which maps the partition <P1> to the
##  partition <P2> and which is affine on the elements of <P1>.
##
##  The arguments <P1> and <P2> must be partitions of <R> into equally
##  many residue classes, and the argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(<R>) and two class partitions (RCWA)", true,
               [ IsNaturalRCWA, IsList, IsList, IsFunction ], 0,

  function ( RCWA_R, P1, P2, act )

    local  R, g;

    R := Support(RCWA_R);

    if   Length(P1) <> Length(P2)
      or not ForAll(Union(P1,P2),IsResidueClass)
      or not ForAll(Union(P1,P2),cl->IsSubset(R,cl))
      or not ForAll([P1,P2],P->Sum(List(P,Density))=1)
      or not ForAll([P1,P2],P->Union(P) = R)
    then TryNextMethod(); fi;

    return RcwaMapping(P1,P2);
  end );

#############################################################################
##
#S  Conjugacy of elements in RCWA(R) and CT(R). /////////////////////////////
##
#############################################################################

#############################################################################
##
#M  IsConjugate( RCWA( Integers ), <f>, <g> ) 
##
##  This method checks whether the `standard conjugates' of <f> and <g> are
##  equal, if the mappings are tame, and looks for different lengths of short
##  cycles otherwise. The latter will often not terminate. In particular this
##  is the case if <f> and <g> are conjugate.
##
InstallMethod( IsConjugate,
               "for two rcwa mappings of Z, in RCWA(Z) (RCWA)",
               true, [ IsNaturalRCWA_Z, IsRcwaMappingOfZ,
                       IsRcwaMappingOfZ ], 0,

  function ( RCWA_Z, f, g )

    local  maxlng;

    if f = g then return true; fi;
    if Order(f) <> Order(g) or IsTame(f) <> IsTame(g) then return false; fi;
    if IsTame(f) then
      return StandardConjugate(f) = StandardConjugate(g);
    else
      maxlng := 2;
      repeat
        if    Collected(List(ShortCycles(f,maxlng),Length))
           <> Collected(List(ShortCycles(g,maxlng),Length))
        then return false; fi;
        maxlng := maxlng * 2;
      until false;
    fi;
  end );

#############################################################################
##
#M  IsConjugate( RCWA( Z_pi( <pi> ) ), <f>, <g> ) 
##
##  This method makes only trivial checks. It cannot confirm conjugacy
##  unless <f> and <g> are equal.
##
InstallMethod( IsConjugate,
               "for two rcwa mappings of Z_(pi) in RCWA(Z_(pi)) (RCWA)",
               ReturnTrue, [ IsNaturalRCWA_Z_pi,
                             IsRcwaMappingOfZ_pi, IsRcwaMappingOfZ_pi ], 0,

  function ( RCWA_Z_pi, f, g )

    local  maxlng;

    if not f in RCWA_Z_pi or not g in RCWA_Z_pi then return fail; fi;
    if f = g then return true; fi;
    if Order(f) <> Order(g) or IsTame(f) <> IsTame(g) then return false; fi;
    maxlng := 2;
    repeat
      if    Collected(List(ShortCycles(f,maxlng),Length))
         <> Collected(List(ShortCycles(g,maxlng),Length))
      then return false; fi;
      maxlng := maxlng * 2;
    until false;
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA( Integers ), <f>, <g>, <act> ) 
##
##  This method is for tame rcwa mappings of Z under the conjugation action
##  of RCWA(Z). It returns an rcwa mapping <h> such that <f>^<h> = <g> in
##  case such a mapping exists and fail otherwise. The action <act> must be
##  `OnPoints'.
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(Z) and two tame rcwa mappings of Z (RCWA)", true,
               [ IsNaturalRCWA_Z, IsRcwaMappingOfZ, IsRcwaMappingOfZ,
                 IsFunction ], 0,

  function ( RCWA_Z, f, g, act )
    if act <> OnPoints then TryNextMethod(); fi;
    if f = g then return One(f); fi;
    if not ForAll([f,g],IsTame) then TryNextMethod(); fi;
    if Order(f) <> Order(g) then return fail; fi;
    if StandardConjugate(f) <> StandardConjugate(g) then return fail; fi;
    return StandardizingConjugator(f) * StandardizingConjugator(g)^-1;
  end );

#############################################################################
##
#M  RepresentativeActionOp( RCWA( Integers ), <f>, <g>, <act> ) 
##
##  This method is for tame rcwa mappings of Z under the conjugation action
##  of RCWA(Z). It covers the special case of products of the same numbers of
##  class shifts, inverses of class shifts, class reflections and class
##  transpositions, each, whose supports are pairwise disjoint and do not
##  entirely cover Z up to a finite complement.
##
InstallMethod( RepresentativeActionOp,
               "for RCWA(Z) and products of disjoint CS/CR/CT (RCWA)", true,
               [ IsNaturalRCWA_Z, IsRcwaMappingOfZ, IsRcwaMappingOfZ,
                 IsFunction ], 100,

  function ( RCWA_Z, f, g, act )

    local  RefinedPartition, Sorted, maps, facts, P, l, sigma, i;

    RefinedPartition := function ( P, k )

      local  l, mods, min, pos;

      P := ShallowCopy(P); l := Length(P);
      while l < k do
        mods   := List(P,Modulus);
        min    := Minimum(mods);
        pos    := Position(mods,min);
        P[pos] := SplittedClass(P[pos],2);
        P      := Flat(P);
        l      := l + 1;
      od;
      return P;
    end;

    Sorted := l -> [Filtered(l,fact->IsClassShift(fact)
                                  or IsClassShift(fact^-1)),
                    Filtered(l,IsClassReflection),
                    Filtered(l,IsClassTransposition)];              

    if act <> OnPoints then TryNextMethod(); fi;
    if f = g then return One(f); fi;
    if not ForAll([f,g],IsTame) then TryNextMethod(); fi;
    if Order(f) <> Order(g) then return fail; fi;
    maps  := [f,g];
    facts := List(maps,FactorizationIntoCSCRCT);
    if   Length(facts[1]) <> Length(facts[2])
      or 1 in List(maps,map->Density(Support(map)))
      or ForAny([1..2],i->Density(Support(maps[i]))
                       <> Sum(List(facts[i],fact->Density(Support(fact)))))
      or not ForAll(Union(facts),
                    fact ->   IsClassShift(fact) or IsClassShift(fact^-1)
                           or IsClassReflection(fact)
                           or IsClassTransposition(fact))
    then TryNextMethod(); fi;
    facts := List(facts,Sorted);
    if   List(facts[1],Length) <> List(facts[2],Length)
    then TryNextMethod(); fi;
    P := List(maps,
              map->AsUnionOfFewClasses(Difference(Integers,Support(map))));
    l  := Maximum(List(P,Length));
    for i in [1..2] do
      if l > Length(P[i]) then P[i] := RefinedPartition(P[i],l); fi;
    od;
    for i in [1..2] do
      Append(P[i],Flat(List(Flat(facts[i]),
                  fact->Filtered(LargestSourcesOfAffineMappings(fact),
                                 cl->Intersection(Support(fact),cl)<>[]))));
    od;
    sigma := RcwaMapping(P[1],P[2]);
    for i in [1..Length(facts[1][1])] do
--> --------------------

--> maximum size reached

--> --------------------