chap0.txt

  
  
                                      RCWA
  
  
                        Residue-Class-Wise Affine Groups
  
  
                                 Version 4.6.1
  
  
                               December 18, 2017
  
  
                                  Stefan Kohl
  
  
  
  Stefan Kohl
      Email:    mailto:[email protected]
      Homepage: https://stefan-kohl.github.io/
  
  -------------------------------------------------------
  Abstract
  RCWA  is  a package for GAP 4. It provides implementations of algorithms and
  methods  for  computing in certain infinite permutation groups acting on the
  set of integers. This package can be used to investigate the following types
  of groups and many more:
  
      Finite  groups,  and certain divisible torsion groups which they embed
        into.
  
      Free groups of finite rank.
  
      Free products of finitely many finite groups.
  
      Direct products of the above groups.
  
      Wreath products of the above groups with finite groups and with (ℤ,+).
  
      Subgroups of any such groups.
  
  With the help of this package, the author has found a countable simple group
  which  is generated by involutions interchanging disjoint residue classes of
  ℤ and which all the above groups embed into -- see [Koh10].
  
  
  -------------------------------------------------------
  Copyright
  © 2003 - 2017 by Stefan Kohl.
  
  RCWA  is  free  software: you can redistribute it and/or modify it under the
  terms  of  the  GNU General Public License as published by the Free Software
  Foundation,  either  version 2 of the License, or (at your option) any later
  version.
  
  RCWA  is  distributed  in  the  hope that it will be useful, but WITHOUT ANY
  WARRANTY;  without  even  the implied warranty of MERCHANTABILITY or FITNESS
  FOR  A  PARTICULAR  PURPOSE.  See  the  GNU  General Public License for more
  details.
  
  For  a  copy  of the GNU General Public License, see the file GPL in the etc
  directory       of       the       GAP       distribution       or       see
  http://www.gnu.org/licenses/gpl.html.
  
  
  -------------------------------------------------------
  Acknowledgements
  I  am  grateful  to  John  P.  McDermott  for  the  discovery that the group
  discussed  in  Section 7.1 is isomorphic to Thompson's Group V in July 2008,
  and to Laurent Bartholdi for his hint on how to construct wreath products of
  residue-class-wise  affine groups with (ℤ,+) in April 2006. Further, I thank
  Bettina Eick for communicating this package and for her valuable suggestions
  on  its  manual  in  the time before its first public release in April 2005.
  Last but not least I thank the two anonymous referees for their constructive
  criticism and their helpful suggestions.
  
  
  -------------------------------------------------------
  
  
  Contents (RCWA)
  
  1 About the RCWA 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 Saving memory -- the sparse representation of rcwa mappings
      2.9-1 SparseRepresentation
    2.10 The categories and families of rcwa mappings
      2.10-1 IsRcwaMapping
      2.10-2 RcwaMappingsFamily
  3 Residue-Class-Wise Affine Groups
    3.1 Constructing residue-class-wise affine groups
      3.1-1 IsomorphismRcwaGroup
      3.1-2 DirectProduct
      3.1-3 WreathProduct (for an rcwa group over Z, with a permutation group
      or (ℤ,+))
      3.1-4 MergerExtension
      3.1-5 GroupByResidueClasses
      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.1-8 RCWA
      3.1-9 CT
    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 GrowthFunctionOfOrbit
      3.3-3 DrawOrbitPicture
      3.3-4 ShortOrbits (for rcwa groups) & ShortCycles (for rcwa
      permutations)
      3.3-5 ShortResidueClassOrbits & ShortResidueClassCycles
      3.3-6 ComputeCycleLength
      3.3-7 CycleRepresentativesAndLengths
      3.3-8 FixedResidueClasses
      3.3-9 Ball (for group, element and radius or group, point, radius and
      action)
      3.3-10 RepresentativeAction
      3.3-11 ProjectionsToInvariantUnionsOfResidueClasses
      3.3-12 RepresentativeAction
      3.3-13 CollatzLikeMappingByOrbitTree
    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 Residue-Class-Wise Affine Mappings, Groups and Monoids over ℤ^2
    5.1 The definition of residue-class-wise affine mappings of ℤ^d
    5.2 Entering residue-class-wise affine mappings of ℤ^2
      5.2-1 RcwaMapping (the general constructor; methods for ℤ^2)
      5.2-2 ClassTransposition (for ℤ^2)
      5.2-3 ClassRotation (for ℤ^2)
      5.2-4 ClassShift (for ℤ^2)
    5.3 Methods for residue-class-wise affine mappings of ℤ^2
      5.3-1 ProjectionsToCoordinates
    5.4 Methods for residue-class-wise affine groups and -monoids over ℤ^2
      5.4-1 IsomorphismRcwaGroup (Embeddings of SL(2,ℤ) and GL(2,ℤ))
      5.4-2 DrawGrid
  6 Databases of Residue-Class-Wise Affine Groups and -Mappings
    6.1 The collection of examples
      6.1-1 LoadRCWAExamples
    6.2 Databases of rcwa groups
      6.2-1 LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions
      6.2-2 LoadDatabaseOfGroupsGeneratedBy3ClassTranspositions
      6.2-3 LoadDatabaseOfGroupsGeneratedBy4ClassTranspositions
    6.3 Databases of rcwa mappings
      6.3-1 LoadDatabaseOfProductsOf2ClassTranspositions
      6.3-2 LoadDatabaseOfNonbalancedProductsOfClassTranspositions
  7 Examples
    7.1 Thompson's group V
    7.2 Factoring Collatz' permutation of the integers
    7.3 The 3n+1 group
    7.4 A group with huge finite orbits
    7.5 A group which acts 4-transitively on the positive integers
    7.6 A group which acts 3-transitively, but not 4-transitively on ℤ
    7.7 An rcwa mapping which seems to be contracting, but very slow
    7.8 Checking a result by P. Andaloro
    7.9 Two examples by Matthews and Leigh
    7.10 Orders of commutators
    7.11 An infinite subgroup of CT(GF(2)[x]) with many torsion elements
    7.12 An abelian rcwa group over a polynomial ring
    7.13 Checking for solvability
    7.14 Some examples over (semi)localizations of the integers
    7.15 Twisting 257-cycles into an rcwa mapping with modulus 32
    7.16 The behaviour of the moduli of powers
    7.17 Images and preimages under the Collatz mapping
    7.18 An extension of the Collatz mapping T to a permutation of ℤ^2
    7.19 Finite quotients of Grigorchuk groups
    7.20 Forward orbits of a monoid with 2 generators
    7.21 The free group of rank 2 and the modular group PSL(2,ℤ)
  8 The Algorithms Implemented in RCWA
  9 Installation and Auxiliary Functions
    9.1 Requirements
    9.2 Installation
    9.3 Building the manual
      9.3-1 RCWABuildManual
    9.4 The testing routines
      9.4-1 RCWATestInstall
      9.4-2 RCWATestAll
      9.4-3 RCWATestExamples
    9.5 The Info class of the package
      9.5-1 InfoRCWA