  
  [1m[4m[31m5. The Algorithms Implemented in RCWA[0m
  
  This  chapter  lists  brief  descriptions  of  most  algorithms  and methods
  implemented  in  this package. These descriptions are kept very informal and
  short,  and  some  of  them  provide  only rudimentary information. They are
  listed in alphabetical order. The word "trivial" as a description means that
  essentially  nothing  is  done except of storing or recalling one or several
  values, and "straightforward" means that no sophisticated algorithm is used.
  
  [1m[33m
      [22m[32mActionOnRespectedPartition([22m[34mG[0m)[0m
    [0m
        "Straightforward"  after  having  computed  a  respected  partition by
        [22m[32mRespectedPartition[0m.  One  only  needs to know how to compute images of
        residue classes under affine mappings.
  
  [1m[33m
      [22m[32mBall([22m[34mG[0m,[22m[34mg[0m,[22m[34md[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mBall([22m[34mG[0m,[22m[34mp[0m,[22m[34md[0m,[22m[34mact[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mClassReflection([22m[34mr[0m,[22m[34mm[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mClassShift([22m[34mr[0m,[22m[34mm[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mClassTransposition([22m[34mr1[0m,[22m[34mm1[0m,[22m[34mr2[0m,[22m[34mm2[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mCoefficients([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mCommonRightInverse([22m[34ml[0m,[22m[34mr[0m)[0m
    [0m
        (See [22m[32mRightInverse[0m.)
  
  [1m[33m
      [22m[32mDecreasingOn([22m[34mf[0m)[0m
    [0m
        Forms  the  union  of  the residue classes which are determined by the
        coefficients as indicated.
  
  [1m[33m
      [22m[32mDeterminant([22m[34mg[0m)[0m
    [0m
        Evaluation  of  the  given  expression.  For  the mathematical meaning
        (epimorphism!), see Theorem2.11.9 in[K05].
  
  [1m[33m
      [22m[32mDirectProduct([22m[34mG1[0m,[22m[34mG2[0m, ... )[0m
    [0m
        Restricts  the  groups  [22m[34mG1[0m,  [22m[34mG2[0m,  ... to disjoint residue classes. See
        [22m[32mRestriction[0m and Corollary2.3.3 in[K05].
  
  [1m[33m
      [22m[32mDisplay([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mDivisor([22m[34mf[0m)[0m
    [0m
        Lcm of coefficients, as indicated.
  
  [1m[33m
      [22m[32mFactorizationIntoCSCRCT([22m[34mg[0m)[0m
    [0m
        This uses a rather sophisticated method which will likely some time be
        published  elsewhere. At the moment termination is not guaranteed, but
        in  case of termination the result is certain. The strategy is roughly
        first  to  make  the mapping class-wise order-preserving and balanced,
        and  then  to remove all prime factors from multiplier and divisor one
        after  the  other in decreasing order by dividing by appropriate class
        transpositions.  The remaining integral mapping can be factored almost
        similarly easily as a permutation of a finite set can be factored into
        transpositions.
  
  [1m[33m
      [22m[32mFactorizationOnConnectedComponents([22m[34mf[0m,[22m[34mm[0m)[0m
    [0m
        Calls  [1mGRAPE[0m  to get the connected components of the transition graph,
        and  then  computes a partition of the suitably "blown up" coefficient
        list corresponding to the connected components.
  
  [1m[33m
      [22m[32mFixedPointsOfAffinePartialMappings([22m[34mf[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mGuessedDivergence([22m[34mf[0m)[0m
    [0m
        Numerical  computation  of  the  limit  of some series, which seems to
        converge "often". Caution!!!
  
  [1m[33m
      [22m[32mImage([22m[34mf[0m)[0m, [22m[32mImage([22m[34mf[0m,[22m[34mS[0m)[0m
    [0m
        "Straightforward"  if  one can compute images of residue classes under
        affine  mappings  and  unite  and  intersect  residue classes (Chinese
        Remainder Theorem). See Lemma1.2.1 in[K05].
  
  [1m[33m
      [22m[32mImageDensity([22m[34mf[0m)[0m
    [0m
        Evaluation of the given expression.
  
  [1m[33m
      [22m[32m[22m[34mg[0m in [22m[34mG[0m[0m (membership test)
    [0m
        Test whether the mapping [22m[34mg[0m or its inverse is in the list of generators
        of[22m[34mG[0m. If it is, return [22m[32mtrue[0m. Test whether its prime set is a subset of
        the  prime set of[22m[34mG[0m. If not, return [22m[32mfalse[0m. Test whether the multiplier
        or  the  divisor  of[22m[34mg[0m  has  a  prime factor which does not divide the
        multiplier  of[22m[34mG[0m.  If  yes,  return  [22m[32mfalse[0m.  Test  if  [22m[34mG[0m is class-wise
        order-preserving,  and [22m[34mg[0m is not. If so, return [22m[32mfalse[0m. Test if the sign
        of  [22m[34mg[0m is-1 and all generators of[22m[34mG[0m have sign1. If yes, return [22m[32mfalse[0m.
        Test  if  [22m[34mG[0m  is  class-wise order-preserving, all generators of[22m[34mG[0m have
        determinant0  and  [22m[34mg[0m has determinant<> 0. If yes, return [22m[32mfalse[0m. Test
        whether  the  support  of[22m[34mg[0m  is  a subset of the support of[22m[34mG[0m. If not,
        return [22m[32mfalse[0m. Test whether [22m[34mG[0m fixes the nonnegative integers setwisely,
        but[22m[34mg[0m does not. If yes, return [22m[32mfalse[0m.
  
        If  [22m[34mG[0m  is  tame,  proceed  as  follows:  Test whether the modulus of [22m[34mg[0m
        divides  the  modulus  of  [22m[34mG[0m.  If not, return [22m[32mfalse[0m. Test whether [22m[34mG[0m is
        finite  and  [22m[34mg[0m has infinite order. If so, return [22m[32mfalse[0m. Test whether [22m[34mg[0m
        is  tame.  If  not, return [22m[32mfalse[0m. Compute a respected partition [22m[32mP[0m of [22m[34mG[0m
        and   the  finite  permutation  group  [22m[32mH[0m  induced  by  [22m[34mG[0m  on  it  (see
        [22m[32mRespectedPartition[0m). Check whether [22m[34mg[0m permutes [22m[32mP[0m. If not, return [22m[32mfalse[0m.
        Let [22m[32mh[0m be the permutation induced by [22m[34mg[0m on [22m[32mP[0m. Check whether [22m[32mh[0m lies in [22m[32mH[0m.
        If  not,  return  [22m[32mfalse[0m.  Compute  an  element [22m[32mg1[0m of [22m[34mG[0m which acts on[22m[32mP[0m
        like[22m[34mg[0m.  For  this  purpose,  factor  [22m[34mh[0m  into  generators  of[22m[32mH[0m  using
        [22m[32mPreImagesRepresentative[0m,  and  compute  the  corresponding  product of
        generators  of[22m[34mG[0m.  Let  [22m[32mk  :=  g/g1[0m. The mapping [22m[32mk[0m is always integral.
        Compute    the    kernel[22m[32mK[0m   of   the   action   of   [22m[34mG[0m   on[22m[32mP[0m   using
        [22m[32mKernelOfActionOnRespectedPartition[0m. Check whether [22m[32mk[0m lies in[22m[32mK[0m. This is
        done using the package [1mPolycyclic[0m[EN03], and uses an isomorphism from
        a  supergroup of [22m[32mK[0m which is isomorphic to the [22m[32m|P|[0m-fold direct product
        of  the  infinite  dihedral  group  and  which  always contains[22m[32mk[0m to a
        polycyclically presented group. If[22m[32mk[0m lies in[22m[32mK[0m, return [22m[32mtrue[0m, otherwise
        return [22m[32mfalse[0m.
  
        If  [22m[34mG[0m is not tame, proceed as follows: Look for finite orbits of[22m[34mG[0m. If
        some  are  found, test whether [22m[34mg[0m acts on them, and whether the induced
        permutations lie in the permutation groups induced by[22m[34mG[0m. If for one of
        the  examined  orbits  one  of the latter two questions has a negative
        answer,  then  return [22m[32mfalse[0m. Look for a positive integerm such that [22m[34mg[0m
        does not leave a partition ofZ into unions of residue classes (modm)
        invariant  which  is  fixed by[22m[34mG[0m. If successful, return [22m[32mfalse[0m. If not,
        try to factor [22m[34mg[0m into generators of[22m[34mG[0m using [22m[32mPreImagesRepresentative[0m. If
        successful,  return [22m[32mtrue[0m. If [22m[34mg[0m is in [22m[34mG[0m, this terminates after a finite
        number  of steps. Both runtime and memory requirements are exponential
        in the word length. If [22m[34mg[0m is not in [22m[34mG[0m, the method runs into an infinite
        loop.
  
  [1m[33m
      [22m[32mIncreasingOn([22m[34mf[0m)[0m
    [0m
        Forms  the  union  of  the residue classes which are determined by the
        coefficients as indicated.
  
  [1m[33m
      [22m[32mInduction([22m[34mg[0m,[22m[34mf[0m)[0m
    [0m
        Computes [22m[32mf * g * RightInverse([22m[34mf[0m)[0m.
  
  [1m[33m
      [22m[32mInduction([22m[34mG[0m,[22m[34mf[0m)[0m
    [0m
        Gets  a set of generators by applying [22m[32mInduction([22m[34mg[0m,[22m[34mf[0m)[0m to the generators
        [22m[34mg[0m of[22m[34mG[0m.
  
  [1m[33m
      [22m[32mInjectiveAsMappingFrom([22m[34mf[0m)[0m
    [0m
        The  function starts with the entire source of [22m[34mf[0m as "preimage" [22m[32mpre[0m and
        the  empty  set  as  "image"[22m[32mim[0m.  It  loops  over  the residue classes
        (mod[22m[32mMod([22m[34mf[0m)[0m).  For  any  such  residue class [22m[32mcl[0m the following is done:
        Firstly,  the  image  of  [22m[32mcl[0m  under[22m[34mf[0m  is  added  to[22m[32mim[0m. Secondly, the
        intersection  of  the  preimage of the intersection of the image of [22m[32mcl[0m
        under [22m[34mf[0m and [22m[32mim[0m under [22m[34mf[0m and [22m[32mcl[0m is subtracted from[22m[32mpre[0m.
  
  [1m[33m
      [22m[32mIntegralConjugate([22m[34mf[0m)[0m, 
      [22m[32mIntegralConjugate([22m[34mG[0m)[0m
    [0m
        Uses the algorithm described in the proof of Theorem2.5.14 in[K05].
  
  [1m[33m
      [22m[32mIntegralizingConjugator([22m[34mf[0m)[0m, 
      [22m[32mIntegralizingConjugator([22m[34mG[0m)[0m
    [0m
        Uses the algorithm described in the proof of Theorem2.5.14 in[K05].
  
  [1m[33m
      [22m[32mInverse([22m[34mf[0m)[0m
    [0m
        Essentially  inversion  of  affine mappings. See Lemma1.3.1, Part(b)
        in[K05].
  
  [1m[33m
      [22m[32mIsClassWiseOrderPreserving([22m[34mf[0m)[0m
    [0m
        Tests whether the first entry of all coefficient triples is positive.
  
  [1m[33m
      [22m[32mIsConjugate(RCWA(Integers),[22m[34mf[0m,[22m[34mg[0m)[0m
    [0m
        Test  whether  [22m[34mf[0m and [22m[34mg[0m have the same order, and whether either both or
        none of them is tame. If not, return [22m[32mfalse[0m.
  
        If  the mappings are wild, use [22m[32mShortCycles[0m to search for finite cycles
        not  belonging  to  an  infinite  series,  until  their  numbers for a
        particular  length  differ.  This may run into an infinite loop. If it
        terminates, return [22m[32mfalse[0m.
  
        If  the  mappings  are  tame, use the method described in the proof of
        Theorem2.5.14  in[K05]  to construct integral conjugates of [22m[34mf[0m and [22m[34mg[0m.
        Then   essentially  use  the  algorithm  described  in  the  proof  of
        Theorem2.6.7  in[K05]  to  compute "standard representatives" of the
        conjugacy  classes which the integral conjugates of [22m[34mf[0m and [22m[34mg[0m belong to.
        Finally  compare  these  standard  representatives, and return [22m[32mtrue[0m if
        they are equal and [22m[32mfalse[0m if not.
  
  [1m[33m
      [22m[32mIsInjective([22m[34mf[0m)[0m
    [0m
        See [22m[32mImage[0m.
  
  [1m[33m
      [22m[32mIsIntegral([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mIsomorphismMatrixGroup([22m[34mG[0m)[0m
    [0m
        Uses the algorithm described in the proof of Theorem2.6.3 in[K05].
  
  [1m[33m
      [22m[32mIsomorphismPermGroup([22m[34mG[0m)[0m
    [0m
        If  the  group  [22m[34mG[0m  is  infinite,  there  is no isomorphism to a finite
        permutation     group,     thus    return    [22m[32mfail[0m.    Otherwise    use
        [22m[32mActionOnRespectedPartition[0m.
  
  [1m[33m
      [22m[32mIsomorphismRcwaGroup([22m[34mG[0m)[0m
    [0m
        The method for finite groups uses [22m[32mRcwaMapping[0m, Part(d).
  
        The  method  for  free products of finite groups uses the Table-Tennis
        Lemma  (which is also known as [22m[36mPing-Pong Lemma[0m, cp. e.g. SectionII.B.
        in[H00]).  It uses regular permutation representations of the factors
        G_r  (r  = 0, dots ,m-1) of the free product on residue classes modulo
        n_r  :=  |G_r|.  The  basic  idea  is  that since point stabilizers in
        regular  permutation groups are trivial, all non-identity elements map
        any  of  the  permuted  residue classes into their complements. To get
        into  a  situation  where  the  Table-Tennis  Lemma is applicable, the
        method  computes conjugates of the images of the mentioned permutation
        representations  under  bijective  rcwa mappings sigma_r which satisfy
        0(n_r)^sigma_r = Z \ r(m).
  
        The  method  for  free  groups  uses an adaptation of the construction
        given  on  page27 in[H00] from PSL(2,C) to RCWA(Z). As an equivalent
        for  the closed discs used there, the method takes the residue classes
        modulo two times the rank of the free group.
  
  [1m[33m
      [22m[32mIsSurjective([22m[34mf[0m)[0m
    [0m
        See [22m[32mImage[0m.
  
  [1m[33m
      [22m[32mIsTame([22m[34mG[0m)[0m
    [0m
        Checks whether the modulus of the group is non-zero.
  
  [1m[33m
      [22m[32mIsTame([22m[34mf[0m)[0m
    [0m
        Application  of  the criteria given in Corollary2.5.10 and2.5.12 and
        TheoremA.8  andA.11  in[K05].  The  criterion  "surjective, but not
        injective  means wild" (TheoremA.8 in[K05]) is the subject of[K06].
        For  applying  the  criterion  of  the  existence  of weakly-connected
        components  of  the  transition graph which are not strongly-connected
        (TheoremA.11 in[K05]), the package [1mGRAPE[0m is needed.
  
        In  addition,  some  probabilistic  methods  are  used.  If the result
        depends on one of these, a warning is displayed.
  
  [1m[33m
      [22m[32mIsTransitive([22m[34mG[0m,Integers)[0m
    [0m
        Look for finite orbits, using [22m[32mShortOrbits[0m on a couple of intervals. If
        a  finite  orbit  is found, return [22m[32mfalse[0m. Test if [22m[34mG[0m is finite. If yes,
        return [22m[32mfalse[0m.
  
        Search  for  an  element  [22m[32mg[0m  and  a  residue  class r(m) such that the
        restriction of [22m[32mg[0m to r(m) is given by n -> n + m. Then the cyclic group
        generated  by  [22m[32mg[0m  acts transitively on r(m). The element [22m[32mg[0m is searched
        among  the generators of [22m[34mG[0m, its powers, its commutators, powers of its
        commutators  and  products of few different generators. The search for
        such  an  element  may  run  into  an  infinite  loop,  as there is no
        guarantee that the group has a suitable element.
  
        If suitable [22m[32mg[0m and r(m) are found, proceed as follows:
  
        Set  S  :=  r(m).  Set  S  := S cup S^g for all generators g of [22m[34mG[0m, and
        repeat  this  until  S remains constant. This may run into an infinite
        loop.
  
        If it terminates: If S = Z, return [22m[32mtrue[0m, otherwise return [22m[32mfalse[0m.
  
  [1m[33m
      [22m[32mKernelOfActionOnRespectedPartition([22m[34mG[0m)[0m
    [0m
        First  determine  the  abelian  invariants  of the kernel[22m[32mK[0m. For this,
        compute  sufficiently  many  quotients of orders of permutation groups
        induced by[22m[34mG[0m on refinements of the stored respected partition[22m[32mP[0m by the
        order  of  the  permutation group induced by[22m[34mG[0m on[22m[32mP[0m itself. Then use a
        random   walk   through  the  group  [22m[34mG[0m.  Compute  powers  of  elements
        encountered along the way which fix[22m[32mP[0m. Translate these kernel elements
        into  elements  of  a polycyclically presented group isomorphic to the
        [22m[32m|P|[0m-fold  direct  product  of the infinite dihedral group ([22m[32mK[0m certainly
        embeds  in  this  group). Use [1mPolycyclic[0m[EN03] to collect independent
        "nice"  generators  of[22m[32mK[0m. Proceed until the permutation groups induced
        by[22m[32mK[0m  on  the  refined  respected  partitions  all equal the initially
        stored quotients.
  
  [1m[33m
      [22m[32mLargestSourcesOfAffineMappings([22m[34mf[0m)[0m
    [0m
        Forms  unions  of  residue  classes modulo the modulus of the mapping,
        whose corresponding coefficient triples are equal.
  
  [1m[33m
      [22m[32mLaTeXObj([22m[34mf[0m)[0m
    [0m
        Collects  residue  classes those corresponding coefficient triples are
        equal.
  
  [1m[33m
      [22m[32mLikelyContractionCentre([22m[34mf[0m,[22m[34mmaxn[0m,[22m[34mbound[0m)[0m
    [0m
        Computes  trajectories  with  starting  values  from a given interval,
        until  a  cycle  is  reached.  Aborts  if  the  trajectory exceeds the
        prescribed bound. Form the union of the detected cycles.
  
  [1m[33m
      [22m[32mLocalizedRcwaMapping([22m[34mf[0m,[22m[34mp[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mmKnot([22m[34mm[0m)[0m
    [0m
        "Straightforward", following the definition given in [K99].
  
  [1m[33m
      [22m[32mModulus([22m[34mG[0m)[0m
    [0m
        Searches  for  a  wild element in the group. If unsuccessful, tries to
        construct a respected partition (see [22m[32mRespectedPartition[0m).
  
  [1m[33m
      [22m[32mModulus([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mMovedPoints([22m[34mG[0m)[0m
    [0m
        Needs  only  forming  unions  of residue classes and determining fixed
        points of affine mappings.
  
  [1m[33m
      [22m[32mMultiplier([22m[34mf[0m)[0m
    [0m
        Lcm of coefficients, as indicated.
  
  [1m[33m
      [22m[32mMultpk([22m[34mf[0m,[22m[34mp[0m,[22m[34mk[0m)[0m
    [0m
        Forms  the  union  of  the  residue  classes modulo the modulus of the
        mapping,  which  are determined by the given divisibility criteria for
        the coefficients of the corresponding affine mapping.
  
  [1m[33m
      [22m[32mNrConjugacyClassesOfRCWAZOfOrder([22m[34mord[0m)[0m
    [0m
        The class numbers are taken from Corollary2.7.1 in[K05].
  
  [1m[33m
      [22m[32mOrbitsModulo([22m[34mf[0m,[22m[34mm[0m)[0m
    [0m
        Uses  [1mGRAPE[0m  to  compute  the  connected  components of the transition
        graph.
  
  [1m[33m
      [22m[32mOrbitsModulo([22m[34mG[0m,[22m[34mm[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mOrder([22m[34mf[0m)[0m
    [0m
        Test  for  [22m[32mIsTame[0m.  If  the mapping is not tame, then return [22m[32minfinity[0m.
        Otherwise use Corollary2.5.10 in[K05].
  
  [1m[33m
      [22m[32mPreImage([22m[34mf[0m,[22m[34mS[0m)[0m
    [0m
        See [22m[32mImage[0m.
  
  [1m[33m
      [22m[32mPreImagesRepresentative([22m[34mphi[0m,[22m[34mg[0m)[0m,
      [22m[32mPreImagesRepresentatives([22m[34mphi[0m,[22m[34mg[0m)[0m
    [0m
        As  indicated  in  the  documentation of these methods. The underlying
        idea  to  successively  compute  two  balls  around1 and[22m[34mg[0m until they
        intersect non-trivially is standard in computational group theory. For
        rcwa  groups it would mean wasting both memory and runtime to actually
        compute  group  elements.  Thus  only  images  of tuples of points are
        computed and stored.
  
  [1m[33m
      [22m[32mPrimeSet([22m[34mf[0m)[0m,
      [22m[32mPrimeSet([22m[34mG[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mPrimeSwitch([22m[34mp[0m)[0m
    [0m
        Multiplication of rcwa mappings as indicated.
  
  [1m[33m
      [22m[32mPrint([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32m[22m[34mf[0m*[22m[34mg[0m[0m
    [0m
        Essentially  composition of affine mappings. See Lemma1.3.1, Part(a)
        in[K05].
  
  [1m[33m
      [22m[32mRandom(RCWA(Integers))[0m
    [0m
        Computes   a   product   of  "randomly"  chosen  class  shifts,  class
        reflections  and  class  transpositions. This seems to be suitable for
        generating reasonably good examples.
  
  [1m[33m
      [22m[32mRankOfKernelOfActionOnRespectedPartition([22m[34mG[0m)[0m
    [0m
        This  performs  basically  the  first part of the computations done by
        [22m[32mKernelOfActionOnRespectedPartition[0m.
  
  [1m[33m
      [22m[32mRCWA([22m[34mR[0m)[0m
    [0m
        Attributes   are   set   according  to  Theorem2.1.1,  Theorem2.1.2,
        Corollary2.1.6 and Theorem2.12.8 in[K05].
  
  [1m[33m
      [22m[32mRcwaGroupByPermGroup([22m[34mG[0m)[0m
    [0m
        Uses [22m[32mRcwaMapping[0m, Part(d).
  
  [1m[33m
      [22m[32mRcwaMapping[0m
    [0m
        (a)-(c):  "trivial", (d): [22m[32mn^perm - n[0m for determining the coefficients,
        (e):  "affine  mappings  by  values at two given points", (f) and (g):
        "trivial", (h) and (i): correspond to Lemma2.1.4 in[K05].
  
  [1m[33m
      [22m[32mRepresentativeAction([22m[34mG[0m,[22m[34msrc[0m,[22m[34mdest[0m,[22m[34mact[0m)[0m,
      [22m[32mRepresentativeActionPreImage[0m
    [0m
        As  indicated  in  the  documentation of these methods. The underlying
        idea  to successively compute two balls around [22m[34msrc[0m and [22m[34mdest[0m until they
        intersect  non-trivially  is  standard  in computational group theory.
        Words  standing  for  products  of  generators of [22m[34mG[0m are stored for any
        image of [22m[34msrc[0m or [22m[34mdest[0m.
  
  [1m[33m
      [22m[32mRepresentativeAction([22m[34mG[0m,[22m[34mP1[0m,[22m[34mP2[0m)[0m
    [0m
        Arbitrary  mapping:  see Lemma2.1.4 in[K05]. Tame mapping: see proof
        of  Theorem2.8.9  in[K05].  The  former is almost trivial, while the
        latter is a bit complicate and takes usually also much more time.
  
  [1m[33m
      [22m[32mRepresentativeAction(RCWA(Integers),[22m[34mf[0m,[22m[34mg[0m)[0m
    [0m
        The  algorithm used by [22m[32mIsConjugate[0m constructs actually also an element
        [22m[32mx[0m such that [22m[32m[22m[34mf[0m^x = [22m[34mg[0m[0m.
  
  [1m[33m
      [22m[32mRespectedPartition([22m[34mf[0m)[0m,
      [22m[32mRespectedPartition([22m[34mG[0m)[0m
    [0m
        Uses the algorithm described in the proof of Theorem2.5.8 in[K05].
  
  [1m[33m
      [22m[32mRestriction([22m[34mg[0m,[22m[34mf[0m)[0m
    [0m
        Computes the action of [22m[32mRightInverse([22m[34mf[0m) * g * f[0m on the image of[22m[34mf[0m.
  
  [1m[33m
      [22m[32mRestriction([22m[34mG[0m,[22m[34mf[0m)[0m
    [0m
        Gets   a  set  of  generators  by  applying  [22m[32mRestriction([22m[34mg[0m,[22m[34mf[0m)[0m  to  the
        generators [22m[34mg[0m of[22m[34mG[0m.
  
  [1m[33m
      [22m[32mRightInverse([22m[34mf[0m)[0m
    [0m
        "Straightforward"  if  one  knows  how  to  compute  images of residue
        classes  under  affine mappings, and how to compute inverses of affine
        mappings.
  
  [1m[33m
      [22m[32mRoot([22m[34mf[0m,[22m[34mk[0m)[0m
    [0m
        If [22m[34mf[0m is bijective, class-wise order-preserving and has finite order:
  
        Find  a  conjugate  of  [22m[34mf[0m  which is a product of class transpositions.
        Slice   cycles   prod_i=2^l  tau_r_1(m_1),r_i(m_i)  of[22m[34mf[0m  a  respected
        partition     mathcalP    into    cycles    prod_i=1^l    prod_j=0^k-1
        tau_r_1(km_1),r_i+jm_i(km_i)  of  the  [22m[34mk[0m-fold  length  on  the refined
        partition  which one gets from mathcalP by decomposing any r_i(m_i) in
        mathcalP  into  residue  classes  (modkm_i).  Finally  conjugate  the
        resulting permutation back.
  
        Other cases seem to be more difficult and are currently not covered.
  
  [1m[33m
      [22m[32mSemilocalizedRcwaMapping([22m[34mf[0m,[22m[34mpi[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mShortCycles([22m[34mf[0m,[22m[34mmaxlng[0m)[0m
    [0m
        Looks for fixed points of affine partial mappings of powers of[22m[34mf[0m.
  
  [1m[33m
      [22m[32mShortOrbits([22m[34mG[0m,[22m[34mS[0m,[22m[34mmaxlng[0m)[0m
    [0m
        "Straightforward".
  
  [1m[33m
      [22m[32mSetOnWhichMappingIsClassWiseOrderPreserving([22m[34mf[0m)[0m, etc.
    [0m
        Forms  the  union  of  the  residue  classes modulo the modulus of the
        mapping,  in whose corresponding coefficient triple the first entry is
        positive, zero resp. negative.
  
  [1m[33m
      [22m[32mSign([22m[34mg[0m)[0m
    [0m
        Evaluation  of  the  given  expression.  For  the mathematical meaning
        (epimorphism!), see Theorem2.12.8 in[K05].
  
  [1m[33m
      [22m[32mSize([22m[34mG[0m)[0m
    [0m
        Test  whether one of the generators of the group[22m[34mG[0m has infinite order.
        If  so,  return  [22m[32minfinity[0m.  Test  whether the group [22m[34mG[0m is tame. If not,
        return               [22m[32minfinity[0m.               Test              whether
        [22m[32mRankOfKernelOfActionOnRespectedPartition([22m[34mG[0m)[0m  is nonzero. If so, return
        [22m[32minfinity[0m.  Otherwise  if  [22m[34mG[0m is class-wise order-preserving, return the
        size  of  the  permutation  group  induced  on  the  stored  respected
        partition. If [22m[34mG[0m is not class-wise order-preserving, return the size of
        the  permutation  group  induced  on  the  refinement  of  the  stored
        respected  partition which is obtained by splitting each residue class
        into three residue classes with equal moduli.
  
  [1m[33m
      [22m[32mStructureDescription([22m[34mG[0m)[0m
    [0m
        (Not described here.)
  
  [1m[33m
      [22m[32m[22m[34mf[0m+[22m[34mg[0m[0m
    [0m
        Pointwise addition of affine mappings.
  
  [1m[33m
      [22m[32mTrajectory([22m[34mf[0m,[22m[34mn[0m,...)[0m
    [0m
        Iterated  application  of  an  rcwa  mapping. In the methods computing
        "accumulated   coefficients"   additionally   composition   of  affine
        mappings.
  
  [1m[33m
      [22m[32mTransitionGraph([22m[34mf[0m,[22m[34mm[0m)[0m
    [0m
        "Straightforward" -- just check a sufficiently long interval.
  
  [1m[33m
      [22m[32mTransitionMatrix([22m[34mf[0m,[22m[34mm[0m)[0m
    [0m
        Evaluation of the given expression.
  
  [1m[33m
      [22m[32mViewObj([22m[34mf[0m)[0m
    [0m
        "Trivial".
  
  [1m[33m
      [22m[32mWreathProduct([22m[34mG[0m,[22m[34mP[0m)[0m
    [0m
        Uses  [22m[32mDirectProduct[0m  to embed the [22m[32mDegreeAction([22m[34mP[0m)[0mth direct power of[22m[34mG[0m,
        and [22m[32mRcwaMapping[0m, Part(d) to embed the finite permutation group[22m[34mP[0m.
  
  [1m[33m
      [22m[32mWreathProduct([22m[34mG[0m,[22m[34mZ[0m)[0m
    [0m
        Restricts  [22m[34mG[0m to the residue class3(4), and encodes the generator of[22m[34mZ[0m
        as  tau_0(2),1(2)  * tau_0(2),1(4). It is used that the images of3(4)
        under powers of this mapping are pairwise disjoint residue classes.
  
