Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind

[Top of Book] [Contents] [Next Chapter]

RCWA

Residue-Class-Wise Affine Groups

4.7.1

6 December 2022

Stefan Kohl
Email: sk239@st-andrews.ac.uk
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 - 2018 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 https://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

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 CTCSCRSplit
  2.5-2 FactorizationIntoCSCRCT
  2.5-3 PrimeSwitch
  2.5-4 mKnot

2.6 Extracting roots of residue-class-wise affine mappings

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.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.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 The testing routines

  9.3-1 RCWATestInstall
  9.3-2 RCWATestAll
  9.3-3 RCWATestExamples

9.4 The Info class of the package

[Top of Book] [Contents] [Next Chapter]

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind

generated by GAPDoc2HTML