RCWA
  
  
                        Residue-Class-Wise Affine Groups
  
  
                                 Version 2.5.4
  
  
                               September 26, 2007
  
  
                                  Stefan Kohl
  
  
  
  Stefan Kohl
      Email:    mailto:kohl@mathematik.uni-stuttgart.de
      Homepage: http://www.cip.mathematik.uni-stuttgart.de/~kohlsn/
      Address:  Institut für Geometrie und Topologie
                Pfaffenwaldring 57
                Universität Stuttgart
                70550 Stuttgart
                Germany
  
  
  
  -------------------------------------------------------
  Abstract
  RCWA  is  a package for GAP 4. It provides implementations of algorithms and
  methods  for computing in certain infinite permutation groups. In principle,
  this  package can deal at least with the following types of groups and their
  subgroups:
  
  --    Finite  groups,  and certain divisible torsion groups which they embed
        into.
  
  --    Free groups of finite rank.
  
  --    Free  products  of finitely many finite groups, thus in particular the
        modular group PSL(2,Z).
  
  --    Direct products of the above groups.
  
  --    Wreath products of the above groups with finite groups and with (Z,+).
  
  With  substancial  help  of  this  package, the author has found a countable
  simple  group  which  has  an  uncountable  series of simple subgroups. This
  simple  group is generated by involutions which interchange disjoint residue
  classes of the integers. All the above groups embed into it.
  
  
  -------------------------------------------------------
  Copyright
  ©  2003  -  2007  by  Stefan Kohl. This package is distributed under the GNU
  General Public License.
  
  
  -------------------------------------------------------
  Acknowledgements
  I  am  very  grateful to Bettina Eick for communicating this package and for
  her  kind help in improving its documentation. Further I would like to thank
  the  two  anonymous  referees  for  their  constructive  criticism and their
  helpful suggestions.
  
  I  am  also  very  grateful  to  Laurent  Bartholdi  for  his hint on how to
  construct  wreath  products  of residue-class-wise affine groups with (Z,+).
  Last  but not least I would like to thank all the people who have invited me
  so  far  to  give  talks  on  the  subject  in  their  seminars and on their
  conferences.
  
  
  -------------------------------------------------------
  
  
  Content (RCWA)
  
  1. About the RCWA Package
    1.1 Motivation
    1.2 Purpose of this package
    1.3 Groups which this package can deal with
    1.4 Scope of this package
  2. Residue-Class-Wise Affine Mappings
    2.1 Basic definitions
    2.2 Entering residue-class-wise affine mappings
      2.2-1 ClassShift
      2.2-2 ClassReflection
      2.2-3 ClassTransposition
      2.2-4 ClassRotation
      2.2-5 RcwaMapping (the general constructor)
      2.2-6 LocalizedRcwaMapping
    2.3 Basic arithmetic for residue-class-wise affine mappings
    2.4 Attributes and properties of residue-class-wise affine mappings
      2.4-1 LargestSourcesOfAffineMappings
      2.4-2 FixedPointsOfAffinePartialMappings
      2.4-3 Multpk
      2.4-4 Determinant
      2.4-5 Sign
    2.5 Factoring residue-class-wise affine permutations
      2.5-1 FactorizationIntoCSCRCT
      2.5-2 PrimeSwitch
      2.5-3 mKnot
    2.6 Extracting roots of residue-class-wise affine mappings
      2.6-1 Root
    2.7 Special functions for non-bijective mappings
      2.7-1 RightInverse
      2.7-2 CommonRightInverse
      2.7-3 ImageDensity
    2.8 On trajectories and cycles of residue-class-wise affine mappings
      2.8-1 Trajectory (methods for rcwa mappings)
      2.8-2 Trajectory (methods for rcwa mappings -- "accumulated
      coefficients")
      2.8-3 IncreasingOn & DecreasingOn (for an rcwa mapping)
      2.8-4 TransitionGraph
      2.8-5 OrbitsModulo
      2.8-6 FactorizationOnConnectedComponents
      2.8-7 TransitionMatrix
      2.8-8 Sources & Sinks (of an rcwa mapping)
      2.8-9 Loops
      2.8-10 GluckTaylorInvariant
      2.8-11 LikelyContractionCentre
      2.8-12 GuessedDivergence
    2.9 The categories and families of rcwa mappings
      2.9-1 IsRcwaMapping
      2.9-2 RcwaMappingsFamily
  3. Residue-Class-Wise Affine Groups
    3.1 Constructing residue-class-wise affine groups
      3.1-1 RCWA
      3.1-2 CT
      3.1-3 IsomorphismRcwaGroup
      3.1-4 DirectProduct
      3.1-5 WreathProduct (for an rcwa group over Z, with a permutation group
      or (Z,+))
      3.1-6 Restriction (of an rcwa mapping or -group, by an injective rcwa
      mapping)
      3.1-7 Induction (of an rcwa mapping or -group, by an injective rcwa
      mapping)
    3.2 Basic routines for investigating residue-class-wise affine groups
      3.2-1 StructureDescription
      3.2-2 EpimorphismFromFpGroup
      3.2-3 PreImagesRepresentative
    3.3 The natural action of an rcwa group on the underlying ring
      3.3-1 Orbit (for an rcwa group and either a point or a set)
      3.3-2 DrawOrbitPicture
      3.3-3 ShortOrbits (for rcwa groups) & ShortCycles (for rcwa
      permutations)
      3.3-4 Ball (for group, element and radius or group, point, radius and
      action)
      3.3-5 RepresentativeAction
      3.3-6 Projections
      3.3-7 RepresentativeAction
    3.4 Special attributes of tame residue-class-wise affine groups
      3.4-1 RespectedPartition (of a tame rcwa group or -permutation)
      3.4-2 ActionOnRespectedPartition & KernelOfActionOnRespectedPartition
    3.5 Generating pseudo-random elements of RCWA(R) and CT(R)
    3.6 The categories of residue-class-wise affine groups
      3.6-1 IsRcwaGroup
  4. Residue-Class-Wise Affine Monoids
    4.1 Constructing residue-class-wise affine monoids
      4.1-1 Rcwa
    4.2 Computing with residue-class-wise affine monoids
      4.2-1 ShortOrbits
      4.2-2 Ball (for monoid, element and radius or monoid, point, radius and
      action)
  5. Examples
    5.1 Factoring Collatz' permutation of the integers
    5.2 An rcwa mapping which seems to be contracting, but very slow
    5.3 Checking a result by P. Andaloro
    5.4 Two examples by Matthews and Leigh
    5.5 Exploring the structure of a wild rcwa group
    5.6 A wild rcwa mapping which has only finite cycles
    5.7 An abelian rcwa group over a polynomial ring
    5.8 A tame group generated by commutators of wild permutations
    5.9 Checking for solvability
    5.10 Some examples over (semi)localizations of the integers
    5.11 Twisting 257-cycles into an rcwa mapping with modulus 32
    5.12 The behaviour of the moduli of powers
    5.13 Images and preimages under the Collatz mapping
    5.14 A group which acts 4-transitively on the positive integers
    5.15 A group which acts 3-transitively, but not 4-transitively on Z
    5.16 Grigorchuk groups
    5.17 Forward orbits of a monoid with 2 generators
    5.18 Representations of the free group of rank 2
    5.19 Representations of the modular group PSL(2,Z)
  6. The Algorithms Implemented in RCWA
  7. Installation and auxiliary functions
    7.1 Requirements
    7.2 Installation
    7.3 The Info class of the package
      7.3-1 InfoRCWA
    7.4 The testing routine
      7.4-1 RCWATest
    7.5 Building the manual
      7.5-1 RCWABuildManual
    7.6 Loading and saving bitmap pictures
      7.6-1 SaveAsBitmapPicture
    7.7 Running demonstrations
      7.7-1 RunDemonstration
    7.8 Some general utility functions
  
  
  -------------------------------------------------------