[1X[5XRCWA[0X[0X [1XResidue-Class-Wise Affine Groups[0X Version 2.5.4 September 26, 2007 Stefan Kohl Stefan Kohl Email: [7Xmailto:kohl@mathematik.uni-stuttgart.de[0X Homepage: [7Xhttp://www.cip.mathematik.uni-stuttgart.de/~kohlsn/[0X Address: Institut für Geometrie und Topologie Pfaffenwaldring 57 Universität Stuttgart 70550 Stuttgart Germany ------------------------------------------------------- [1XAbstract[0X [5XRCWA[0X is a package for [5XGAP[0X 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. ------------------------------------------------------- [1XCopyright[0X © 2003 - 2007 by Stefan Kohl. This package is distributed under the GNU General Public License. ------------------------------------------------------- [1XAcknowledgements[0X 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. ------------------------------------------------------- [1XContent (RCWA)[0X 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 -------------------------------------------------------