RCWA

Residue-Class-Wise Affine Groups

Version 2.5.4

Stefan Kohl

Abstract

This package for GAP 4 provides implementations of algorithms and methods for computing in certain infinite permutation groups. These groups act on the set of integers or on the set of elements of another suitable ring:

Let R be a principal ideal domain. Given disjoint residue classes r1(m1) and r2(m2) of R, let the corresponding class transposition be the permutation of R which interchanges r1+km1 and r2+km2 for each k in R and which fixes all other points. Further let CT(R) be the group which is generated by the set of all class transpositions of R. At least in case R = Z, this group is simple.

The RCWA package permits to compute in the group CT(R), where R is either the ring of integers or a univariate polynomial ring GF(q)[x] over a finite field. This means that in principle it allows to construct and investigate all finitely generated groups which embed into CT(R) for one of the mentioned rings R. For R = Z, this holds for the following 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 the infinite cyclic group (Z,+).
• Many, many further groups which are not listed here.

This list permits already to conclude that CT(Z) has finitely generated subgroups which do not have finite presentations, and such with algorithmically unsolvable membership problem. However the list is certainly by far not exhaustive, and using this package it is easy to construct groups falling into the last-mentioned category.

For results on the group CT(Z) including a proof that it is simple, see the preprint A Simple Group Generated by Involutions Interchanging Residue Classes of the Integers (DVI PS PDF).

Descriptions of many of the algorithms and methods which are implemented in this package can be found in the author's article

The type of groups the RCWA package deals with is also discussed in the author's thesis.

RCWA is published / redistributed on the GAP website here.

Download, Manual and Examples

• Download RCWA: rcwa-2.5.4.tar.gz (1.4 MB).
• RCWA can be used under any operating system for which GAP is available.
• Requirements: GAP 4.4.7 or newer, ResClasses 2.5.1 or newer, GRAPE 4.0 or newer, Polycyclic 2.1 or newer and GAPDoc 1.0 or newer. With possible exception of the most recent versions of ResClasses and GAPDoc, all needed packages are already present in an up-to-date standard GAP installation.
• Installation: Extract the distribution file in the pkg/ subdirectory of the GAP root directory. Then issue LoadPackage("rcwa"); at the GAP prompt to load the package.
• Manual: HTML PDF.
• Examples for the use of RCWA.
• A little RCWA Picture Gallery.
• RCWA's entry in ORMS (Oberwolfach References on Mathematical Software).
• Slides from some of my talks on the subject.
• A readme file which provides similar information as given on this webpage.
• Version history: See relnotes.txt.
• GAP - readable package information: See PackageInfo.g.
• An announcement of this package in Russian can be found on this page.

If you have problems with this package, wish to make comments or suggestions, or if you find bugs, please send me an e - mail. Please also let me know if you use RCWA in some of your work.

Acknowledgements

I am very grateful to Bettina Eick for communicating this package and for her kind help in improving its documentation. Further I thank the two anonymous referees for their constructive criticism and their helpful suggestions.

Likewise I am very grateful to Laurent Bartholdi for his hint on how to construct wreath products of residue-class-wise affine groups with the infinite cyclic group (Z,+). Last but not least I thank all the people who have invited me so far to give talks on the subject in their seminars and on their conferences.