chap8.txt

  
  8 The Algorithms Implemented in RCWA
  
  This  chapter  lists  brief  descriptions  of  the  algorithms  and  methods
  implemented  in  this package. These descriptions are kept very informal and
  terse,  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 performing I/O operations, storing or
  recalling  one  or  several  values  or  doing  very basic computations, and
  straightforward  means  that  no  sophisticated algorithm is used. Note that
  trivial  and  straightforward  are  to  be  read  as  mathematically trivial
  respectively  straightforward,  and  that  the  code of a function or method
  attributed  in this way can still be reasonably long and complicated. Longer
  and  better  descriptions of some of the algorithms and methods can be found
  in [Koh08].
  
   ActionOnRespectedPartition(G) 
        Straightforward   after  having  computed  a  respected  partition  by
        RespectedPartition.
  
   AllElementsOfCTZWithGivenModulus(m) 
        This  function  first  determines  a  list of all unordered partitions
        mathcalP  of  ℤ  into  m  residue classes. Then for any such partition
        mathcalP  it  runs  a loop over the elements of the symmetric group of
        degree m. For any σ ∈ S_m and any partition mathcalP it constructs the
        element  of  CT(Z)  with  modulus  dividing  m  which maps the ordered
        partition {0(m), 1(m), dots, m-1(m)} to the ordered partition obtained
        from  mathcalP  by  permuting  the  residue classes with σ. Finally it
        discards  the  elements  whose  modulus  is a proper divisor of m, and
        returns the rest.
  
   Ball(G,g,r) 
        Straightforward.
  
   Ball(G,p,r,act) 
        Straightforward.
  
   ClassPairs(m) 
        Runs a loop over all 4-tuples of nonnegative integers less than m, and
        filters by congruence criteria and ordering of the entries.
  
   ClassReflection(r,m) 
        Trivial.
  
   ClassRotation(r,m,u) 
        Trivial.
  
   ClassShift(r,m) 
        Trivial.
  
   ClassTransposition(r1,m1,r2,m2) 
        Trivial.
  
   ClassWiseOrderPreservingOn(f), etc. 
        Forms  the  union  of  the  residue classes modulo the modulus of f in
        whose  corresponding  coefficient  triple the first entry is positive,
        zero or negative, respectively.
  
   Coefficients(f) 
        Trivial.
  
   CommonRightInverse(l,r) 
        See RightInverse.
  
   CT(R) 
        Attributes and properties are set according to [Koh10].
  
   CycleRepresentativesAndLengths(g,S) 
        Straightforward.
  
   CyclesOnFiniteOrbit(G,g,n) 
        Straightforward.
  
   DecreasingOn(f) 
        Forms  the  union  of  the residue classes which are determined by the
        coefficients as indicated.
  
   DerivedSubgroup(G) 
        No genuine method -- GAP Library methods already work for tame groups.
  
   Determinant(g) 
        Evaluation  of  the  given  expression.  For  the mathematical meaning
        (epimorphism!), see Theorem 2.11.9 in [Koh05].
  
   DifferencesList(l) 
        Trivial.
  
   DirectProduct(G1,G2, ... ) 
        Restricts  the  groups  G1,  G2,  ... to disjoint residue classes. See
        Restriction and Corollary 2.3.3 in [Koh05].
  
   Display(f) 
        Trivial.
  
   DistanceToNextSmallerPointInOrbit(G,n) 
        Straightforward  --  computes  balls of radius r about n for r = 1, 2,
        dots until a point smaller than n is found.
  
   Divisor(f) 
        Lcm of coefficients, as indicated.
  
   DrawGrid(U,range_y,range_x,filename) 
        Straightforward.
  
   DrawOrbitPicture 
        Compute spheres of radius 1, dots, r around the given point(s). Choose
        the  origin  either  in  the  lower left corner of the picture (if all
        points  lie in the first quadrant) or in the middle of the picture (if
        they  don't).  Mark  points of the ball with black pixels in case of a
        monochrome  picture. Choose colors from the given palette depending on
        the distance from the starting points in case of a colored picture.
  
   EpimorphismFromFpGroup(G,r) 
        Computes  orders of elements in the ball of radius r about 1 in G, and
        uses the corresponding relations if they affect the abelian invariants
        of G, G', G'', etc..
  
   Exponent(G) 
        Check  whether G is finite. If it is, then use the GAP Library method,
        applied to Image(IsomorphismPermGroup(G)). Check whether G is tame. If
        yes,  return  infinity.  If  not,  run  a loop over G until finding an
        element of infinite order. Once one is found, return infinity.
  
        The  final  loop  to find a non-torsion element can be left away under
        the  assumption that any finitely generated wild rcwa group has a wild
        element.  It  looks  likely  that this holds, but currently the author
        does not know a proof.
  
   ExtRepOfObj(f) 
        Trivial.
  
   FactorizationIntoCSCRCT(g),   Factorization(g) 
        The  method  used  here  is rather sophisticated, and 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 in a similar way as a permutation of a finite
        set can be factored into transpositions.
  
   FactorizationOnConnectedComponents(f,m) 
        Calls  GRAPE  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.
  
   FixedPointsOfAffinePartialMappings(f) 
        Straightforward.
  
   FixedResidueClasses(g,maxmod),   FixedResidueClasses(G,maxmod) 
        Runs a loop over all moduli m ≤ maxmod and all residues r modulo these
        moduli,  and  selects  those  residue classes r(m) which are mapped to
        itself by g, respectively, by all generators of G.
  
   FloatQuotientsList(l) 
        Trivial.
  
   GluckTaylorInvariant(a) 
        Evaluation of the given expression.
  
   GroupByResidueClasses(classes) 
        Finds  all  pairs  of  residue  classes  in the list classes which are
        disjoint, forms the corresponding class transpositions and returns the
        group generated by them.
  
   GuessedDivergence(f) 
        Numerical  computation  of  the  limit  of some series, which seems to
        converge often. Caution!!!
  
   Image(f),   Image(f,S) 
        Straightforward  if  one  can  compute images of residue classes under
        affine  mappings  and  unite  and  intersect  residue classes (Chinese
        Remainder Theorem). See Lemma 1.2.1 in [Koh05].
  
   ImageDensity(f) 
        Evaluation of the given expression.
  
   g in G (membership test for rcwa groups) 
        Test whether the mapping g or its inverse is in the list of generators
        of G. If it is, return true. Test whether its prime set is a subset of
        the  prime set of G. If not, return false. Test whether the multiplier
        or  the  divisor  of g  has  a  prime factor which does not divide the
        multiplier  of G.  If  yes,  return  false.  Test  if  G is class-wise
        order-preserving,  and g is not. If so, return false. Test if the sign
        of  g is -1 and all generators of G have sign 1. If yes, return false.
        Test  if  G  is  class-wise order-preserving, all generators of G have
        determinant 0  and  g  has determinant ≠ 0. If yes, return false. Test
        whether  the  support  of g  is  a subset of the support of G. If not,
        return  false.  Test whether G fixes the nonnegative integers setwise,
        but g does not. If yes, return false.
  
        If  G  is  tame,  proceed  as  follows:  Test whether the modulus of g
        divides  the  modulus  of  G.  If not, return false. Test whether G is
        finite  and  g has infinite order. If so, return false. Test whether g
        is  tame.  If  not, return false. Compute a respected partition P of G
        and   the  finite  permutation  group  H  induced  by  G  on  it  (see
        RespectedPartition). Check whether g permutes P. If not, return false.
        Let h be the permutation induced by g on P. Check whether h lies in H.
        If  not,  return  false.  Compute  an  element g1 of G which acts on P
        like g.  For  this  purpose,  factor  h  into  generators  of H  using
        PreImagesRepresentative,  and  compute  the  corresponding  product of
        generators  of G.  Let  k  :=  g/g1. The mapping k is always integral.
        Compute    the    kernel K   of   the   action   of   G   on P   using
        KernelOfActionOnRespectedPartition. Check whether k lies in K. This is
        done  using  the  package  Polycyclic [EHN13], and uses an isomorphism
        from  a  supergroup  of   K which is isomorphic to the |P|-fold direct
        product  of the infinite dihedral group and which always contains k to
        a  polycyclically  presented  group.  If k  lies  in K,  return  true,
        otherwise return false.
  
        If  G is not tame, proceed as follows: Look for finite orbits of G. If
        some  are  found, test whether g acts on them, and whether the induced
        permutations lie in the permutation groups induced by G. If for one of
        the  examined  orbits  one  of the latter two questions has a negative
        answer,  then  return false. Look for a positive integer m such that g
        does not leave a partition of ℤ into unions of residue classes (mod m)
        invariant  which  is  fixed by G. If successful, return false. If not,
        try to factor g into generators of G using PreImagesRepresentative. If
        successful,  return true. If g is in G, this terminates after a finite
        number of steps. Both run time and memory requirements are exponential
        in  the  word  length. If g is not in G at this stage, the method runs
        into an infinite loop.
  
   f in M (membership test for rcwa monoids) 
        Test  whether  the  mapping f is in the list of generators of G. If it
        is,  return  true.  Test  whether the multiplier of f is zero, but all
        generators of M have nonzero multiplier. If yes, return false. Test if
        neither f  nor  any  generator  of M has multiplier zero. If so, check
        whether  the  prime  set  of f  is a subset of the prime set of M, and
        whether the set of prime factors of the multiplier of f is a subset of
        the  union  of  the  sets  of  prime factors of the multipliers of the
        generators  of M. If one of these is not the case, return false. Check
        whether  the  set  of prime factors of the divisor of f is a subset of
        the  union  of  the  sets  of  prime  factors  of  the divisors of the
        generators  of M. If not, return false. If the underlying ring is ℤ or
        a  semilocalization  thereof,  then  check whether f is not class-wise
        order-preserving, but M is. If so, return false.
  
        If f is not injective, but all generators of M are, then return false.
        If  f  is  not  surjective,  but  all generators of M are, then return
        false.  If  the support of f is not a subset of the support of M, then
        return  false.  If  f  is  not  sign-preserving, but M is, then return
        false. Check whether M is tame. If so, then return false provided that
        one  of  the following three conditions hold: 1. The modulus of f does
        not  divide  the modulus of M. 2. f is not tame. 3. M is finite, and f
        is  bijective and has infinite order. If membership has still not been
        decided,  use  ShortOrbits  to  look for finite orbits of M, and check
        whether  f fixes all of them setwise. If a finite orbit is found which
        f does not map to itself, then return false.
  
        Finally  compute  balls of increasing radius around 1 until f is found
        to  lie  in  one  of  them.  If  that happens, return true. If f is an
        element  of M,  this will eventually terminate, but if at this stage f
        is not an element of M, this will run into an infinite loop.
  
   point in orbit (membership test for orbits) 
        Uses  the  equality  test for orbits: The orbit equality test computes
        balls of increasing radius around the orbit representatives until they
        intersect non-trivially. Once they do so, it returns true. If it finds
        that  one  or  both  of  the  orbits  are finite, it makes use of that
        information,  and returns false if appropriate. In between, i.e. after
        having  computed balls to a certain extent depending on the properties
        of  the  group,  it  chooses  a suitable modulus m and computes orbits
        (modulo m). If the representatives of the orbits to be compared belong
        to different orbits (mod m), it returns false. If this is not the case
        although  the  orbits  are  different,  the equality test runs into an
        infinite loop.
  
   IncreasingOn(f) 
        Forms  the  union  of  the residue classes which are determined by the
        coefficients as indicated.
  
   Index(G,H) 
        In  general, i.e. if the underlying ring is not ℤ, proceed as follows:
        If  both  groups  G  and H  are  finite,  return the quotient of their
        orders.  If G is infinite, but H is finite, return infinity. Otherwise
        return  the  number  of  right  cosets  of H in G, computed by the GAP
        Library function RightCosets.
  
        If  the  underlying  ring  is ℤ,  do additionally the following before
        attempting  to  compute  the  list  of right cosets: If the group G is
        class-wise  order-preserving,  check whether one of its generators has
        nonzero   determinant,   and   whether   all   generators   of H  have
        determinant zero.  If  so,  then  return  infinity. Check whether H is
        tame,  but  G  is not. If so, then return infinity. If G is tame, then
        check  whether  the  rank  of the largest free abelian subgroup of the
        kernel  of the action of G on a respected partition is higher than the
        corresponding      rank     for H.     For     this     check,     use
        RankOfKernelOfActionOnRespectedPartition.   If   it  is,  then  return
        infinity.
  
   Induction(g,f) 
        Computes f * g * RightInverse(f).
  
   Induction(G,f) 
        Gets  a set of generators by applying Induction(g,f) to the generators
        g of G.
  
   InjectiveAsMappingFrom(f) 
        The  function  starts  with the entire source of f as preimage pre and
        the  empty  set  as  image im.  It  loops  over  the  residue  classes
        (mod Mod(f)).  For  any  such  residue class cl the following is done:
        Firstly,  the  image  of  cl  under f  is  added  to im. Secondly, the
        intersection  of  the  preimage of the intersection of the image of cl
        under f and im under f and cl is subtracted from pre.
  
   IntegralConjugate(f),   IntegralConjugate(G) 
        Uses   the   algorithm   described  in  the  proof  of  Theorem 2.5.14
        in [Koh05].
  
   IntegralizingConjugator(f),   IntegralizingConjugator(G) 
        Uses   the   algorithm   described  in  the  proof  of  Theorem 2.5.14
        in [Koh05].
  
   Inverse(f) 
        Essentially  inversion  of  affine mappings. See Lemma 1.3.1, Part (b)
        in [Koh05].
  
   IsBalanced(f) 
        Checks  whether  the  sets  of prime factors of the multiplier and the
        divisor of f are the same.
  
   IsBijective(f) 
        Trivial, respectively, see IsInjective and IsSurjective.
  
   IsClassReflection(g) 
        Computes the support of g, and compares g with the corresponding class
        reflection.
  
   IsClassRotation(g) 
        Computes  the support of g, extracts the possible rotation factor from
        the coefficients and compares g with the corresponding class rotation.
  
   IsClassShift(g) 
        Computes the support of g, and compares g with the corresponding class
        shift.
  
   IsClassTransposition(g),   IsGeneralizedClassTransposition(g) 
        Computes  the  support  of g,  writes  it  as  a disjoint union of two
        residue  classes  and  compares g  with  the class transposition which
        interchanges them.
  
   IsClassWiseOrderPreserving(f),   IsClassWiseTranslating(f) 
        Trivial.
  
   IsConjugate(RCWA(Integers),f,g) 
        Test  whether  f and g have the same order, and whether either both or
        none of them is tame. If not, return false.
  
        If  the mappings are wild, use ShortCycles 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 false.
  
        If  the  mappings  are  tame, use the method described in the proof of
        Theorem 2.5.14 in [Koh05] to construct integral conjugates of f and g.
        Then   essentially  use  the  algorithm  described  in  the  proof  of
        Theorem 2.6.7  in [Koh05]  to  compute standard representatives of the
        conjugacy  classes which the integral conjugates of f and g belong to.
        Finally  compare  these  standard  representatives, and return true if
        they are equal and false if not.
  
   IsInjective(f) 
        See Image.
  
   IsIntegral(f) 
        Trivial.
  
   IsNaturalCT(G),   IsNaturalRCWA(G) 
        Only checks a set flag.
  
   IsomorphismMatrixGroup(G) 
        Uses the algorithm described in the proof of Theorem 2.6.3 in [Koh05].
  
   IsomorphismPermGroup(G) 
        If  the  group  G  is  finite  and  class-wise  order-preserving,  use
        ActionOnRespectedPartition.   If  G  is  finite,  but  not  class-wise
        order-preserving,  compute the action on the respected partition which
        is    obtained    by    splitting    any   residue   class   r(m)   in
        RespectedPartition(G)  into  three  residue  classes  r(3m),  r+m(3m),
        r+2m(3m).  If  G  is  infinite,  there  is  no isomorphism to a finite
        permutation group, thus return fail.
  
   IsomorphismRcwaGroup(G) 
        The method for finite groups uses RcwaMapping, Part (d).
  
        The  method  for  free products of finite groups uses the Table-Tennis
        Lemma  (which is also known as Ping-Pong Lemma, cf. e.g. Section II.B.
        in [dlH00]).  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 rcwa permutations σ_r which satisfy 0(n_r)^σ_r =
        ℤ ∖ r(m).
  
        The  method  for  free  groups  uses an adaptation of the construction
        given on page 27 in [dlH00] from PSL(2,ℂ) to RCWA(ℤ). As an equivalent
        for  the closed discs used there, the method takes the residue classes
        modulo two times the rank of the free group.
  
   IsOne(f) 
        Trivial.
  
   IsPerfect(G) 
        If  the  group  G  is  trivial,  then  return true. Otherwise if it is
        abelian, then return false.
  
        If  the  underlying  ring  is ℤ,  then do the following: If one of the
        generators  of G  has  sign -1,  then return false. If G is class-wise
        order-preserving  and  one  of the generators has nonzero determinant,
        then return false.
  
        If  G  is wild, and perfectness has not been decided so far, then give
        up.  If  G  is finite, then check the image of IsomorphismPermGroup(G)
        for perfectness, and return true or false accordingly.
  
        If  the  group G  is  tame  and  if it acts transitively on its stored
        respected  partition,  then  return true or false depending on whether
        the  finite permutation group ActionOnRespectedPartition(G) is perfect
        or  not.  If G  does  not  act  transitively  on  its stored respected
        partition, then give up.
  
   IsPrimeSwitch(g) 
        Checks  whether  the  multiplier  of g is an odd prime, and compares g
        with the corresponding prime switch.
  
   IsSignPreserving(f) 
        If  f is not class-wise order-preserving, then return false. Otherwise
        let  c  ≥  1  be  greater than or equal to the maximum of the absolute
        values of the coefficients b_r(m) of the affine partial mappings of f,
        and  check whether the minimum of the image of {0, dots, c} under f is
        nonnegative  and  whether  the  maximum of the image of {-c, dots, -1}
        under f  is negative. If both is the case, then return true, otherwise
        return false.
  
   IsSolvable(G) 
        If  G  is abelian, then return true. If G is tame, then return true or
        false  depending  on whether ActionOnRespectedPartition(G) is solvable
        or not. If G is wild, then give up.
  
   IsSubset(G,H) (checking for a subgroup relation) 
        Check whether the set of stored generators of H is a subset of the set
        of stored generators of G. If so, return true. Check whether the prime
        set  of H  is  a  subset  of the prime set of G. If not, return false.
        Check  whether  the  support  of H is a subset of the support of G. If
        not,  return  false.  Check  whether  G is tame, but H is wild. If so,
        return false.
  
        If  G  and H are both tame, then proceed as follows: If the multiplier
        of H does not divide the multiplier of G, then return false. If H does
        not  respect  the  stored respected partition of G, then return false.
        Check   whether   the   finite  permutation  group  induced  by  H  on
        RespectedPartition(G)  is a subgroup of ActionOnRespectedPartition(G).
        If  yes, return true. Check whether the order of H is greater than the
        order of G. If so, return false.
  
        Finally  use  the membership test to check whether all generators of H
        lie in G, and return true or false accordingly.
  
   IsSurjective(f) 
        See Image.
  
   IsTame(G) 
        Checks whether the modulus of the group is nonzero.
  
   IsTame(f) 
        Application  of  the criteria given in Corollary 2.5.10 and 2.5.12 and
        Theorem A.8  and A.11  in [Koh05],  as  well  as of the criteria given
        in [Koh07a].  The  criterion  surjective, but not injective means wild
        (Theorem A.8 in [Koh05]) is the subject of [Koh07b]. The package GRAPE
        is needed for the application of the criterion which says that an rcwa
        permutation  is  wild  if  a  transition  graph has a weakly-connected
        component   which   is   not   strongly-connected   (cf.  Theorem A.11
        in [Koh05]).
  
   IsTransitive(G,Integers) 
        Look for finite orbits, using ShortOrbits on a couple of intervals. If
        a  finite  orbit  is found, return false. Test if G is finite. If yes,
        return false.
  
        Search  for  an  element  g  and  a  residue  class r(m) such that the
        restriction  of g to r(m) is given by n ↦ n + m. Then the cyclic group
        generated  by  g  acts transitively on r(m). The element g is searched
        among  the generators of G, 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 g and r(m) are found, proceed as follows:
  
        Put  S := r(m). Put S := S ∪ S^g for all generators g of G, and repeat
        this until S remains constant. This may run into an infinite loop.
  
        If it terminates: If S = ℤ, return true, otherwise return false.
  
   IsTransitiveOnNonnegativeIntegersInSupport(G) 
        Computes  balls about 1 with successively increasing radii, and checks
        whether  the  union  of the sets where the elements of these balls are
        decreasing  or  shifting  down  equals the support of G. If a positive
        answer  is  found,  transitivity on small points (nonnegative integers
        less than an explicit bound) is verified.
  
   IsZero(f) 
        Trivial.
  
   KernelOfActionOnRespectedPartition(G) 
        First  determine  the  abelian  invariants  of the kernel K. For this,
        compute  sufficiently  many  quotients of orders of permutation groups
        induced by G on refinements of the stored respected partition P by the
        order  of  the  permutation group induced by G on P itself. Then use a
        random   walk   through  the  group  G.  Compute  powers  of  elements
        encountered along the way which fix P. Translate these kernel elements
        into  elements  of  a polycyclically presented group isomorphic to the
        |P|-fold  direct  product  of the infinite dihedral group (K certainly
        embeds into this group). Use Polycyclic [EHN13] to collect independent
        nice  generators  of K.  Proceed  until the permutation groups induced
        by K  on  the  refined  respected  partitions  all equal the initially
        stored quotients.
  
   LargestSourcesOfAffineMappings(f) 
        Forms  unions  of  residue  classes modulo the modulus of the mapping,
        whose corresponding coefficient triples are equal.
  
   LaTeXStringRcwaMapping(f),   LaTeXAndXDVI(f) 
        Collects  residue  classes those corresponding coefficient triples are
        equal.
  
   LikelyContractionCentre(f,maxn,bound) 
        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.
  
   LoadDatabaseOf...(),   LoadRCWAExamples() 
        Trivial.  --  These  functions do nothing more than reading in certain
        files.
  
   LocalizedRcwaMapping(f,p) 
        Trivial.
  
   Log2HTML(logfilename) 
        Straightforward string operations.
  
   Loops(f) 
        Runs  over  the  residue  classes modulo the modulus of f, and selects
        those  of them which f does not map to themselves, but which intersect
        non-trivially with their images under f.
  
   MaximalShift(f) 
        Trivial.
  
   MergerExtension(G,points,point) 
        As described in MergerExtension (3.1-4).
  
   Mirrored(g),   Mirrored(G) 
        Conjugates with n ↦ -n - 1, as indicated in the definition.
  
   mKnot(m) 
        Straightforward, following the definition given in [Kel99].
  
   Modulus(G) 
        Searches  for  a  wild element in the group. If unsuccessful, tries to
        construct a respected partition (see RespectedPartition).
  
   Modulus(f) 
        Trivial.
  
   MovedPoints(G) 
        Needs  only  forming  unions  of residue classes and determining fixed
        points of affine mappings.
  
   Multiplier(f) 
        Lcm of coefficients, as indicated.
  
   Multpk(f,p,k) 
        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.
  
   NrClassPairs(m) 
        Relatively  straightforward.  --  Practical for values of m ranging up
        into the hundreds and corresponding counts of $10^9$ and more.
  
   NrConjugacyClassesOfCTZOfOrder(ord), 
        Evaluation               of               the               expression
        Length(Filtered(Combinations(DivisorsInt(ord)),  l  ->  l  <>  []  and
        Lcm(l) = ord)).
  
   NrConjugacyClassesOfRCWAZOfOrder(ord) 
        The class numbers are taken from Corollary 2.7.1 in [Koh05].
  
   ObjByExtRep(fam,l) 
        Trivial.
  
   One(f),   One(G), 
        Trivial.
  
   Orbit(G,pnt,gens,acts,act) 
        Check  if  the orbit has length less than a certain bound. If so, then
        return  it  as  a  list. Otherwise test whether the group G is tame or
        wild.
  
        If  G is tame, then test whether G is finite. If yes, then compute the
        orbit by the GAP Library method. Otherwise proceed as follows: Compute
        a  respected  partition mathcalP  of G. Use mathcalP to find a residue
        class r(m)  which is a subset of the orbit to be computed. In general,
        r(m)  will not be one of the residue classes in mathcalP, but a subset
        of  one  of them. Put Ω := r(m). Unite the set Ω with its images under
        all  the  generators of G and their inverses. Repeat that until Ω does
        not change any more. Return Ω.
  
        If  G  is  wild, then return an orbit object which stores the group G,
        the representative rep and the action act.
  
   OrbitsModulo(f,m) 
        Uses  GRAPE  to  compute  the  connected  components of the transition
        graph.
  
   OrbitsModulo(G,m) 
        Straightforward.
  
   Order(f) 
        Test  for  IsTame.  If  the mapping is not tame, then return infinity.
        Otherwise use Corollary 2.5.10 in [Koh05].
  
   PermutationOpNC(sigma,P,act) 
        Several  different  methods  for  different  types of arguments, which
        either   provide  straightforward  optimizations  via  computing  with
        coefficients directly, or just delegate to PermutationOp.
  
   PreImage(f,S) 
        See Image.
  
   PreImagesRepresentative(phi,g),   PreImagesRepresentatives(phi,g) 
        As  described  in  the  documentation of these methods. The underlying
        idea  to  successively  compute  two  balls  around 1 and g until they
        intersect non-trivially is standard in computational group theory. For
        rcwa groups it would mean wasting both memory and run time to actually
        compute  group  elements.  Thus  only  images  of tuples of points are
        computed and stored.
  
   PrimeSet(f),   PrimeSet(G) 
        Straightforward.
  
   PrimeSwitch(p) 
        Multiplication of rcwa mappings as indicated.
  
   Print(f) 
        Trivial.
  
   f*g 
        Essentially  composition of affine mappings. See Lemma 1.3.1, Part (a)
        in [Koh05].
  
   ProjectionsToCoordinates(f) 
        Straightforward coefficient operations.
  
   ProjectionsToInvariantUnionsOfResidueClasses(G,m) 
        Use  OrbitsModulo  to  determine  the  supports  of  the images of the
        epimorphisms  to  be determined, and use RestrictedPerm to compute the
        images of the generators of G under these epimorphisms.
  
   QuotientsList(l) 
        Trivial.
  
   Random(RCWA(Integers)) 
        Computes  a product of randomly chosen class shifts, class reflections
        and  class  transpositions.  This  seems to be suitable for generating
        reasonably good examples.
  
   RankOfKernelOfActionOnRespectedPartition(G) 
        Performs    the    first    part   of   the   computations   done   by
        KernelOfActionOnRespectedPartition.
  
   Rcwa(R) 
        Trivial.  --  Attributes  and  properties set can be derived easily or
        hold by definition.
  
   RCWA(R) 
        Attributes   and   properties  are  set  according  to  Theorem 2.1.1,
        Theorem 2.1.2, Corollary 2.1.6 and Theorem 2.12.8 in [Koh05].
  
   RCWABuildManual() 
        Consists of a call to a function from the GAPDoc package.
  
   RcwaGroupByPermGroup(G) 
        Uses RcwaMapping, Part (d).
  
   RCWAInfo(n) 
        Trivial.
  
   RcwaMapping 
        (a)-(c):  trivial,  (d):  n^perm - n for determining the coefficients,
        (e):  affine  mappings  by  values  at  two given points, (f) and (g):
        trivial,  (h) and (i): correspond to Lemma 2.1.4 in [Koh05], (j): uses
        a simple parser for the permitted expressions.
  
   RCWATestAll(),   RCWATestInstall() 
        Just read in files running / containing the tests.
  
   RCWATestExamples() 
        Runs the example tester from the GAPDoc package.
  
   RepresentativeAction(G,src,dest,act),   RepresentativeActionPreImage 
        As  described  in  the  documentation of these methods. The underlying
        idea  to successively compute two balls around src and dest until they
        intersect  non-trivially  is  standard  in computational group theory.
        Words  standing  for  products of generators of G are stored for every
        image of src or dest.
  
   RepresentativeAction(RCWA(Integers),P1,P2) 
        Arbitrary mapping: see Lemma 2.1.4 in [Koh05]. Tame mapping: see proof
        of  Theorem 2.8.9  in [Koh05]. The former is almost trivial, while the
        latter is a bit complicated and takes usually also much more time.
  
   RepresentativeAction(RCWA(Integers),f,g) 
        The  algorithm used by IsConjugate constructs actually also an element
        x such that f^x = g.
  
   RespectedPartition(f),   RespectedPartition(G) 
        There  are  presently  two  sophisticated  algorithms  implemented for
        finding  respected  partitions.  One  of  them  has  evolved  from the
        algorithm  described  in  the  proof  of Theorem 2.5.8 in [Koh05]. The
        other  one  starts  with  the coarsest partition of the base ring such
        that  every  generator of G is affine on every part. This partition is
        then refined successively until a respected partition is obtained. The
        refinement  step  is  basically  as  follows:  Take  the images of the
        partition  under  all  generators  of  G. This way one obtains as many
        further partitions of the base ring as there are generators of G. Then
        the  new  partition  is  the  coarsest  common refinement of all these
        partitions.
  
   RespectsPartition(G,P) 
        Straightforward.
  
   RestrictedBall(G,g,r,modulusbound) 
        Straightforward.
  
   RestrictedPerm(g,S) 
        Straightforward.
  
   Restriction(g,f) 
        Computes the action of RightInverse(f) * g * f on the image of f.
  
   Restriction(G,f) 
        Gets   a  set  of  generators  by  applying  Restriction(g,f)  to  the
        generators g of G.
  
   RightInverse(f) 
        Straightforward  if one knows how to compute images of residue classes
        under affine mappings, and how to compute inverses of affine mappings.
  
   Root(f,k) 
        If f is bijective, class-wise order-preserving and has finite order:
  
        Find  a  conjugate  of  f  which is a product of class transpositions.
        Slice  cycles  ∏_i=2^l  τ_r_1(m_1),r_i(m_i) of f a respected partition
        mathcalP  into  cycles ∏_i=1^l ∏_j=0^k-1 τ_r_1(km_1),r_i+jm_i(km_i) of
        the  k-fold  length  on  the  refined  partition  which  one gets from
        mathcalP  by  decomposing any r_i(m_i) ∈ mathcalP into residue classes
        (mod km_i). Finally conjugate the resulting permutation back.
  
        Other cases seem to be more difficult and are currently not covered.
  
   RotationFactor(g) 
        Trivial.
  
   RunDemonstration(filename) 
        Trivial -- only I/O operations.
  
   SemilocalizedRcwaMapping(f,pi) 
        Trivial.
  
   ShiftsDownOn(f),   ShiftsUpOn(f) 
        Straightforward coefficient- and residue class operations.
  
   ShortCycles(g,maxlng) 
        Looks for fixed points of affine partial mappings of powers of g.
  
   ShortCycles(g,S,maxlng),   ShortCycles(g,S,maxlng,maxn) 
        Straightforward.
  
   ShortOrbits(G,S,maxlng),   ShortOrbits(G,S,maxlng,maxn) 
        Straightforward.
  
   ShortResidueClassCycles(g,modulusbound,maxlng) 
        Different methods -- see source code in pkg/rcwa/lib/rcwamap.gi.
  
   ShortResidueClassOrbits(g,modulusbound,maxlng) 
        Different methods -- see source code in pkg/rcwa/lib/rcwagrp.gi.
  
   Sign(g) 
        Evaluation  of  the  given  expression.  For  the mathematical meaning
        (epimorphism!), see Theorem 2.12.8 in [Koh05].
  
   Sinks(f) 
        Computes  the strongly connected components of the transition graph by
        the  function STRONGLY_CONNECTED_COMPONENTS_DIGRAPH, and selects those
        which  are  proper  subsets of their preimages and proper supersets of
        their images under f.
  
   Size(G) (order of an rcwa group) 
        Test  whether one of the generators of the group G has infinite order.
        If  so,  return  infinity.  Test  whether the group G is tame. If not,
        return               infinity.               Test              whether
        RankOfKernelOfActionOnRespectedPartition(G)  is nonzero. If so, return
        infinity.  Otherwise  if  G is class-wise order-preserving, return the
        size  of  the  permutation  group  induced  on  the  stored  respected
        partition. If G 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.
  
   Size(M) (order of an rcwa monoid) 
        Check  whether  M  is in fact an rcwa group. If so, use the method for
        rcwa  groups  instead.  Check  whether  one  of the generators of M is
        surjective,  but  not injective. If so, return infinity. Check whether
        for  all  generators f  of M, the image of the union of the loops of f
        under f  is  finite. If not, return infinity. Check whether one of the
        generators  of M  is  bijective  and has infinite order. If so, return
        infinity.  Check  whether  one  of the generators of M is wild. If so,
        return  infinity. Apply the above criteria to the elements of the ball
        of  radius 2  around 1,  and  return  infinity if appropriate. Finally
        attempt  to  compute the list of elements of M. If this is successful,
        return the length of the resulting list.
  
   SmallGeneratingSet(G) 
        Eliminates  generators  g  which  can be found to be redundant easily,
        i.e.  by checking whether the balls about 1 and g of some small radius
        r in the group generated by all generators of G except for g intersect
        nontrivially.
  
   Sources(f) 
        Computes  the strongly connected components of the transition graph by
        the  function STRONGLY_CONNECTED_COMPONENTS_DIGRAPH, and selects those
        which  are  proper  supersets of their preimages and proper subsets of
        their images under f.
  
   SparseRep(f),   StandardRep(f) 
        Straightforward coefficient operations.
  
   SplittedClassTransposition(ct,k) 
        Straightforward.
  
   StructureDescription(G) 
        This  method  uses  a  combination  of techniques to obtain some basic
        information   on   the  structure  of  an  rcwa  group.  The  returned
        description  reflects the way the group has been built (DirectProduct,
        WreathProduct, etc.).
  
   f+g 
        Pointwise addition of affine mappings.
  
   String(obj) 
        Trivial.
  
   Support(G) 
        Straightforward.
  
   Trajectory(f,n,...) 
        Iterated  application  of  an  rcwa  mapping. In the methods computing
        accumulated coefficients, additionally composition of affine mappings.
  
   TransitionGraph(f,m) 
        Straightforward -- just check a sufficiently long interval.
  
   TransitionMatrix(f,m) 
        Evaluation of the given expression.
  
   TransposedClasses(g) 
        Trivial.
  
   View(f) 
        Trivial.
  
   WreathProduct(G,P) 
        Uses  DirectProduct to embed the NrMovedPoints(P)th direct power of G,
        and RcwaMapping, Part (d) to embed the finite permutation group P.
  
   WreathProduct(G,Z) 
        Restricts  G to the residue class 3(4), and encodes the generator of Z
        as τ_0(2),1(2) ⋅ τ_0(2),1(4). It is used that the images of 3(4) under
        powers of this mapping are pairwise disjoint residue classes.
  
   Zero(f) 
        Trivial.