  
  [1m[4m[31m2. Residue Class-Wise Affine Mappings[0m
  
  This  chapter  describes  the  functionality  provided  by  this package for
  computing with residue class-wise affine mappings.
  
  
  [1m[4m[31m2.1 Basic definitions[0m
  
  Let  R be an infinite euclidean domain which is not a field and all of whose
  proper residue class rings are finite. A mapping f: R -> R is called [22m[36mresidue
  class-wise  affine[0m,  or  in short an [22m[36mrcwa[0m mapping, if there is an m in R \ 0
  such  that  the  restrictions  of  f to the residue classes r(m) in R/mR are
  affine.  This  means  that for any residue class r(m) there are coefficients
  a_r(m),  b_r(m),  c_r(m) in R, such that the restriction of the mapping f to
  the set r(m) = r+km | k in R is given by
  
  f|_r(m): r(m) -> R, n -> ( a_r(m) * n + b_r(m) ) / c_r(m).
  
  The  value m is called the [22m[36mmodulus[0m of f. It is understood that all fractions
  are  reduced,  i.e.  that  gcd(  a_r(m), b_r(m), c_r(m) ) = 1, and that m is
  chosen multiplicatively minimal.
  
  Apart  from  the restrictions imposed by the condition that the image of any
  residue  class r(m) under f must be a subset of R and that one cannot divide
  by 0, the coefficients a_r(m), b_r(m) and c_r(m) can be any ring elements.
  
  When  talking  about  the  [22m[36mproduct[0m of some rcwa mappings, it is always meant
  their  composition  as  mappings,  and  by  the  inverse of a bijective rcwa
  mapping  it  is  meant  its inverse mapping. Products are evaluated from the
  left to the right.
  
  The  set  RCWA(R)  :=  {  g  in Sym(R) | g is residue class-wise affine } is
  closed  under  multiplication  and  taking  inverses  (this  can be verified
  easily), hence forms a subgroup of Sym(R). A subgroup of RCWA(R) is called a
  [22m[36mresidue class-wise affine[0m group, or in short an [22m[36mrcwa[0m group.
  
  
  [1m[4m[31m2.2 Entering rcwa mappings[0m
  
  In  order  to  define  an  rcwa  mapping,  it  is  necessary  to specify the
  underlying  ring R,  the  modulus m  and  the  coefficients  a_r(m),  b_r(m)
  and c_r(m) for r(m) running over the residue classes (mod m).
  
  A  coefficient  list  for  an rcwa mapping with modulus m consists of |R/mR|
  coefficient  triples  [22m[32m[ a_rm, b_rm, c_rm ][0m.  Their ordering is determined by
  the  ordering  of  the representatives of the residue classes (mod m) in the
  sorted  list  returned  by [22m[32mAllResidues([22m[34mR[0m, [22m[34mm[0m)[0m. For R = Z, this means that the
  coefficient  triple  for  the residue class 0(m) comes first, then comes the
  one for 1(m), the one for 2(m) and so on.
  
  The  easiest  way to enter a given rcwa mapping is by [22m[32mRcwaMapping( [ [22m[34mR[0m, [22m[34mm[0m, ]
  [22m[34mcoeffs[0m  )[0m.  If  the  arguments [22m[34mR[0m and [22m[34mm[0m are omitted, they default to [22m[32mIntegers[0m
  resp.  the  length of the coefficient list [22m[34mcoeffs[0m. If the given coefficients
  would  enforce  a  division by zero or images of elements of [22m[34mR[0m outside [22m[34mR[0m, an
  error  message  is  printed  and  a  break loop is entered. For example, the
  coefficient  triple [22m[32m[1,1,3][0m at the first position is not allowed if [22m[34mR[0m is the
  ring  of integers. The reason for this is that not all integers congruent to
  0 + 1 = 1 mod [22m[34mm[0m are divisible by 3.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> T := RcwaMapping([[1,0,2],[3,1,2]]); # The Collatz mapping.[0m
    [22m[35m<rcwa mapping of Z with modulus 2>[0m
    [22m[35mgap> SetName(T,"T"); Display(T);[0m
    [22m[35m[0m
    [22m[35mRcwa mapping of Z with modulus 2[0m
    [22m[35m[0m
    [22m[35m                n mod 2                |                 n^T[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m  0                                    | n/2[0m
    [22m[35m  1                                    | (3n + 1)/2[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  In  the  sequel,  a  description of the general-purpose constructor for rcwa
  mappings  is  given.  This might look a bit technical on a first glance. For
  getting  started,  the  reader  may  find  it  easier  to  look first at the
  functions  for  constructing  some  kinds  of particularly simple-structured
  bijective rcwa mappings of Z described afterwards.
  
  [1m[4m[31m2.2-1 RcwaMapping[0m
  
  [1m[34m> RcwaMapping( [0m[22m[34mR, m, coeffs[0m[1m[34m ) ________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mR, coeffs[0m[1m[34m ) ___________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mcoeffs[0m[1m[34m ) ______________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mperm, range[0m[1m[34m ) _________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mm, values[0m[1m[34m ) ___________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mpi, coeffs[0m[1m[34m ) __________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mq, m, coeffs[0m[1m[34m ) ________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mP1, P2[0m[1m[34m ) ______________________________________________[0mmethod
  [1m[34m> RcwaMapping( [0m[22m[34mcycles[0m[1m[34m ) ______________________________________________[0mmethod
  [1mReturns:[0m  An rcwa mapping.
  
  Construction of an rcwa mapping.
  
  In  all  cases  the  argument [22m[34mR[0m is the underlying ring, [22m[34mm[0m is the modulus and
  [22m[34mcoeffs[0m is the coefficient list as described above. In case one or several of
  these  arguments are omitted or replaced by other arguments, they are either
  derived  from  the  latter  or  default values are taken. The meaning of the
  other  arguments  is  defined  in the detailed description of the particular
  methods given in the sequel. The above methods return the rcwa mapping
  
  [1m[33m(a)[0m
        of [22m[34mR[0m with modulus [22m[34mmodulus[0m and coefficients [22m[34mcoeffs[0m, resp.
  
  [1m[33m(b)[0m
        of  [22m[34mR[0m  =  Z or [22m[34mR[0m = Z_(pi) with modulus [22m[32mLength([22m[34mcoeffs[0m)[0m and coefficients
        [22m[34mcoeffs[0m, resp.
  
  [1m[33m(c)[0m
        of [22m[34mR[0m = Z with modulus [22m[32mLength([22m[34mcoeffs[0m)[0m and coefficients [22m[34mcoeffs[0m, resp.
  
  [1m[33m(d)[0m
        of  [22m[34mR[0m  =  Z,  acting  on  any  set  [22m[32m[22m[34mrange[0m  +  k*Length([22m[34mrange[0m)[0m like the
        permutation [22m[34mperm[0m on the range [22m[34mrange[0m, resp.
  
  [1m[33m(e)[0m
        of  [22m[34mR[0m  = Z with modulus [22m[34mmodulus[0m and values prescribed by the list [22m[34mval[0m,
        which  consists  of  2*[22m[34mmodulus[0m  pairs  giving preimage and image for 2
        points per residue class (mod [22m[34mmodulus[0m), resp.
  
  [1m[33m(f)[0m
        of Z_(pi) with modulus [22m[32mLength([22m[34mcoeffs[0m)[0m and coefficients [22m[34mcoeffs[0m (the set
        of  primes  pi  denoting the underlying ring is given as argument [22m[34mpi[0m),
        resp.
  
  [1m[33m(g)[0m
        of GF([22m[34mq[0m)[[22m[34mx[0m] with modulus [22m[34mmodulus[0m and coefficients [22m[34mcoeffs[0m, resp.
  
  [1m[33m(h)[0m
        an  arbitrary  rcwa  mapping  which  induces  a  bijection between the
        partitions  [22m[34mP1[0m  and  [22m[34mP2[0m  of [22m[34mR[0m into disjoint single residue classes and
        which is affine on the elements of [22m[34mP1[0m, resp.
  
  [1m[33m(i)[0m
        an  arbitrary  rcwa  mapping  with  "residue class cycles" as given by
        [22m[34mcycles[0m.  The  latter  is  a  list of lists of disjoint residue classes
        which the mapping should permute cyclically, each.
  
  The  methods  for  the  operation  [22m[32mRcwaMapping[0m  perform a number of argument
  checks, which can be skipped by using [22m[32mRcwaMappingNC[0m instead.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> f := RcwaMapping([[1,1,1],[1,-1,1],[1,1,1],[1,-1,1]]);[0m
    [22m[35m<rcwa mapping of Z with modulus 2>[0m
    [22m[35mgap> f = RcwaMapping((2,3),[2..3]);[0m
    [22m[35mtrue[0m
    [22m[35mgap> g := RcwaMapping((1,2,3)(8,9),[4..20]);[0m
    [22m[35m<rcwa mapping of Z with modulus 17>[0m
    [22m[35mgap> Action(Group(g),[4..20]);[0m
    [22m[35mGroup([ (5,6) ])[0m
    [22m[35mgap> T = RcwaMapping(2,[[1,2],[2,1],[3,5],[4,2]]);[0m
    [22m[35mtrue[0m
    [22m[35mgap> t := RcwaMapping(1,[[-1,1],[1,-1]]); # The involution n -> -n.[0m
    [22m[35mRcwa mapping of Z: n -> -n[0m
    [22m[35mgap> d := RcwaMapping([2],[[1/3,0,1]]);[0m
    [22m[35mRcwa mapping of Z_( 2 ): n -> 1/3 n[0m
    [22m[35mgap> RcwaMapping([2,3],ShallowCopy(Coefficients(T)));[0m
    [22m[35m<rcwa mapping of Z_( 2, 3 ) with modulus 2>[0m
    [22m[35mgap> u := RcwaMapping([[3,0,5],[9,1,5],[3,-1,5],[9,-2,5],[9,4,5]]);[0m
    [22m[35m<rcwa mapping of Z with modulus 5>[0m
    [22m[35mgap> x := Indeterminate(GF(2),1);; SetName(x,"x");[0m
    [22m[35mgap> R := PolynomialRing(GF(2),1); z := Zero(R);; e := One(R);;[0m
    [22m[35mGF(2)[x][0m
    [22m[35mgap> r := RcwaMapping( R, x^2 + e,[0m
    [22m[35m>                      [ [ x^2 + x + e, z      , x^2 + e ],[0m
    [22m[35m>                        [ x^2 + x + e, x      , x^2 + e ],[0m
    [22m[35m>                        [ x^2 + x + e, x^2    , x^2 + e ],[0m
    [22m[35m>                        [ x^2 + x + e, x^2 + x, x^2 + e ] ] );[0m
    [22m[35m<rcwa mapping of GF(2)[x] with modulus x^2+Z(2)^0>[0m
    [22m[35mgap> rc := function(r,m) return ResidueClass(DefaultRing(m),m,r); end;;[0m
    [22m[35mgap> f1 := RcwaMapping([[rc(1,6),rc(0, 8)],[rc(5,6),rc(4, 8)]]);;[0m
    [22m[35mgap> f2 := RcwaMapping([[rc(1,6),rc(0, 4)],[rc(5,6),rc(2, 4)]]);;[0m
    [22m[35mgap> f3 := RcwaMapping([[rc(2,6),rc(1,12)],[rc(4,6),rc(7,12)]]);;[0m
    [22m[35mgap> List([f1,f2,f3],Order);[0m
    [22m[35m[ 2, 2, 2 ][0m
    [22m[35mgap> f := f1*f2*f3;[0m
    [22m[35m<bijective rcwa mapping of Z with modulus 12>[0m
    [22m[35mgap> Order(f);[0m
    [22m[35minfinity[0m
    [22m[35mgap> a := RcwaMapping([rc(0,2),rc(1,4),rc(3,4)],[rc(0,3),rc(1,3),rc(2,3)]);[0m
    [22m[35m<rcwa mapping of Z with modulus 4>[0m
    [22m[35mgap> [rc(0,2),rc(1,4),rc(3,4)]^a;[0m
    [22m[35m[ 0(3), 1(3), 2(3) ][0m
    [22m[35mgap> Cycle(a,44);[0m
    [22m[35m[ 44, 66, 99, 74, 111, 83, 62, 93, 70, 105, 79, 59 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  Some  kinds  of  very  simple-structured  rcwa  mappings  are  of particular
  interest:
  
  [1m[4m[31m2.2-2 ClassShift[0m
  
  [1m[34m> ClassShift( [0m[22m[34mr, m[0m[1m[34m ) _______________________________________________[0mfunction
  [1mReturns:[0m  The [22m[36mclass shift[0m nu_r(m).
  
  The [22m[36mclass shift[0m nu_r(m) is the rcwa mapping of Z which maps n in r(m) to n +
  m  and  fixes Z \ r(m) pointwise. The residue class [22m[32mResidueClass([22m[34mr[0m,[22m[34mm[0m)[0m itself
  can  be given in place of the arguments [22m[34mr[0m and [22m[34mm[0m. Enclosing the argument list
  in list brackets is permitted.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(ClassShift(5,12));    [0m
    [22m[35m[0m
    [22m[35mTame bijective rcwa mapping of Z with modulus 12, of order infinity[0m
    [22m[35m[0m
    [22m[35m               n mod 12                |          n^ClassShift(5,12)[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m   0  1  2  3  4  6  7  8  9 10 11     | n[0m
    [22m[35m   5                                   | n + 12[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.2-3 ClassReflection[0m
  
  [1m[34m> ClassReflection( [0m[22m[34mr, m[0m[1m[34m ) __________________________________________[0mfunction
  [1mReturns:[0m  The [22m[36mclass reflection[0m varsigma_r(m).
  
  The  [22m[36mclass reflection[0m varsigma_r(m) is the rcwa mapping of Z which maps n in
  r(m)   to   -n  +  2r  and  fixes  Z \ r(m)  pointwise.  The  residue  class
  [22m[32mResidueClass([22m[34mr[0m,[22m[34mm[0m)[0m  itself  can  be  given in place of the arguments [22m[34mr[0m and [22m[34mm[0m.
  Enclosing the argument list in list brackets is permitted.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(ClassReflection(5,9));[0m
    [22m[35m[0m
    [22m[35mBijective rcwa mapping of Z with modulus 9, of order 2[0m
    [22m[35m[0m
    [22m[35m                n mod 9                |        n^ClassReflection(5,9)[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m  0 1 2 3 4 6 7 8                      | n[0m
    [22m[35m  5                                    | -n + 10[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.2-4 ClassTransposition[0m
  
  [1m[34m> ClassTransposition( [0m[22m[34mr1, m1, r2, m2[0m[1m[34m ) _____________________________[0mfunction
  [1mReturns:[0m  The [22m[36mclass transposition[0m tau_r_1(m_1),r_2(m_2).
  
  The  [22m[36mclass  transposition[0m  tau_r_1(m_1),r_2(m_2)  is an rcwa mapping of Z of
  order 2  which  interchanges  the  disjoint  residue  classes  r_1(m_1)  and
  r_2(m_2) of Z and fixes the complement of their union pointwise. The residue
  classes  [22m[32mResidueClass([22m[34mr1[0m,[22m[34mm1[0m)[0m and [22m[32mResidueClass([22m[34mr2[0m,[22m[34mm2[0m)[0m themselves can be given
  in  place of the arguments [22m[34mr1[0m, [22m[34mm1[0m, [22m[34mr2[0m and [22m[34mm2[0m. Enclosing the argument list in
  list brackets is permitted.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(ClassTransposition(1,2,8,10));[0m
    [22m[35m[0m
    [22m[35mBijective rcwa mapping of Z with modulus 10, of order 2[0m
    [22m[35m[0m
    [22m[35m               n mod 10                |    n^ClassTransposition(1,2,8,10)[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m   0  2  4  6                          | n[0m
    [22m[35m   1  3  5  7  9                       | 5n + 3[0m
    [22m[35m   8                                   | (n - 3)/5[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.2-5 PrimeSwitch[0m
  
  [1m[34m> PrimeSwitch( [0m[22m[34mp[0m[1m[34m ) _________________________________________________[0mfunction
  [1m[34m> PrimeSwitch( [0m[22m[34mp, k[0m[1m[34m ) ______________________________________________[0mfunction
  [1mReturns:[0m  In   the   one-argument   form   the   [22m[36mprime   switch[0m  sigma_p  :=
            tau_0(8),1(2p)    *    tau_4(8),-1(2p)    *    tau_0(4),1(2p)    *
            tau_2(4),-1(2p) * tau_2(2p),1(4p) * tau_4(2p),2p+1(4p), and in the
            two-argument   form   the  restriction  of  sigma_p  by  n  ->  kn
            (cp. [1m[34mRestriction[0m ([1m3.7-1[0m)).
  
  For  an odd prime p, the [22m[36mprime switch[0m sigma_p is a bijective rcwa mapping of
  Z  with modulus 4p, multiplier p (see [1m[34mMultiplier[0m ([1m2.6-1[0m)) and divisor 2 (see
  [1m[34mDivisor[0m  ([1m2.6-2[0m)).  The  prime  switches  sigma_p  play an important role in
  factoring  non-balanced  rcwa  mappings into class shifts, class reflections
  and class transpositions (cp. [1m[34mFactorizationIntoGenerators[0m ([1m2.4-1[0m)).
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(PrimeSwitch(3));[0m
    [22m[35m[0m
    [22m[35mWild bijective rcwa mapping of Z with modulus 12[0m
    [22m[35m[0m
    [22m[35m               n mod 12                |           n^PrimeSwitch(3)[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m   0                                   | n/2[0m
    [22m[35m   1  7                                | n + 1[0m
    [22m[35m   2  6 10                             | (3n + 4)/2[0m
    [22m[35m   3  9                                | n[0m
    [22m[35m   4                                   | n - 3[0m
    [22m[35m   5  8 11                             | n - 1[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  In  most  cases  an rcwa mapping is not determined uniquely by the output of
  the  [22m[32mViewObj[0m  method  --  in these cases the output is enclosed in brackets.
  There  are  methods  installed  for  [22m[32mDisplay[0m,  [22m[32mPrint[0m and [22m[32mString[0m. The [22m[32mPrint[0med
  representation  of  an  rcwa  mapping  is  [1mGAP[0m - readable if and only if the
  [22m[32mPrint[0med  representation  of the elements of the underlying ring is so. There
  is also a method for [22m[32mLaTeXObj[0m:
  
  [1m[4m[31m2.2-6 LaTeXObj[0m
  
  [1m[34m> LaTeXObj( [0m[22m[34mf[0m[1m[34m ) ______________________________________________________[0mmethod
  [1mReturns:[0m  A LaTeX representation of the integral rcwa mapping [22m[34mf[0m.
  
  The  output  makes  use  of  the  LaTeX macro package [1mamsmath[0m. If the option
  [22m[34mFactorization[0m  is  set,  a  factorization  of  [22m[34mf[0m  into  class  shifts, class
  reflections,  class  transpositions  and  prime  switches  is  printed  (cp.
  [1m[34mFactorizationIntoGenerators[0m  ([1m2.4-1[0m)). For rcwa mappings with modulus larger
  than 1, an indentation by [22m[34mIndentation[0m characters can be specified by setting
  this option value accordingly.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Print(LaTeXObj(a));[0m
    [22m[35mn \ \longmapsto \[0m
    [22m[35m\begin{cases}[0m
    [22m[35m  \frac{3n}{2}     & \text{if} \ n \in 0(2), \\[0m
    [22m[35m  \frac{3n + 1}{4} & \text{if} \ n \in 1(4), \\[0m
    [22m[35m  \frac{3n - 1}{4} & \text{if} \ n \in 3(4).[0m
    [22m[35m\end{cases}[0m
    [22m[35mgap> Print(LaTeXObj(Comm(a,ClassShift(0,4)):Factorization));[0m
    [22m[35m      &\nu_{8(12)} \cdot \nu_{0(12)}^{-1}[0m
    [22m[35m \cdot \tau_{0(12),6(12)} \cdot \tau_{0(12),4(12)}[0m
    [22m[35m \cdot \tau_{0(12),8(12)}[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  The  [22m[32mDisplay[0m  method  recognizes the option [22m[34mxdvi[0m. If this option is set, the
  given  rcwa  mapping  is  displayed in an [1mxdvi[0m window. For this purpose, the
  string  returned by the [22m[32mLaTeXObj[0m - method described above is inserted into a
  LaTeX  template  file.  This  file is LaTeX'ed, and the result is shown with
  [1mxdvi[0m.  This works only on a UNIX system, and requires suitable installations
  of LaTeX and [1mxdvi[0m.
  
  
  [1m[4m[31m2.3 Basic functionality for rcwa mappings[0m
  
  Checking  whether two rcwa mappings are equal is cheap. Rcwa mappings can be
  multiplied,  thus  there is a method for [22m[32m*[0m. Bijective rcwa mappings can also
  be  inverted,  thus  there  is  a  method  for [22m[32mInverse[0m. The latter method is
  usually  accessed by raising a mapping to some power with negative exponent.
  Multiplying,  inverting  and  exponentiating  tame  rcwa  mappings is cheap.
  Computing powers of wild mappings is usually expensive -- runtime and memory
  requirements  normally  grow  approximately exponentially with the exponent.
  How expensive multiplying a couple of wild mappings is, varies very much. In
  any  case,  the  amount  of  memory  required for storing an rcwa mapping is
  proportional  to its modulus. Whether a given mapping is tame or wild can be
  determined  by  the operation [22m[32mIsTame[0m. There are methods for [22m[32mOrder[0m, which can
  not  only  compute  a  finite  order,  but  are  also suitable for detecting
  infinite order.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List([-6..6],k->Modulus(f^k)); Order(f);[0m
    [22m[35m[ 324, 108, 108, 36, 36, 12, 1, 12, 24, 48, 96, 192, 384 ][0m
    [22m[35minfinity[0m
    [22m[35mgap> List( [ a, u, f ], IsTame );[0m
    [22m[35m[ false, false, false ][0m
    [22m[35mgap> f^2*u;         [0m
    [22m[35m<bijective rcwa mapping of Z with modulus 120>[0m
    [22m[35mgap> f^2*u*a^2*f^-1;[0m
    [22m[35m<bijective rcwa mapping of Z with modulus 3840>[0m
    [22m[35mgap> Comm(f,ClassShift(6,12)*f)^1000;[0m
    [22m[35m<bijective rcwa mapping of Z with modulus 18>[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  There  are  methods installed for [22m[32mIsInjective[0m, [22m[32mIsSurjective[0m, [22m[32mIsBijective[0m and
  [22m[32mImage[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> [ IsInjective(T), IsSurjective(T), IsBijective(u) ];[0m
    [22m[35m[ false, true, true ][0m
    [22m[35mgap> Image(RcwaMapping([[-4,-8,1]]));[0m
    [22m[35m0(4)[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  Images  of  elements,  of  finite sets of elements and of unions of finitely
  many residue classes of the source of an rcwa mapping can be computed with [22m[32m^[0m
  (the same symbol as used for exponentiation and conjugation). The same works
  for partitions of the source into a finite number of residue classes.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> [ 15^T, 7^d, (x^3+x^2+x+One(R))^r ];[0m
    [22m[35m[ 23, 7/3, x^3+Z(2)^0 ][0m
    [22m[35mgap> A := ResidueClass(Integers,3,2);;[0m
    [22m[35mgap> [ A^T, A^u ];[0m
    [22m[35m[ 1(3) U 8(9), 1(9) U 3(9) U 14(27) U 20(27) U 26(27) ][0m
    [22m[35mgap> [rc(0,2),rc(1,4),rc(3,4)]^f;[0m
    [22m[35m[ 0(6) U 1(6) U 5(6), 2(12) U 4(12) U 9(12), 3(12) U 8(12) U 10(12) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  For  computing  preimages of elements under rcwa mappings, there are methods
  for  [22m[32mPreImageElm[0m  and  [22m[32mPreImagesElm[0m.  The  preimage  of a finite set of ring
  elements  or  of  a  union  of  finitely  many residue classes under an rcwa
  mapping can be computed using [22m[32mPreImage[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> [ PreImageElm(d,37/17), PreImagesElm(T,8), PreImagesElm(Zero(T),0) ];[0m
    [22m[35m[ 111/17, [ 5, 16 ], Integers ][0m
    [22m[35mgap> PreImage(T,ResidueClass(Integers,3,2));[0m
    [22m[35m1(2) U 4(6)[0m
    [22m[35mgap> M := [1];; l := [1];;[0m
    [22m[35mgap> while Length(M) < 10000 do M := PreImage(T,M); Add(l,Length(M)); od; l;[0m
    [22m[35m[ 1, 1, 2, 2, 4, 5, 8, 10, 14, 18, 26, 36, 50, 67, 89, 117, 157, 208, 277, [0m
    [22m[35m  367, 488, 649, 869, 1154, 1534, 2039, 2721, 3629, 4843, 6458, 8608, 11472 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  There is a method for the operation [22m[32mMovedPoints[0m for computing the support of
  a  bijective  rcwa  mapping,  and  there  is a method for [22m[32mRestrictedPerm[0m for
  computing  the restriction of a bijective rcwa mapping to a union of residue
  classes it fixes setwisely.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> [ MovedPoints(u), MovedPoints(u^2) ];[0m
    [22m[35m[ Z \ [ -1, 0 ], Z \ [ -10, -6, -1, 0, 1, 2, 3, 5 ] ][0m
    [22m[35mgap> MovedPoints(r);[0m
    [22m[35mGF(2)[x] \ [ 0*Z(2), Z(2)^0, x, x+Z(2)^0 ][0m
    [22m[35mgap> RestrictedPerm(f,ResidueClassUnion(Integers,36,[7,8]));[0m
    [22m[35m<rcwa mapping of Z with modulus 36>[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  Rcwa  mappings can be added and subtracted pointwisely. However, please note
  that  the set of rcwa mappings of some ring does not form a ring under [22m[32m+[0m and
  [22m[32m*[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> a  := RcwaMapping([[3,0,2],[3,1,4],[3,0,2],[3,-1,4]]);;[0m
    [22m[35mgap> b  := ClassShift(1,4) * a;;[0m
    [22m[35mgap> [ Image((a + b)), Image((a - b)) ];[0m
    [22m[35m[ 0(6) U 4(6) U 5(6), [ -3, 0 ] ][0m
    [22m[35mgap> d+d+d;[0m
    [22m[35mIdentityMapping( Z_( 2 ) )[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  There   are  operations  [22m[32mModulus[0m  (abbreviated  [22m[32mMod[0m)  and  [22m[32mCoefficients[0m  for
  extracting  the  modulus resp. the coefficient list of a given rcwa mapping.
  The  meaning  of  the return values is as described in the previous section.
  General  documentation  for most operations mentioned in this section can be
  found  in the [1mGAP[0m reference manual. For rcwa mappings of rings other than Z,
  not for all operations applicable methods are available.
  
  
  [1m[4m[31m2.4 Factoring rcwa mappings[0m
  
  Factoring  group  elements into elements of some "nice" set of generators is
  often  helpful.  The  following  can be seen as an attempt towards getting a
  satisfactory solution to this problem for the group RCWA(Z):
  
  [1m[4m[31m2.4-1 FactorizationIntoGenerators[0m
  
  [1m[34m> FactorizationIntoGenerators( [0m[22m[34mg[0m[1m[34m ) ________________________________[0mattribute
  [1mReturns:[0m  A factorization of the bijective rcwa mapping [22m[34mg[0m into class shifts,
            class  reflections  and class transpositions, provided that such a
            factorization exists and the method finds it.
  
  This  may  return  [22m[32mfail[0m,  stop with an error message or run into an infinite
  loop.  If  it  returns  a result, this result is always correct. By default,
  prime switches are taken as one factor. If the option [22m[34mExpandPrimeSwitches[0m is
  set,  they  are each decomposed into the 6 class transpositions given in the
  definition  (see  [1m[34mPrimeSwitch[0m  ([1m2.2-5[0m)).  By  default, the factoring process
  begins  with  splitting  off  factors from the right. This can be changed by
  setting  the  option  [22m[34mDirection[0m to [22m[32m"from the left"[0m. By default, the coarsest
  possible  respected  partition of the integral mapping occuring in the final
  stage  of  the  algorithm is computed. This can be suppressed by setting the
  option [22m[34mShortenPartition[0m equal to [22m[32mfalse[0m. By default, at the end it is checked
  whether  the  product  of the determined factors indeed equals [22m[34mg[0m. This check
  can be suppressed by setting the option [22m[34mNC[0m.
  
  The  problem  of  obtaining  a  factorization  as desired is algorithmically
  difficult,  and  this  factorization  routine  is currently perhaps the most
  sophisticated  part  of  the [1mRCWA[0m package. Information about the progress of
  the  factorization  process can be obtained by setting the info level of the
  Info class [1m[34mInfoRCWA[0m ([1m6.4-1[0m) to 2.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> FactorizationIntoGenerators(Comm(a,b));[0m
    [22m[35m[ ClassShift(7,9), ClassShift(1,9)^-1, ClassTransposition(1,9,4,9), [0m
    [22m[35m  ClassTransposition(1,9,7,9), ClassTransposition(6,18,15,18), [0m
    [22m[35m  ClassTransposition(5,9,15,18), ClassTransposition(4,9,15,18), [0m
    [22m[35m  ClassTransposition(5,9,6,18), ClassTransposition(4,9,6,18) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  For purposes of demonstrating the capabilities of the factorization routine,
  in Section [1m4.1[0m a permutation is factored which has already been mentioned by
  Lothar Collatz in 1932, and whose cycle structure is unknown so far.
  
  
  [1m[4m[31m2.5 Determinant and sign[0m
  
  [1m[4m[31m2.5-1 Determinant[0m
  
  [1m[34m> Determinant( [0m[22m[34msigma[0m[1m[34m ) _______________________________________________[0mmethod
  [1m[34m> Determinant( [0m[22m[34msigma, S[0m[1m[34m ) ____________________________________________[0mmethod
  [1mReturns:[0m  The determinant of the bijective rcwa mapping [22m[34msigma[0m.
  
  The [22m[36mdeterminant[0m of an affine mapping n -> (an+b)/c whose source is a residue
  class  r(m)  is defined by b/|a|m. This definition is extended additively to
  determinants  of  rcwa  mappings and their restrictions to unions of residue
  classes.
  
  Using  the  notation from the definition of an rcwa mapping, the [22m[36mdeterminant[0m
  det(sigma)  of  an  rcwa mapping sigma is given by (see LaTeX version of the
  manual).
  
  In  the  author's  thesis  it  is  shown  that the determinant mapping is an
  epimorphism from the group of all class-wise order-preserving bijective rcwa
  mappings of Z onto (Z,+) (see Theorem 2.11.9).
  
  If  a  residue  class union [22m[34mS[0m is given as an additional argument, the method
  returns the determinant of the restriction of [22m[34msigma[0m to [22m[34mS[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> nu := ClassShift(0,1);;[0m
    [22m[35mgap> List( [ nu, a, b, u ], Determinant );[0m
    [22m[35m[ 1, 0, 1, 0 ][0m
    [22m[35mgap> Determinant(u^2*b^-3);[0m
    [22m[35m-3[0m
    [22m[35mgap> Determinant(nu^7*a^2*nu^-1*b^-1*a^-3);[0m
    [22m[35m5[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.5-2 Sign[0m
  
  [1m[34m> Sign( [0m[22m[34msigma[0m[1m[34m ) ___________________________________________________[0mattribute
  [1mReturns:[0m  The sign of the bijective rcwa mapping [22m[34msigma[0m.
  
  Using  the  notation  from  the definition of an rcwa mapping, the [22m[36msign[0m of a
  bijective  rcwa  mapping sigma  of Z is defined by (see LaTeX version of the
  manual).
  
  In  the  author's thesis it is shown that the sign mapping is an epimorphism
  from RCWA(Z) onto the group Z^times of units of Z (see Theorem 2.12.8). This
  means that the kernel of the sign mapping is a normal subgroup of RCWA(Z) of
  index 2.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ nu, nu^2, nu^3 ], Sign );[0m
    [22m[35m[ -1, 1, -1 ][0m
    [22m[35mgap> List( [ t, nu^3*t ], Sign );[0m
    [22m[35m[ -1, 1 ][0m
    [22m[35mgap> List( [ a, a*b, (a*b)^2, Comm(a,b) ], Sign );[0m
    [22m[35m[ 1, -1, 1, 1 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.6 Attributes and properties derived from the coefficients[0m
  
  [1m[4m[31m2.6-1 Multiplier[0m
  
  [1m[34m> Multiplier( [0m[22m[34mf[0m[1m[34m ) _________________________________________________[0mattribute
  [1m[34m> Mult( [0m[22m[34mf[0m[1m[34m ) _______________________________________________________[0mattribute
  [1mReturns:[0m  The multiplier of the rcwa mapping [22m[34mf[0m.
  
  In the notation used in the definition of an rcwa mapping, the [22m[36mmultiplier[0m is
  the lcm of the coefficients a_r(m) in the numerators.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ g, u, T, d, r ], Multiplier );[0m
    [22m[35m[ 1, 9, 3, 1, x^2+x+Z(2)^0 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.6-2 Divisor[0m
  
  [1m[34m> Divisor( [0m[22m[34mf[0m[1m[34m ) ____________________________________________________[0mattribute
  [1m[34m> Div( [0m[22m[34mf[0m[1m[34m ) ________________________________________________________[0mattribute
  [1mReturns:[0m  The divisor of the rcwa mapping [22m[34mf[0m.
  
  In  the  notation  used in the definition of an rcwa mapping, the [22m[36mdivisor[0m is
  the lcm of the coefficients c_r(m) in the denominators.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ g, u, T, d, r ], Divisor );[0m
    [22m[35m[ 1, 5, 2, 1, x^2+Z(2)^0 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.6-3 PrimeSet[0m
  
  [1m[34m> PrimeSet( [0m[22m[34mf[0m[1m[34m ) ___________________________________________________[0moperation
  [1mReturns:[0m  The prime set of the rcwa mapping [22m[34mf[0m.
  
  The [22m[36mprime set[0m of an rcwa mapping is the set of prime divisors of the product
  of  its  modulus,  its multiplier and its divisor. See also [1m[34mPrimeSet[0m ([1m3.2-3[0m)
  for rcwa groups.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> PrimeSet(T);[0m
    [22m[35m[ 2, 3 ][0m
    [22m[35mgap> List( [ u, T^u, T^(u^-1) ], PrimeSet );[0m
    [22m[35m[ [ 3, 5 ], [ 2, 3 ], [ 2, 3, 5 ] ][0m
    [22m[35mgap> PrimeSet(r);[0m
    [22m[35m[ x+Z(2)^0, x^2+x+Z(2)^0 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.6-4 IsIntegral[0m
  
  [1m[34m> IsIntegral( [0m[22m[34mf[0m[1m[34m ) __________________________________________________[0mproperty
  [1mReturns:[0m  [22m[32mtrue[0m if the rcwa mapping [22m[34mf[0m is integral and [22m[32mfalse[0m otherwise.
  
  An  rcwa  mapping  is  called  [22m[36mintegral[0m if its divisor equals 1, thus "if no
  proper divisions occur". Computing with such mappings is particularly easy.
  
  Be  careful not to confuse this with the term [22m[36mintegral rcwa mapping[0m for rcwa
  mappings of the integers; normally it should be rather clear what is meant.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ u, t, RcwaMapping([[2,0,1],[3,5,1]]) ], IsIntegral );[0m
    [22m[35m[ false, true, true ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.6-5 IsClassWiseOrderPreserving[0m
  
  [1m[34m> IsClassWiseOrderPreserving( [0m[22m[34mf[0m[1m[34m ) __________________________________[0mproperty
  [1mReturns:[0m  [22m[32mtrue[0m  if  the  rcwa  mapping [22m[34mf[0m  is class-wise order-preserving and
            [22m[32mfalse[0m otherwise.
  
  The  term  [22m[36mclass-wise  order-preserving[0m is defined only for rcwa mappings of
  ordered rings, e.g. Z.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ g, u, T, t, d ], IsClassWiseOrderPreserving );[0m
    [22m[35m[ true, true, true, false, true ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.7 Functionality related to the affine partial mappings[0m
  
  [1m[4m[31m2.7-1 LargestSourcesOfAffineMappings[0m
  
  [1m[34m> LargestSourcesOfAffineMappings( [0m[22m[34mf[0m[1m[34m ) _____________________________[0mattribute
  [1mReturns:[0m  The  coarsest  partition  of  [22m[32mSource([22m[34mf[0m)[0m on whose elements the rcwa
            mapping [22m[34mf[0m is affine.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> LargestSourcesOfAffineMappings(T);[0m
    [22m[35m[ 0(2), 1(2) ][0m
    [22m[35mgap> List( [ u, u^-1 ], LargestSourcesOfAffineMappings );[0m
    [22m[35m[ [ 0(5), 1(5), 2(5), 3(5), 4(5) ], [ 0(3), 1(3), 2(9), 5(9), 8(9) ] ][0m
    [22m[35mgap> LargestSourcesOfAffineMappings(t);[0m
    [22m[35m[ Integers ][0m
    [22m[35mgap> kappa := RcwaMapping([[1,0,1],[1,0,1],[3,2,2],[1,-1,1],[0m
    [22m[35m>                          [2,0,1],[1,0,1],[3,2,2],[1,-1,1],[0m
    [22m[35m>                          [1,1,3],[1,0,1],[3,2,2],[2,-2,1]]);;[0m
    [22m[35mgap> SetName(kappa,"kappa");[0m
    [22m[35mgap> LargestSourcesOfAffineMappings(kappa);[0m
    [22m[35m[ 2(4), 1(4) U 0(12), 3(12) U 7(12), 4(12), 8(12), 11(12) ][0m
    [22m[35mgap> LargestSourcesOfAffineMappings(r);[0m
    [22m[35m[ 0*Z(2) ( mod x^2+Z(2)^0 ), Z(2)^0 ( mod x^2+Z(2)^0 ), x ( mod x^2+Z(2)^0 ), [0m
    [22m[35m  x+Z(2)^0 ( mod x^2+Z(2)^0 ) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.7-2 Multpk[0m
  
  [1m[34m> Multpk( [0m[22m[34mf, p, k[0m[1m[34m ) _______________________________________________[0moperation
  [1mReturns:[0m  The  union  of the residue classes r(m) such that p^k||a_r(m) if k
            >=  0,  and  the  union  of  the  residue  classes  r(m) such that
            p^k||c_r(m) if k <= 0.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> [ Multpk(T,2,-1), Multpk(T,3,1) ];[0m
    [22m[35m[ Integers, 1(2) ][0m
    [22m[35mgap> [ Multpk(u,3,0), Multpk(u,3,1), Multpk(u,3,2), Multpk(u,5,-1) ];[0m
    [22m[35m[ [  ], 0(5) U 2(5), 1(5) U 3(5) U 4(5), Integers ][0m
    [22m[35mgap> [ Multpk(kappa,2,1), Multpk(kappa,2,-1), Multpk(kappa,3,1),[0m
    [22m[35m>      Multpk(kappa,3,-1) ];[0m
    [22m[35m[ 4(12) U 11(12), 2(4), 2(4), 8(12) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.7-3 SetOnWhichMappingIsClassWiseOrderPreserving[0m
  
  [1m[34m> SetOnWhichMappingIsClassWiseOrderPreserving( [0m[22m[34mf[0m[1m[34m ) ________________[0mattribute
  [1m[34m> SetOnWhichMappingIsClassWiseConstant( [0m[22m[34mf[0m[1m[34m ) _______________________[0mattribute
  [1m[34m> SetOnWhichMappingIsClassWiseOrderReversing( [0m[22m[34mf[0m[1m[34m ) _________________[0mattribute
  [1mReturns:[0m  The  union  of  the  residue classes (mod [22m[32mModulus([22m[34mf[0m)[0m) on which the
            rcwa mapping [22m[34mf[0m is class-wise order-preserving, class-wise constant
            resp. class-wise order-reversing.
  
  The source of the rcwa mapping [22m[34mf[0m must be ordered.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ T, u, t ], SetOnWhichMappingIsClassWiseOrderPreserving );[0m
    [22m[35m[ Integers, Integers, [  ] ][0m
    [22m[35mgap> SetOnWhichMappingIsClassWiseConstant(RcwaMapping([[2,0,1],[0,4,1]]));[0m
    [22m[35m1(2)[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.8 Transition graphs and transition matrices[0m
  
  [1m[4m[31m2.8-1 TransitionGraph[0m
  
  [1m[34m> TransitionGraph( [0m[22m[34mf, m[0m[1m[34m ) _________________________________________[0moperation
  [1mReturns:[0m  The transition graph for modulus [22m[34mm[0m of the rcwa mapping [22m[34mf[0m.
  
  The [22m[36mtransition graph[0m Gamma_f,m of f for modulus m is defined as follows:
  
  (1)   The vertices are the residue classes (mod m).
  
  (2)   There  is  an  edge from r_1(m) to r_2(m) if and only if there is some
        n_1 in r_1(m) such that n_1^f in r_2(m).
  
  The  assignment  of the residue classes (mod m) to the vertices of the graph
  is  given  by  the ordering of the residues in [22m[32mAllResidues(Source([22m[34mf[0m),[22m[34mm[0m)[0m. The
  result is returned as a [1mGRAPE[0m-graph.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> TransitionGraph(a,Modulus(a));[0m
    [22m[35mrec( isGraph := true, order := 4, group := Group(()), [0m
    [22m[35m  schreierVector := [ -1, -2, -3, -4 ], [0m
    [22m[35m  adjacencies := [ [ 1, 3 ], [ 1, 2, 3, 4 ], [ 2, 4 ], [ 1, 2, 3, 4 ] ], [0m
    [22m[35m  representatives := [ 1, 2, 3, 4 ], names := [ 1, 2, 3, 4 ] )[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.8-2 OrbitsModulo[0m
  
  [1m[34m> OrbitsModulo( [0m[22m[34mf, m[0m[1m[34m ) ____________________________________________[0moperation
  [1mReturns:[0m  The  partition  of  [22m[32mAllResidues(Source([22m[34mf[0m),[22m[34mm[0m)[0m  corresponding to the
            weakly-connected  components of the transition graph for modulus [22m[34mm[0m
            of the rcwa mapping [22m[34mf[0m.
  
  See also [1m[34mOrbitsModulo[0m ([1m3.5-6[0m) for rcwa groups.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> OrbitsModulo(Comm(a,b),9);[0m
    [22m[35m[ [ 0 ], [ 1, 4, 5, 6, 7 ], [ 2 ], [ 3 ], [ 8 ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.8-3 FactorizationOnConnectedComponents[0m
  
  [1m[34m> FactorizationOnConnectedComponents( [0m[22m[34mf, m[0m[1m[34m ) ______________________[0moperation
  [1mReturns:[0m  The   set   of   restrictions   of   the  rcwa  mapping [22m[34mf[0m  to  the
            weakly-connected components of its transition graph Gamma_f,m.
  
  These  mappings  have  pairwisely  disjoint  supports, hence any two of them
  commute, and their product equals [22m[34mf[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> sigma := RcwaMapping([[1, 0,1],[1, 1,1],[2,2,1],[3,-3,2],[0m
    [22m[35m>                          [1, 0,1],[1,-2,3],[3,6,2],[1,-2,1],[0m
    [22m[35m>                          [1, 0,1],[1, 1,1],[1,1,1],[1,-2,1],[0m
    [22m[35m>                          [2, 0,1],[1, 1,1],[1,1,1],[3,-3,2],[0m
    [22m[35m>                          [1, 0,1],[1, 1,1],[3,6,2],[1,-2,1],[0m
    [22m[35m>                          [1, 0,1],[1, 1,1],[1,1,1],[2,-4,1],[0m
    [22m[35m>                          [1,-3,3],[1, 1,1],[1,1,1],[3,-3,2],[0m
    [22m[35m>                          [1, 0,1],[2, 2,1],[3,6,2],[1,-2,1],[0m
    [22m[35m>                          [1, 0,1],[1, 1,1],[1,1,1],[1,-2,1]]);[0m
    [22m[35m<rcwa mapping of Z with modulus 36>[0m
    [22m[35mgap> fact := FactorizationOnConnectedComponents(sigma,36);[0m
    [22m[35m[ <rcwa mapping of Z with modulus 36>, <rcwa mapping of Z with modulus 36>, [0m
    [22m[35m  <rcwa mapping of Z with modulus 36> ][0m
    [22m[35mgap> List(fact,MovedPoints);[0m
    [22m[35m[ 33(36) U 34(36) U 35(36), 9(36) U 10(36) U 11(36), [0m
    [22m[35m  <union of 23 residue classes (mod 36)> \ [ -6, 3 ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.8-4 TransitionMatrix[0m
  
  [1m[34m> TransitionMatrix( [0m[22m[34mf, m[0m[1m[34m ) _________________________________________[0mfunction
  [1mReturns:[0m  The transition matrix of the rcwa mapping [22m[34mf[0m for modulus [22m[34mm[0m.
  
  Let  M  be  this  matrix. Then for any two residue classes r_1(m), r_2(m) in
  R/mR, the entry M_r_1(m),r_2(m) is defined by
  
  (See  LaTeX  version  of  the manual.) The assignment of the residue classes
  (mod [22m[34mm[0m)  to  the  rows and columns of the matrix is given by the ordering of
  the residues in [22m[32mAllResidues(Source([22m[34mf[0m),[22m[34mm[0m)[0m.
  
  The  transition  matrix  is a weighted adjacency matrix of the corresponding
  transition  graph [22m[32mTransitionGraph([22m[34mf[0m,[22m[34mm[0m)[0m. The sums of the rows of a transition
  matrix are always equal to 1.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(TransitionMatrix(a,5));[0m
    [22m[35m[ [  1/2,  1/4,    0,    0,  1/4 ],[0m
    [22m[35m  [    0,  1/4,    0,  1/4,  1/2 ],[0m
    [22m[35m  [  1/4,    0,    0,  3/4,    0 ],[0m
    [22m[35m  [  1/4,    0,  3/4,    0,    0 ],[0m
    [22m[35m  [    0,  1/2,  1/4,    0,  1/4 ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(TransitionMatrix(T,19)*One(GF(7)));[0m
    [22m[35m 4 . . . . . . . . . 4 . . . . . . . .[0m
    [22m[35m . . 4 . . . . . . . 4 . . . . . . . .[0m
    [22m[35m . 4 . . . . . . . . . . . 4 . . . . .[0m
    [22m[35m . . . . . 4 . . . . . 4 . . . . . . .[0m
    [22m[35m . . 4 . . . . . . . . . . . . . 4 . .[0m
    [22m[35m . . . . . . . . 4 . . . 4 . . . . . .[0m
    [22m[35m 4 . . 4 . . . . . . . . . . . . . . .[0m
    [22m[35m . . . . . . . . . . . 4 . 4 . . . . .[0m
    [22m[35m . . . 4 4 . . . . . . . . . . . . . .[0m
    [22m[35m . . . . . . . . . . . . . . 1 . . . .[0m
    [22m[35m . . . . . 4 4 . . . . . . . . . . . .[0m
    [22m[35m . . . . . . . . . . . . . . . 4 . 4 .[0m
    [22m[35m . . . . . . 4 . . 4 . . . . . . . . .[0m
    [22m[35m . 4 . . . . . . . . . . . . . . 4 . .[0m
    [22m[35m . . . . . . . 4 . . . . 4 . . . . . .[0m
    [22m[35m . . . . 4 . . . . . . . . . . . . 4 .[0m
    [22m[35m . . . . . . . . 4 . . . . . . 4 . . .[0m
    [22m[35m . . . . . . . 4 . . . . . . . . . . 4[0m
    [22m[35m . . . . . . . . . 4 . . . . . . . . 4[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.9 Trajectories[0m
  
  [1m[4m[31m2.9-1 Trajectory[0m
  
  [1m[34m> Trajectory( [0m[22m[34mf, n, val, cond[0m[1m[34m ) ____________________________________[0mfunction
  [1mReturns:[0m  The trajectory of the ring element [22m[34mn[0m under the rcwa mapping [22m[34mf[0m.
  
  Depending  on  whether  [22m[32m[22m[34mcond[0m  = "length"[0m or [22m[32m[22m[34mcond[0m = "stop"[0m, the parameter [22m[34mval[0m
  either  is  the length of the sequence to be computed or is a "stopping set"
  such that the computation stops when some iterate [22m[32m[22m[34mn[0m^([22m[34mf[0m^k) in [22m[34mval[0m[0m is reached.
  In  place  of  the  ring element [22m[34mn[0m, a union of residue classes is permitted,
  also.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Trajectory(T,27,[1],"stop");[0m
    [22m[35m[ 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, [0m
    [22m[35m  233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, [0m
    [22m[35m  425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, [0m
    [22m[35m  3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, [0m
    [22m[35m  23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1 ][0m
    [22m[35mgap> Trajectory(T,ResidueClass(Integers,3,0),Integers,"stop");[0m
    [22m[35m[ 0(3), 0(3) U 5(9), 0(3) U 5(9) U 7(9) U 8(27), [0m
    [22m[35m  <union of 20 residue classes (mod 27)>, <union of 73 residue classes (mod [0m
    [22m[35m    81)>, <union of 79 residue classes (mod 81)>, Integers ][0m
    [22m[35mgap> Length(Trajectory(RcwaMapping([[1,0,2],[5,-1,2]]),19,[1],"stop"));[0m
    [22m[35m307[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.9-2 TrajectoryModulo[0m
  
  [1m[34m> TrajectoryModulo( [0m[22m[34mf, n, m, lng[0m[1m[34m ) _________________________________[0mfunction
  [1m[34m> TrajectoryModulo( [0m[22m[34mf, n, lng[0m[1m[34m ) ____________________________________[0mfunction
  [1mReturns:[0m  The  sequence  (n_i), i = 0, dots, lng-1 with n_i := n^(f^i) mod [22m[34mm[0m
            as a list.
  
  If [22m[34mm[0m is not given it defaults to the modulus of [22m[34mf[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> TrajectoryModulo(a,8,25);[0m
    [22m[35m[ 0, 0, 2, 3, 0, 2, 1, 2, 3, 2, 1, 3, 0, 0, 0, 0, 2, 3, 2, 1, 1, 2, 3, 1, 2 ][0m
    [22m[35mgap> TrajectoryModulo(T,27,2,100);[0m
    [22m[35m[ 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, [0m
    [22m[35m  0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, [0m
    [22m[35m  1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, [0m
    [22m[35m  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.9-3 CoefficientsOnTrajectory[0m
  
  [1m[34m> CoefficientsOnTrajectory( [0m[22m[34mf, n, val, cond, all[0m[1m[34m ) _________________[0mfunction
  [1mReturns:[0m  A list [22m[32mc[0m of coefficient triples, such that for any [22m[32mk[0m it holds that
            [22m[32m[22m[34mn[0m^([22m[34mf[0m^(k-1)) = (c[k][1]*[22m[34mn[0m + c[k][2])/c[k][3][0m, or its last entry.
  
  The  meaning  of  the  arguments  [22m[34mval[0m  and [22m[34mcond[0m is the same as in [1m[34mTrajectory[0m
  ([1m2.9-1[0m).  If  [22m[32m[22m[34mall[0m  =  true[0m,  the  whole  sequence  of coefficient triples is
  returned. Otherwise the result is only the last triple.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> CoefficientsOnTrajectory(T,27,1,"stop",false);[0m
    [22m[35m[ 36472996377170786403, 195820718533800070543, 1180591620717411303424 ][0m
    [22m[35mgap> (last[1]*27+last[2])/last[3];[0m
    [22m[35m1[0m
    [22m[35mgap> CoefficientsOnTrajectory(sigma,37,37,"stop",true);[0m
    [22m[35m[ [ 1, 0, 1 ], [ 1, 1, 1 ], [ 2, 4, 1 ], [ 3, 9, 1 ], [ 6, 18, 1 ], [0m
    [22m[35m  [ 2, 5, 1 ], [ 2, 3, 1 ], [ 2, 1, 3 ], [ 2, 4, 3 ], [ 2, 7, 3 ], [0m
    [22m[35m  [ 1, 2, 1 ], [ 3, 3, 2 ], [ 3, 5, 2 ], [ 3, 7, 2 ], [ 3, 3, 1 ], [0m
    [22m[35m  [ 9, 15, 2 ], [ 27, 57, 4 ], [ 27, 57, 2 ], [ 9, 17, 2 ], [ 9, 13, 2 ], [0m
    [22m[35m  [ 9, 15, 1 ], [ 3, 4, 1 ], [ 3, 2, 1 ], [ 1, 0, 1 ] ][0m
    [22m[35mgap> List(last,c->(c[1]*37+c[2])/c[3]){[1..23]} = Cycle(sigma,37);[0m
    [22m[35mtrue[0m
    [22m[35mgap> CoefficientsOnTrajectory(r,x^3+x^2,x^3+x^2,"stop",true);[0m
    [22m[35m[ [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ x^2+x+Z(2)^0, x^2+x, x^2+Z(2)^0 ], [0m
    [22m[35m  [ x^4+x^2+Z(2)^0, x^4+x, x^4+Z(2)^0 ], [0m
    [22m[35m  [ x^6+x^5+x^3+x+Z(2)^0, x^6+x^4+x^3+x^2, x^6+x^4+x^2+Z(2)^0 ], [0m
    [22m[35m  [ x^8+x^4+Z(2)^0, x^7+x^6, x^8+Z(2)^0 ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.9-4 IncreasingOn[0m
  
  [1m[34m> IncreasingOn( [0m[22m[34mf[0m[1m[34m ) ________________________________________________[0mfunction
  [1m[34m> DecreasingOn( [0m[22m[34mf[0m[1m[34m ) ________________________________________________[0mfunction
  [1mReturns:[0m  The  union  of  all  residue  classes r(m) such that |R/a_r(m)R| >
            |R/c_r(m)R|  resp.  |R/a_r(m)R| < |R/c_r(m)R|, where R denotes the
            source,   m   the  modulus  and  a_r(m),  b_r(m)  and  c_r(m)  the
            coefficients  of [22m[34mf[0m  as  introduced  in  the  definition of an rcwa
            mapping.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List([1..3],k->IncreasingOn(T^k));[0m
    [22m[35m[ 1(2), 3(4), 3(4) U 1(8) U 6(8) ][0m
    [22m[35mgap> List([1..3],k->DecreasingOn(T^k));[0m
    [22m[35m[ 0(2), 0(2) U 1(4), 0(4) U 2(8) U 5(8) ][0m
    [22m[35mgap> List([1..3],k->IncreasingOn(a^k));[0m
    [22m[35m[ 0(2), 0(2) U 3(8) U 5(8), 0(4) U 2(16) U 5(16) U 11(16) U 14(16) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.10 Special functions for non-bijective mappings and miscellanea[0m
  
  [1m[4m[31m2.10-1 LikelyContractionCentre[0m
  
  [1m[34m> LikelyContractionCentre( [0m[22m[34mf, maxn, bound[0m[1m[34m ) _______________________[0moperation
  [1mReturns:[0m  A list of ring elements -- see below.
  
  Tries  to  compute  the [22m[36mcontraction centre[0m of an rcwa mapping - assuming its
  existence  this is the uniquely-defined finite subset S_0 of the base ring R
  which  is  mapped  bijectively  onto itself under [22m[34mf[0m and where for any x in R
  there  is  an  integer k  such that the image of x under the k-th power of f
  lies in S_0. The mapping [22m[34mf[0m is assumed to be [22m[36mcontracting[0m, i.e. to have such a
  contraction  centre. As this problem seems to be computationally undecidable
  methods  will be probabilistic. The argument [22m[34mmaxn[0m is a bound on the starting
  value  and [22m[34mbound[0m is a bound on the elements of the sequences to be searched.
  If  the  limit  [22m[34mbound[0m  is  exceeded,  an  Info message on some Info level of
  [22m[32mInfoRCWA[0m is given.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> S0 := LikelyContractionCentre(T,100,1000);[0m
    [22m[35m#I  Warning: `LikelyContractionCentre' is highly probabilistic.[0m
    [22m[35mThe returned result can only be regarded as a rough guess.[0m
    [22m[35mSee ?LikelyContractionCentre for information on how to improve this guess.[0m
    [22m[35m[ -136, -91, -82, -68, -61, -55, -41, -37, -34, -25, -17, -10, -7, -5, -1, 0, [0m
    [22m[35m  1, 2 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.10-2 GuessedDivergence[0m
  
  [1m[34m> GuessedDivergence( [0m[22m[34mf[0m[1m[34m ) __________________________________________[0moperation
  [1mReturns:[0m  A  floating point value, which should be a rough guess on how fast
            the  trajectories  of  the  rcwa  mapping [22m[34mf[0m  diverge (return value
            greater than 1) or converge (return value smaller than 1).
  
  Nothing particular is guaranteed.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ T, a ], GuessedDivergence );[0m
    [22m[35m#I  Warning: GuessedDivergence: no particular return value is guaranteed.[0m
    [22m[35m#I  Warning: GuessedDivergence: no particular return value is guaranteed.[0m
    [22m[35m[ 0.866025, 1.06066 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.10-3 ImageDensity[0m
  
  [1m[34m> ImageDensity( [0m[22m[34mf[0m[1m[34m ) _______________________________________________[0mattribute
  [1mReturns:[0m  The [22m[36mimage density[0m of the rcwa mapping [22m[34mf[0m.
  
  In  the  notation introduced in the definition of an rcwa mapping, the [22m[36mimage
  density[0m  of f is defined by frac1m sum_r(m) in R/mR |R/c_r(m)R|/|R/a_r(m)R|.
  Injective  rcwa  mappings  have an image density of at most 1, and the image
  density of a surjective rcwa mapping is at least 1 (this can be seen easily)
  -- thus in particular the image density of a bijective mapping equals 1.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> List( [ T, a, RcwaMapping([[2,0,1]]) ], ImageDensity );[0m
    [22m[35m[ 4/3, 1, 1/2 ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.10-4 RightInverse[0m
  
  [1m[34m> RightInverse( [0m[22m[34mf[0m[1m[34m ) _______________________________________________[0mattribute
  [1mReturns:[0m  A  right inverse of the injective rcwa mapping [22m[34mf[0m, i.e. a mapping g
            such that [22m[34mf[0mg = 1.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> RcwaMapping([[2,0,1]]);                       [0m
    [22m[35mRcwa mapping of Z: n -> 2n[0m
    [22m[35mgap> Display(RightInverse(last));[0m
    [22m[35m[0m
    [22m[35mRcwa mapping of Z with modulus 2[0m
    [22m[35m[0m
    [22m[35m                n mod 2                |                 n^f[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m  0                                    | n/2[0m
    [22m[35m  1                                    | n[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.10-5 CommonRightInverse[0m
  
  [1m[34m> CommonRightInverse( [0m[22m[34ml, r[0m[1m[34m ) ______________________________________[0moperation
  [1mReturns:[0m  A mapping d such that [22m[34ml[0md = [22m[34mr[0md = 1.
  
  The  mappings  [22m[34ml[0m  and  [22m[34mr[0m  must  be  injective,  and their images must form a
  partition of the underlying ring.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Display(CommonRightInverse(RcwaMapping([[2,0,1]]),[0m
    [22m[35m>                               RcwaMapping([[2,1,1]])));[0m
    [22m[35m[0m
    [22m[35mRcwa mapping of Z with modulus 2[0m
    [22m[35m[0m
    [22m[35m                n mod 2                |                 n^f[0m
    [22m[35m---------------------------------------+--------------------------------------[0m
    [22m[35m  0                                    | n/2[0m
    [22m[35m  1                                    | (n - 1)/2[0m
    [22m[35m[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.11 The categories and families of rcwa mappings[0m
  
  [1m[4m[31m2.11-1 IsRcwaMapping[0m
  
  [1m[34m> IsRcwaMapping( [0m[22m[34mf[0m[1m[34m ) _________________________________________________[0mfilter
  [1m[34m> IsIntegralRcwaMapping( [0m[22m[34mf[0m[1m[34m ) _________________________________________[0mfilter
  [1m[34m> IsSemilocalIntegralRcwaMapping( [0m[22m[34mf[0m[1m[34m ) ________________________________[0mfilter
  [1m[34m> IsModularRcwaMapping( [0m[22m[34mf[0m[1m[34m ) __________________________________________[0mfilter
  [1mReturns:[0m  [22m[32mtrue[0m  if [22m[34mf[0m is an rcwa mapping resp. an rcwa mapping of the ring of
            integers  resp.  an rcwa mapping of a semilocalization of the ring
            of  integers  resp.  an  rcwa  mapping of a polynomial ring in one
            variable over a finite field, and [22m[32mfalse[0m otherwise.
  
  [1m[4m[31m2.11-2 RcwaMappingsFamily[0m
  
  [1m[34m> RcwaMappingsFamily( [0m[22m[34mR[0m[1m[34m ) __________________________________________[0mfunction
  [1mReturns:[0m  The family of rcwa mappings of the ring [22m[34mR[0m.
  
