RCWA

Residue-Class-Wise Affine Groups

Version 3.2.0

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), see the author's article

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

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

Manual and Examples

• The RCWA manual is available in the following formats:
  • HTML
  • PDF
• Examples for the use of RCWA.
• A little RCWA Picture Gallery.
• Slides from some of my talks on the subject.

Requirements and Installation

RCWA can be used under almost any operating system. RCWA requires only a recent GAP installation and the recent version of ResClasses. For details see the README file of the package. The installation requires only extracting the archive file in the pkg/ subdirectory of the GAP root directory. To load the package, enter LoadPackage("rcwa"); at the GAP prompt.

Download

Download one of the following archives:

• rcwa-3.2.0.tar.gz, rcwa-3.2.0-win.zip (recent version, released 07-May-2012, about 1.3 MB).
• rcwa-2.5.4.tar.gz (last 2.x version, released 26-Sep-2007).

The .tar.gz files are for all operating systems except for Windows, while the -win.zip file is the Windows version. RCWA is redistributed on the GAP website here. Note that it may take a while until the redistribution site picks up the recent version.

If you install RCWA or if you use it in some of your work, then please let me know. - I am interested very much in any applications of this package. Also please let me know if you have problems with this package, if you wish to make comments or suggestions or if you find bugs.

Acknowledgements

I am grateful to John P. McDermott for the discovery that the group discussed in Section 7.1 of the manual is isomorphic to the Higman-Thompson group (which is a finitely presented infinite simple group), and to Laurent Bartholdi for his hint on how to construct wreath products of residue-class-wise affine groups with the infinite cyclic group (Z,+).

Further, I thank Bettina Eick for communicating this package and for her kind help in improving its documentation. Last but not least I thank the two anonymous referees for their constructive criticism and their helpful suggestions.