6. The Algorithms Implemented in RCWA
  
  This  chapter lists brief descriptions of many of the 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.
  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 many of the algorithms and methods can be
  found in [Koh07b].
  
  
      ActionOnRespectedPartition(G)
    
        "Straightforward"  after  having  computed  a  respected  partition by
        RespectedPartition.  One  only  needs to know how to compute images of
        residue classes under affine mappings.
  
  
      Ball(G,g,r)
    
        "Straightforward".
  
  
      Ball(G,p,r,act)
    
        "Straightforward".
  
  
      ClassPairs
    
        Run  over  all  4-tuples,  and  filter  by divisibility criteria, size
        comparisons, ordering of the entries etc.
  
  
      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 [Koh06a].
  
  
      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].
  
  
      DirectProduct(G1,G2, ... )
    
        Restricts  the  groups  G1,  G2,  ... to disjoint residue classes. See
        Restriction and Corollary 2.3.3 in [Koh05].
  
  
      Display(f)
    
        "Trivial".
  
  
      Divisor(f)
    
        Lcm of coefficients, as indicated.
  
  
      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)
    
        If   the   package   FR [Bar07]  is  loaded,  then  use  its  function
        FindGroupRelations  to  find  relations. Otherwise proceed as follows:
        First  compute  the  ball of radius r around 1 in the free group whose
        rank  is the number of stored generators of G. Then compute the images
        of  the  elements  of  that ball under the natural projection onto the
        group G. Take pairs of elements of the ball whose images coincide, and
        add  their  quotients  to the set of known relations. For images which
        have  finite  order,  add  the corresponding power relations. Finally,
        regardless  of  whether  FR  is  present or not, simplify the finitely
        presented  group  with  the  determined  relations  by  the  operation
        IsomorphismSimplifiedFpGroup  from  the  GAP  Library,  and return the
        natural epimorphism from it to G.
  
  
      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.
  
  
      FactorizationIntoCSCRCT(g)
    
        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.
  
  
      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".
  
  
      GluckTaylorInvariant(a(
    
        Evaluation of the given expression.
  
  
      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 [EN06], 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 Z 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 runtime 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 Z 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  nontrivially. 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 Z, 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 Z,  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.
  
  
      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)
    
        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)
    
        Tests whether the first entry of all coefficient triples is positive.
  
  
      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".
  
  
      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  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 page 27 in [dlH00] 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.
  
  
      IsPerfect(G)
    
        If  the  group  G  is  trivial,  then  return true. Otherwise if it is
        abelian, then return false.
  
        If  the  underlying  ring  is Z,  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 [Koh06b]. 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 cup 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 = Z, return true, otherwise return false.
  
  
      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 [EN06] 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.
  
  
      LaTeXObj(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.
  
  
      LocalizedRcwaMapping(f,p)
    
        "Trivial".
  
  
      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
        nontrivially with their images under f.
  
  
      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.
  
  
      NrConjugacyClassesOfRCWAZOfOrder(ord)
    
        The class numbers are taken from Corollary 2.7.1 in [Koh05].
  
  
      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 Omega := r(m). Unite the set Omega with its images
        under  all  the  generators of G and their inverses. Repeat that until
        Omega does not change any more. Return Omega.
  
        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].
  
  
      PreImage(f,S)
    
        See Image.
  
  
      PreImagesRepresentative(phi,g),
      PreImagesRepresentatives(phi,g)
    
        As  indicated  in  the  documentation of these methods. The underlying
        idea  to  successively  compute  two  balls  around 1 and g until they
        intersect  nontrivially 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.
  
  
      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].
  
  
      Projections(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.
  
  
      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)
    
        This  performs  basically  the  first part of the computations done by
        KernelOfActionOnRespectedPartition.
  
  
      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].
  
  
      RcwaGroupByPermGroup(G)
    
        Uses RcwaMapping, Part (d).
  
  
      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].
  
  
      RepresentativeAction(G,src,dest,act),
      RepresentativeActionPreImage
    
        As  indicated  in  the  documentation of these methods. The underlying
        idea  to successively compute two balls around src and dest until they
        intersect  nontrivially  is  standard  in  computational group theory.
        Words  standing  for  products  of  generators of G are stored for any
        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)
    
        Uses the algorithm described in the proof of Theorem 2.5.8 in [Koh05].
  
  
      RespectsPartition(G,P)
    
        "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   prod_i=2^l  tau_r_1(m_1),r_i(m_i)  of f  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  k-fold  length  on  the refined
        partition  which one gets from mathcalP by decomposing any r_i(m_i) in
        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".
  
  
      SemilocalizedRcwaMapping(f,pi)
    
        "Trivial".
  
  
      ShortCycles(f,maxlng)
    
        Looks for fixed points of affine partial mappings of powers of f.
  
  
      ShortOrbits(G,S,maxlng)
    
        "Straightforward".
  
  
      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.
  
  
      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.
  
  
      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.
  
  
      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 DegreeAction(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  tau_0(2),1(2)  * tau_0(2),1(4). It is used that the images of 3(4)
        under powers of this mapping are pairwise disjoint residue classes.