Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

# RCWA

## Residue Class-Wise Affine Groups

( Version 1.3.5 )

January 9, 2006

Stefan Kohl
e-mail: kohl@mathematik.uni-stuttgart.de
WWW: http://www.cip.mathematik.uni-stuttgart.de/~kohlsn
Address:
Institut für Geometrie und Topologie
Universität Stuttgart
70550 Stuttgart
Germany

### Abstract

The RCWA package provides methods for computations with Residue Class-Wise Affine mappings (rcwa mappings for short) and the groups generated by bijective mappings of this type.

The rcwa mappings are a type of mappings of certain euclidean rings R into themselves. A standard choice is R = Z. Similar classes of mappings are known as Generalized Collatz Mappings, Periodically Linear Functions or Number Theoretic Functions with Periodic Rational Coefficients. In fact, the development of this package has partly been motivated by the 3n+1 - conjecture. A regularly updated comprehensive annotated bibliography for this conjecture which has been compiled by Jeffrey C. Lagarias can be found at http://arxiv.org/abs/math.NT/0309224.

The bijective rcwa mappings of R form a proper subgroup of Sym(R), called RCWA(R). In general, computing with arbitrary mappings from R into R is an algorithmically difficult task. The rcwa mappings provide a class of mappings which are accessible to computations. The investigation of rcwa mappings and groups generated by them is the central aim of this package.

An object of particular interest is the group RCWA(Z) of all residue class-wise affine bijections of the integers.

Residue class-wise affine groups are introduced in the author's thesis Restklassenweise affine Gruppen. This thesis is available at http://elib.uni-stuttgart.de/opus/volltexte/2005/2448/. A copy of it as well as an english translation is distributed with this package (see `thesis/thesis.pdf` resp. `thesis/thesis_e.pdf`).

### Copyright

(C) 2003 - 2005 by Stefan Kohl

This package is distributed under the same conditions as the GAP system.

### Contents

1. Preface
1.1 Motivation
1.2 Purpose of this package
1.3 Scope of this package
1.4 Acknowledgements
2. Residue Class-Wise Affine Mappings
2.1 Basic definitions
2.2 Entering rcwa mappings
2.2-1 RcwaMapping
2.2-2 ClassShift
2.2-3 ClassReflection
2.2-4 ClassTransposition
2.2-5 PrimeSwitch
2.2-6 LaTeXObj
2.3 Basic functionality for rcwa mappings
2.4 Factoring rcwa mappings
2.4-1 FactorizationIntoGenerators
2.5 Determinant and sign
2.5-1 Determinant
2.5-2 Sign
2.6 Attributes and properties derived from the coefficients
2.6-1 Multiplier
2.6-2 Divisor
2.6-3 PrimeSet
2.6-4 IsIntegral
2.6-5 IsClassWiseOrderPreserving
2.7 Functionality related to the affine partial mappings
2.7-1 LargestSourcesOfAffineMappings
2.7-2 Multpk
2.7-3 SetOnWhichMappingIsClassWiseOrderPreserving
2.8 Transition graphs and transition matrices
2.8-1 TransitionGraph
2.8-2 OrbitsModulo
2.8-3 FactorizationOnConnectedComponents
2.8-4 TransitionMatrix
2.9 Trajectories
2.9-1 Trajectory
2.9-2 TrajectoryModulo
2.9-3 CoefficientsOnTrajectory
2.9-4 IncreasingOn
2.10 Special functions for non-bijective mappings and miscellanea
2.10-1 LikelyContractionCentre
2.10-2 GuessedDivergence
2.10-3 ImageDensity
2.10-4 RightInverse
2.10-5 CommonRightInverse
2.11 The categories and families of rcwa mappings
2.11-1 IsRcwaMapping
2.11-2 RcwaMappingsFamily
3. Residue Class-Wise Affine Groups
3.1 Constructing residue class-wise affine groups
3.1-1 RCWA
3.1-2 Random
3.1-3 IsomorphismRcwaGroup
3.2 Attributes and properties of rcwa groups
3.2-1 Modulus
3.2-2 IsTame
3.2-3 PrimeSet
3.3 Membership testing, order computation, permutation- / matrix representations
3.3-1 \in
3.3-2 Size
3.3-3 IsomorphismPermGroup
3.3-4 IsomorphismMatrixGroup
3.4 Factoring elements into generators
3.4-1 PreImagesRepresentative
3.4-2 PreImagesRepresentatives
3.5 The action of an rcwa group on the underlying ring R
3.5-1 IsTransitive
3.5-2 RepresentativeAction
3.5-3 RepresentativeActionPreImage
3.5-4 RepresentativeAction
3.5-5 ShortOrbits
3.5-6 OrbitsModulo
3.6 Conjugacy in RCWA(R)
3.6-1 IsConjugate
3.6-2 RepresentativeAction
3.6-3 ShortCycles
3.6-4 NrConjugacyClassesOfRCWAZOfOrder
3.7 Restriction and induction
3.7-1 Restriction
3.7-2 Restriction
3.7-3 Induction
3.7-4 DirectProduct
3.8 Special attributes for tame rcwa groups
3.8-1 RespectedPartition
3.8-2 ActionOnRespectedPartition
3.8-3 IntegralConjugate
3.8-4 IntegralizingConjugator
3.9 The categories and families of rcwa groups
3.9-1 IsRcwaGroup
3.9-2 IntegralRcwaGroupsFamily
4. Examples
4.1 Factoring Collatz' permutation of the integers
4.2 An rcwa mapping which seems to be contracting, but very slow
4.3 Checking a result by P. Andaloro
4.4 Two examples by Matthews and Leigh
4.5 Exploring the structure of a wild rcwa group
4.6 A wild rcwa mapping which has only finite cycles
4.7 An abelian rcwa group over a polynomial ring
4.8 An rcwa representation of a small group
4.9 An rcwa representation of the symmetric group on 10 points
4.10 Checking for solvability
4.11 Some examples over (semi)localizations of the integers
4.12 Twisting 257-cycles into an rcwa mapping with modulus 32
4.13 The behaviour of the moduli of powers
4.14 Images and preimages under the Collatz mapping
4.15 A group which acts 4-transitively on the positive integers
4.16 A group which acts 3-transitively, but not 4-transitively on Z
4.17 Grigorchuk groups
5. The Algorithms Implemented in RCWA
6. Installation and auxiliary functions
6.1 Requirements
6.2 Installation
6.3 Building the manual
6.3-1 RCWABuildManual
6.4 The Info class of the package
6.4-1 InfoRCWA
6.5 The testing routine
6.5-1 RCWATest

Top of Book | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | Bib | Ind

generated by GAPDoc2HTML