*R*esidue-*C*lass-*W*ise
*A*ffine Groups

Stefan Kohl

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

Algorithms for a Class of Infinite Permutation Groups.DOI: 10.1016/j.jsc.2007.12.001.

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

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

RCWA can be used on any platform for which GAP is available.
It requires only a recent GAP installation and the recent version of
ResClasses.
For details see the README file.
Like any other GAP package, RCWA is usually installed in the `pkg/`

subdirectory of the GAP distribution. This is accomplished by extracting
the distribution file in this directory. To load the package, enter
`LoadPackage("rcwa");`

at the GAP prompt.

Download the recent version of this package from here. To install an older version, download one of the following archives:

- rcwa-4.6.1.tar.gz, rcwa-4.6.1-win.zip (for GAP >=4.8.7 in 64-bit mode, released 18-Dec-2017, about 13 MB).
- rcwa-4.5.1.tar.gz, rcwa-4.5.1-win.zip (for GAP >=4.8.5 in 64-bit mode, released 13-Mar-2017, about 13 MB).
- rcwa-4.4.1.tar.gz, rcwa-4.4.1-win.zip (for GAP >=4.8, released 22-May-2016, about 13 MB).
- rcwa-4.3.1.tar.gz, rcwa-4.3.1-win.zip (for GAP 4.8, released 09-Mar-2016, about 13 MB).
- rcwa-3.7.0.tar.gz, rcwa-3.7.0-win.zip (for GAP 4.7, released 21-Jul-2014, about 5.3 MB).
- rcwa-3.6.1.tar.gz, rcwa-3.6.1-win.zip (for GAP 4.7, released 18-Nov-2013, about 5.2 MB).
- rcwa-3.5.1.tar.gz, rcwa-3.5.1-win.zip (for GAP 4.6, released 30-Dec-2012, about 1.4 MB).
- rcwa-3.0.4.tar.gz, rcwa-3.0.4-win.zip (for GAP 4.4.12, released 04-Jun-2011).
- rcwa-2.5.4.tar.gz (last 2.x version, for GAP 4.4.12, 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 use RCWA 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.

I am grateful to
John P. McDermott
for the discovery that the group discussed in Section 7.1 of the manual 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 the infinite cyclic group (**Z**,+) 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.

Back to main page | Last modified: 30-Sep-2018 |