Residue-Class-Wise Affine 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:
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
A Simple Group Generated by Involutions Interchanging Residue Classes of the Integers. Math. Z. 264 (2010), no. 4, 927-938. DOI: 10.1007/s00209-009-0497-8.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. J. Symb. Comput. 43 (2008), no. 8, 545-581.The type of groups the RCWA package deals with is also discussed in the author's thesis.
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:
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 |