A SIMPLE GROUP GENERATED BY INVOLUTIONS INTERCHANGING RESIDUE CLASSES OF THE INTEGERS

STEFAN KOHL

Abstract. We present a countable simple group which arises in a natural way from the arithmetical structure of the ring of integers.

1. Introduction

Various types of infinite simple groups are treated in the literature so far: We refer to Carter [4] for the simple groups of Lie type, to Higman [9] and Stein [21] for finitely presented simple groups, to Kegel, Wehrfritz [11] for locally finite simple groups, to Baer [1] for composition factors of infinite symmetric groups, and to Ol’shanskii [20] and Chehata [5] for constructions of simple groups with certain given special properties.

Here we present and investigate an infinite simple group, which emerges in a natural way from the arithmetical structure of the ring of integers. By r(m) we denote the residue class r + mℤ.

Definition 1.1. Let CT(ℤ) be the group generated by the set of all class transpositions: Given disjoint residue classes r_{1}(m_{1}) and r_{2}(m_{2}) of ℤ, we define the class transposition τ_{r_{1}(m_{1}),r_{2}(m_{2})} ∈ Sym(ℤ) as the permutation which interchanges r_{1} + km_{1} and r_{2} + km_{2} for each integer k and which fixes all other points. Here we assume that 0 ⩽ r_{1} < m_{1} and that 0 ⩽ r_{2} < m_{2}. For convenience, we set τ := τ_{0(2),1(2)} : n ↦ n + (−1)^{n}.

The theorems given below list various properties of the group CT(ℤ) and provide information on the class of groups which embed into it, respectively. Their proof is the main subject of this article.

Theorem 1.2 (Properties of CT(ℤ)).

(1) The group CT(ℤ) is simple.

(2) The group CT(ℤ) is countable, but it has an uncountable series of simple subgroups which is parametrized by the sets of odd primes.

(3) The group CT(ℤ) is not finitely generated.

(4) The torsion elements of CT(ℤ) are divisible.

(5) The group CT(ℤ) acts highly transitively on ℕ_{0}, and it has a locally finite simple subgroup which does so as well.

Theorem 1.3 (Richness of the class of subgroups of CT(ℤ)).

(1) Every finite group embeds into CT(ℤ).

(2) Every free group of finite rank embeds into CT(ℤ).

(3) Every free product of finitely many finite groups embeds into CT(ℤ).

(4) The class of subgroups of CT(ℤ) is closed under taking (a) direct products, (b) wreath products with finite groups, and

2000 Mathematics Subject Classification. Primary 20E32, secondary 20B40, 20B22, 20-04.

(c) restricted wreath products with (ℤ, +).

(5) The group CT(ℤ) has (a) finitely generated subgroups which do not have finite presentations, and (b) finitely generated subgroups with unsolvable membership problem.

Note however that since words in the generators of subgroups of CT(ℤ) can always be evaluated and compared, groups with unsolvable word problem do not embed into CT(ℤ).

So far, research in computational group theory focussed mainly on finite permutation groups, matrix groups, finitely presented groups, polycyclically presented groups and automatic groups. For details, we refer to [10].

This article describes another large class of groups which are accessible to computational methods. This class includes the subgroups of CT(ℤ). Algorithms to compute with such groups are described in [16] and implemented in the package RCWA [14] for the computer algebra system GAP [8]. Many of the results proved in this article have first been discovered during extensive experiments with the RCWA package.

As a little example of how to compute in the group CT(ℤ), we factor the permutation

α ∈ Sym(ℤ) : n ⟼ \begin{cases}2n/3 & if n ∈ 0(3), \\ (4n − 1)/3 & if n ∈ 1(3), \\ (4n + 1)/3 & if n ∈ 2(3) \end{cases}

into class transpositions, which shows that α ∈ CT(ℤ). This permutation has already been investigated by Lothar Collatz in 1932, and its cycle structure is unknown so far (cf. Keller [12], Wirsching [22]).

In addition to the results given in Theorems 1.2 and 1.3, in the last section we determine two simple supergroups of CT(ℤ) which are in a certain sense ‘canonical’.

2. Basic Properties of CT(ℤ)

In this section we prove that the group CT(ℤ) is not finitely generated, that every finite group embeds into it, that its torsion elements are divisible and that it acts highly transitively on ℕ_{0}. This covers Theorem 1.2, Assertion (3), (4) and the first part of (5), as well as Theorem 1.3, Assertion (1). However, first we need to introduce some basic terms:

Definition 2.1. We call a mapping f : ℤ → ℤ residue-class-wise affine if there is a positive integer m such that the restrictions of f to the residue classes r(m) ∈ ℤ/mℤ are all affine, i.e. given by f|_{r(m)} : r(m) → ℤ, n ↦ (a_{r(m)} · n + b_{r(m)})/c_{r(m)} for certain coefficients a_{r(m)}, b_{r(m)}, c_{r(m)} ∈ ℤ depending on r(m). We call the least possible m the modulus of f, written Mod(f). For reasons of uniqueness, we assume that gcd(a_{r(m)}, b_{r(m)}, c_{r(m)}) = 1 and that c_{r(m)} > 0. We define the multiplier of f by lcm{a_{r(m)} | r(m) ∈ ℤ/mℤ}, and the divisor of f by lcm{c_{r(m)} | r(m) ∈ ℤ/mℤ}. We call the mapping f integral if its divisor is 1. We call f class-wise order-preserving if all a_{r(m)} are positive.

It is easy to see that the permutations of this kind form a countable supergroup of CT(ℤ).

Definition 2.2. We denote the group which is formed by all residue-class-wise affine permutations of ℤ by RCWA(ℤ), and call its subgroups residue-class-wise affine groups.

The notation ‘CT(ℤ)’, respectively, ‘RCWA(ℤ)’ reflects that generalizations to suitable rings other than ℤ make perfect sense. For the sake of simplicity and to keep the article easy to read, we refrain from following this possibly fruitful direction of research here.

Theorem 2.3. The group CT(ℤ) is not finitely generated.

Proof. It is easy to see that the multiplier of a product of residue-class-wise affine permutations divides the product of the multipliers of the factors, and that the corresponding assertion about divisors holds as well. Further, inversion obviously interchanges multiplier and divisor. Therefore as there are infinitely many primes and as for any n ∈ ℕ there is a class transposition τ_{1(2),0(2n)} with multiplier and divisor n, the assertion follows. □

Finite symmetric groups embed into CT(ℤ):

Definition 2.4. Let m ∈ ℕ, and let S_{m} be the symmetric group of degree m. We define the monomorphism φ_{m} : S_{m} ↪ CT(ℤ) by σ ↦ (σ^{φ_{m}}: n ↦ n + (n mod m)^{σ}− (n mod m)), where we assume that S_{m} acts naturally on the set {0, 1, …, m − 1}.

Theorem 2.5. Any finite group embeds into CT(ℤ), and the group CT(ℤ) acts highly transitively on ℕ_{0}.

Proof. The first assertion is immediate.

Let m ∈ ℕ. Just like the group S_{m} itself, its image under φ_{m} acts m-transitively on the set {0, 1, …, m − 1}. The second assertion follows since m can be chosen arbitrary large and since class transpositions map nonnegative integers to nonnegative integers. □

Theorem 2.6. The torsion elements of CT(ℤ) are divisible.

Proof. We show that given an element g ∈ CT(ℤ) of finite order and a positive integer k, there is always an h ∈ CT(ℤ) such that h^{k} = g: Since g has finite order, it permutes a partition P of ℤ into finitely many residue classes on all of which it is affine. A k-th root h can be constructed from g by ‘slicing’ cycles ∏_{i=2}^{l} τ_{r_{1}(m_{1}),r_{i}(m_{i})} on P into cycles ∏_{i=1}^{l} ∏_{j=max(2−i,0)}^{k−1} τ_{r_{1}(km_{1}),r_{i}+jm_{i}(km_{i})} of the k-fold length on the refined partition obtained from P by decomposing any r_{i}(m_{i}) ∈ P into residue classes (mod km_{i}). □

3. The Simplicity of CT(ℤ)

The aim of this section is to show that the group CT(ℤ) is simple, and that it has an uncountable series of simple subgroups which is parametrized by the sets of odd primes. This covers Theorem 1.2, Assertion (1) and (2). First we need some lemmata:

Lemma 3.1. Given two class transpositions τ_{r_{1}(m_{1}),r_{2}(m_{2})}, τ_{r_{3}(m_{3}),r_{4}(m_{4})} not equal to τ, there is a product π of 6 class transpositions such that τ_{r_{1}(m_{1}),r_{2}(m_{2})}^{π} = τ_{r_{3}(m_{3}),r_{4}(m_{4})}.

Proof. Let r_{5}(m_{5}), r_{6}(m_{6}) ⊂ ℤ \ (r_{1}(m_{1}) ∪ r_{2}(m_{2})) be disjoint residue classes such that ∪_{i=3}^{6}r_{i}(m_{i}) ≠ ℤ, and let r_{7}(m_{7}), r_{8}(m_{8}) ⊂ ℤ \ ∪_{i=3}^{6}r_{i}(m_{i}) be disjoint residue classes. Then the following hold:

(1) τ_{r_{1}(m_{1}),r_{2}(m_{2})}τ_{r_{1}(m_{1}),r_{5}(m_{5})} · τ_{r_{2}(m_{2}),r_{6}(m_{6})} = τ_{r_{5}(m_{5}),r_{6}(m_{6})}.

(2) τ_{r_{5}(m_{5}),r_{6}(m_{6})}τ_{r_{5}(m_{5}),r_{7}(m_{7})} · τ_{r_{6}(m_{6}),r_{8}(m_{8})} = τ_{r_{7}(m_{7}),r_{8}(m_{8})}.
(3) τ_{r_{7}(m_{7}),r_{8}(m_{8})}τ_{r_{3}(m_{3}),r_{7}(m_{7})} · τ_{r_{4}(m_{4}),r_{8}(m_{8})} = τ_{r_{3}(m_{3}),r_{4}(m_{4})}.

The assertion follows. □

Lemma 3.2. Let σ, υ ∈ RCWA(ℤ), and put m := Mod(σ). If υ is integral and fixes all residue classes (mod m) setwise, then the commutator [σ, υ] is integral as well.

Proof. An affine partial mapping α of [σ, υ] = σ^{−1}υ^{−1}συ is the product of affine partial mappings α_{σ^{−1}}, α_{υ^{−1}}, α_{σ} and α_{υ} of σ^{−1}, υ^{−1}, σ and υ, respectively. Since υ fixes all residue classes (mod m), we have α_{σ^{−1}} = α_{σ}^{−1}, and therefore α = α_{υ^{−1}}^{α_{σ}} · α_{υ}. The assertion follows since the translations and reflections generate a normal subgroup of the affine group of the rationals. □

Lemma 3.3. Let G be a subgroup of RCWA(ℤ) which contains CT(ℤ). Then any nontrivial normal subgroup N ⊴ G has an integral element ι ≠ 1.

Proof. Let σ ∈ N \ {1}, and let m := Mod(σ). Without loss of generality we can assume that there is a residue class r(m) such that r(m)^{σ} ≠ r(m). By Lemma 3.2, the mapping ι := [σ, τ_{r(2m),r+m(2m)}] ∈ N \ {1} is integral. □

Now we can prove our theorem:

Theorem 3.4. The group CT(ℤ) is simple.

Proof. Let N be a nontrivial normal subgroup of CT(ℤ). We have to show that N contains all class transpositions.

By Lemma 3.1, all class transpositions except for τ are conjugate in CT(ℤ). Furthermore we have τ = τ_{0(4),1(4)} · τ_{2(4),3(4)}. Therefore it is already sufficient to show that N contains one class transposition which is not equal to τ.

By Lemma 3.3, the normal subgroup N has an integral element ι_{1} ≠ 1. Let m ⩾ 3 be a multiple of the modulus of ι_{1}, and choose a residue class r(m) which is moved by ι_{1}. Then put ι_{2} := τ_{r(2m),r+m(2m)} · τ_{r(2m)^{ι_{1}} ,(r+m(2m))^{ι_{1}}} = [τ_{r(2m),r+m(2m)}, ι_{1}] ∈ N.

By the choice of m, we can now choose two distinct residue classes r_{1}(2m) and r_{2}(2m) in the complement of the support of ι_{2}. Then we have

τ_{r_{1}(2m),r_{2}(2m)} = ι_{2}^{τ_{r(2m),r_{1}(4m)}·τ_{r+m(2m),r_{2}(4m)}}
· ι_{2}^{τ_{r(2m),r_{1}+2m(4m)}·τ_{r+m(2m),r_{2}+2m(4m)}} ∈ N,

which completes the proof of the theorem. □

Remark 3.5. Assume CT(ℤ) ⩽ G ⩽ RCWA(ℤ), and let N be a nontrivial normal subgroup of G. Then the proof of Theorem 3.4 shows in fact that N contains CT(ℤ), if we additionally take care that in the third paragraph we choose m sufficiently large such that there is indeed a residue class r(m) which is not mapped to itself under ι_{1}.

Definition 3.6. Given a set ℙ of odd primes, let CT_{ℙ}(ℤ) ⩽ CT(ℤ) denote the subgroup which is generated by all class transpositions τ_{r_{1}(m_{1}),r_{2}(m_{2})} for which all odd prime factors of m_{1} and m_{2} lie in ℙ.

Corollary 3.7. The groups CT_{ℙ}(ℤ) are simple. Therefore the group CT(ℤ) has an uncountable series of simple subgroups, which is parametrized by the sets of odd primes.

Proof. All of our arguments in this section apply to the groups CT_{ℙ}(ℤ) as well: In the proof of Lemma 3.1, we can choose the four residue classes r_{5}(m_{5}), …, r_{8}(m_{8}) in such a way that all prime factors of their moduli already divide m_{1}m_{2}m_{3}m_{4}. The proofs of Lemmas 3.2, 3.3 and Theorem 3.4 likewise do not require the presence of class transpositions whose moduli have certain odd factors. □

Problem 3.8 (Isomorphism Problem). Are there distinct sets ℙ_{1} and ℙ_{2} of odd primes such that CT_{ℙ_{1}}(ℤ) ≅ CT_{ℙ_{2}}(ℤ)?

4. Richness of the Class of Subgroups of CT(ℤ)

In this section we prove Theorem 1.3, Assertion (2) – (5), as well as the second part of Theorem 1.2, Assertion (5).

Theorem 4.1. Free groups of finite rank embed into CT(ℤ).

Proof. It suffices to show that the free group of rank 2 embeds. An example of an embedding is

φ_{F_{2}} : F_{2} = ⟨a, b⟩ ↪ CT(ℤ), a ↦ (τ · τ_{0(2),1(4)})^{2}, b ↦ (τ · τ_{0(2),3(4)})^{2}.

This can be seen by applying the Table-Tennis Lemma (see for example de la Harpe [6], Section II.B.) to the cyclic groups generated by the images of a and b under φ_{F_{2}} and the sets 0(4) ∪ 1(4) and 2(4) ∪ 3(4). □

Theorem 4.2. Every free product of finitely many finite groups embeds into CT(ℤ).

Proof. Let G_{0}, …, G_{m−1} be finite groups. To see that their free product embeds into CT(ℤ), proceed as follows: First consider regular permutation representations φ_{r} of the groups G_{r} on the residue classes (mod |G_{r}|). Then take conjugates H_{r} := (im φ_{r})^{σ_{r}} of the images of these representations under mappings σ_{r} ∈ CT(ℤ) which map 0(|G_{r}|) to ℤ\r(m). Finally use the fact that point stabilizers in regular permutation groups are trivial and apply the Table-Tennis Lemma to the groups H_{r} and the residue classes r(m) to see that the group generated by the H_{r} is isomorphic to their free product. □

The group RCWA(ℤ) is not co-Hopfian. We need the following monomorphisms:

Definition 4.3. Let f be an injective residue-class-wise affine mapping, and let further π_{f} : RCWA(ℤ) ↪ RCWA(ℤ), σ ↦ σ_{f} be the monomorphism defined by the properties ∀σ ∈ RCWA(ℤ) fσ_{f} = σf and supp(im π_{f}) ⊆ im f. Then we call π_{f} the restriction monomorphism associated with f.

Theorem 4.4. The class of subgroups of CT(ℤ) is closed under taking direct products, under taking wreath products with finite groups and under taking restricted wreath products with (ℤ, +). It is also closed under taking upwards extensions by finite groups.

Proof. Given any two subgroups G, H ⩽ RCWA(ℤ), the group generated by π_{n↦2n}(G) and π_{n↦2n+1}(H) is clearly isomorphic to G × H. This argument applies to subgroups of our group CT(ℤ) as well, since the image of a class transposition τ_{r_{1}(m_{1}),r_{2}(m_{2})} under a restriction monomorphism π_{n↦mn+r} is τ_{mr_{1}+r(mm_{1}),mr_{2}+r(mm_{2})}.

Looking at the monomorphisms π_{n↦mn+r} and φ_{m}, it is immediate to see that the classes of subgroups of RCWA(ℤ) and CT(ℤ) are also closed under taking wreath products with finite groups. The assertion on upwards extensions by finite groups follows now from the Universal Embedding Theorem (see e.g. Theorem 2.6A in Dixon and Mortimer [7]).

Given a subgroup G ⩽ CT(ℤ), the group generated by π_{n↦4n+3}(G) and τ · τ_{0(2),1(4)} is isomorphic to the restricted wreath product G ≀ (ℤ, +). This holds since the orbit of the residue class 3(4) under the action of the cyclic group ⟨τ · τ_{0(2),1(4)}⟩ consists of infinitely many pairwise disjoint residue classes, which means that the conjugates of π_{n↦4n+3}(G) under powers of τ · τ_{0(2),1(4)} have pairwise disjoint supports. □

Corollary 4.5. The group CT(ℤ) has (1) finitely generated subgroups which do not have finite presentations, and

(2) finitely generated subgroups with unsolvable membership problem.

Proof.

(1) By Theorem 4.4, the group CT(ℤ) contains nontrivial restricted wreath products G ≀ (ℤ, +). By Baumslag [2], these do not have finite presentations.

(2) Let F_{2} = ⟨a, b⟩ be the free group of rank 2. Further let r_{1}, …, r_{k} ∈ F_{2} be the relators of a finitely presented group with unsolvable word problem – by Novikov [19] and Boone [3], such groups exist. Then the membership problem for the group ⟨(a, a), (b, b), (1, r_{1}), …, (1, r_{k})⟩ < F_{2} × F_{2} is unsolvable (cf. Mihailova [18]; see also Lyndon and Schupp [17], Chapter IV.4). Therefore as by Theorems 4.1 and 4.4 the group F_{2} × F_{2} embeds into CT(ℤ), there exist finitely generated subgroups G < CT(ℤ) with unsolvable membership problem. □

The class transpositions which interchange two residue classes with the same modulus generate a proper subgroup of CT(ℤ), which acts highly transitively on ℕ_{0} as well:

Definition 4.6. Let CT_{int}(ℤ) denote the subgroup of CT(ℤ) which is generated by all integral class transpositions.

Theorem 4.7. The group CT_{int}(ℤ) is locally finite and simple.

Proof. Finitely generated subgroups of CT_{int}(ℤ) act faithfully on the set of residue classes modulo the lcm of the moduli of the generators. Therefore they are finite. Hence the group CT_{int}(ℤ) is locally finite.

Let N be a nontrivial normal subgroup of CT_{int}(ℤ). In order to prove that CT_{int}(ℤ) is simple, we have to show that N contains any class transposition of the form τ_{r_{1}(m),r_{2}(m)}.

Let ι ∈ N\{1}, let m>2 be a multiple of Mod(ι) and choose a residue class r(m) in the support of ι. Then we have τ_{r(2m),r+m(2m)}·τ_{r(2m)^{ι},(r+m(2m))^{ι}} = [ι, τ_{r(2m),r+m(2m)}] ∈N.

All such products of two integral class transpositions with modulus 2m and disjoint supports are conjugate in CT_{int}(ℤ). The reason for this is that their preimages under the monomorphism φ_{2m} have the same cycle structure, and are therefore conjugate in S_{2m}.

Let τ_{1} = τ_{r_{1}(m),r_{2}(m)} be an integral class transposition with modulus m. Then for any integral class transposition τ_{2} with modulus 2m whose support intersects trivially with the one of τ_{1}, we have τ_{1} = (τ_{2} · τ_{r_{1}(2m),r_{2}(2m)}) · (τ_{2} · τ_{r_{1}+m(2m),r_{2}+m(2m)}) ∈ N.

Given a divisor d of m and an integral class transposition τ_{r_{1}(d),r_{2}(d)} with modulus d, we have τ_{r_{1}(d),r_{2}(d)} = ∏_{k=0}^{m/d−1} τ_{r_{1}+kd(m),r_{2}+kd(m)} ∈ N.

In the second paragraph of the proof, we can choose m to be a multiple of any given positive integer. Therefore we can conclude that N contains indeed any integral class transposition. Hence the group CT_{int}(ℤ) is simple, as claimed. □

5. Collatz’ Permutation Lies in CT(ℤ)

In this section, as a small but illustrative example we show that Collatz’ permutation

α ∈ RCWA(ℤ) : n ⟼ \begin{cases}2n/3 & if n ∈ 0(3), \\ (4n − 1)/3 & if n ∈ 1(3), \\ (4n + 1)/3 & if n ∈ 2(3) \end{cases}

lies in CT(ℤ).

In Keller [12] it is shown that α has at most finitely many cycles of any given finite length. However according to Wirsching [22], it is for example not yet known whether the cycle ( … 34 45 30 20 27 18 12 8 11 15 10 13 17 23 31 …) of α is finite or infinite.

In spite of this we can show that the permutation α lies in CT(ℤ) by determining an explicit factorization into generators.

The major obstacle we are confronted with when trying to obtain such a factorization is the fact that the multiplier and the divisor of α are coprime, whereas the multiplier and the divisor of a class transposition are always the same. We even need to form a product of class transpositions in such a way that one prime divisor gets eliminated from the multiplier of the product, but appears in the denominators of all of its affine partial mappings.

As a first step towards a solution of the factorization problem, we hence attempt to determine some product of class transpositions which has coprime multiplier and divisor. We find that given an odd prime p, the permutation

σ_{p} := τ_{0(8),1(2p)} · τ_{4(8),2p−1(2p)}
· τ_{0(4),1(2p)} · τ_{2(4),2p−1(2p)}
· τ_{2(2p),1(4p)} · τ_{4(2p),2p+1(4p)} ∈ CT(ℤ)

has multiplier p and divisor 2. Indeed, evaluating this product yields

σ_{p} : n ⟼ \begin{cases}(pn + 2p − 2)/2 & if n ∈ 2(4), \\ n/2 & if n ∈ 0(4) \ (4(4p) ∪ 8(4p)), \\ n + 2p − 7 & if n ∈ 8(4p), \\ n − 2p + 5 & if n ∈ 2p − 1(2p), \\ n + 1 & if n ∈ 1(2p), \\ n − 3 & if n ∈ 4(4p), \\ n & if n ∈ 1(2) \ (1(2p) ∪ 2p − 1(2p)). \end{cases}

The GAP [8] package RCWA [14] provides a factorization routine for residue-class-wise affine permutations, which uses certain elaborate heuristics. The permutations σ_{p} and their images under restriction monomorphisms π_{n↦mn+r} play a key role in this routine. It has been used to obtain the following factorization of α:

α = τ_{2(3),3(6)} · τ_{1(3),0(6)} · τ_{0(3),1(3)} · τ · τ_{0(36),1(36)}
· τ_{0(36),35(36)} · τ_{0(36),31(36)} · τ_{0(36),23(36)} · τ_{0(36),18(36)} · τ_{0(36),19(36)}
· τ_{0(36),17(36)} · τ_{0(36),13(36)} · τ_{0(36),5(36)} · τ_{2(36),10(36)} · τ_{2(36),11(36)}
· τ_{2(36),15(36)} · τ_{2(36),20(36)} · τ_{2(36),28(36)} · τ_{2(36),26(36)} · τ_{2(36),25(36)}
· τ_{2(36),21(36)} · τ_{2(36),4(36)} · τ_{3(36),8(36)} · τ_{3(36),7(36)} · τ_{9(36),16(36)}
· τ_{9(36),14(36)} · τ_{9(36),12(36)} · τ_{22(36),34(36)} · τ_{27(36),32(36)} · τ_{27(36),30(36)}
· τ_{29(36),33(36)} · τ_{10(18),35(36)} · τ_{5(18),35(36)} · τ_{10(18),17(36)} · τ_{5(18),17(36)}
· τ_{8(12),14(24)} · τ_{6(9),17(18)} · τ_{3(9),17(18)} · τ_{0(9),17(18)} · τ_{6(9),16(18)}
· τ_{3(9),16(18)} · τ_{0(9),16(18)} · τ_{6(9),11(18)} · τ_{3(9),11(18)} · τ_{0(9),11(18)}
· τ_{6(9),4(18)} · τ_{3(9),4(18)} · τ_{0(9),4(18)} · τ_{0(6),14(24)} · τ_{0(6),2(24)}
· τ_{8(12),17(18)} · τ_{7(12),17(18)} · τ_{8(12),11(18)} · τ_{7(12),11(18)} · σ_{3}^{−1}
· τ_{7(12),17(18)} · τ_{2(6),17(18)} · τ_{0(3),17(18)} · σ_{3}^{−3}.

This shows constructively that α ∈ CT(ℤ).

6. Two Simple Supergroups of CT(ℤ)

In this section we present two simple subgroups of RCWA(ℤ) which properly contain CT(ℤ) and which act highly transitively on ℤ.

We find them in the kernels of certain epimorphisms π^{+} : RCWA^{+}(ℤ) → (ℤ, +) and π^{−} : RCWA(ℤ) → ℤ^{×} ≅ C_{2}, where RCWA^{+}(ℤ) < RCWA(ℤ) denotes the subgroup consisting of all class-wise order-preserving elements.

Using the notation σ|_{r(m)} : n ↦ (a_{r(m)} · n + b_{r(m)})/c_{r(m)} for the affine partial mappings of an rcwa permutation σ with modulus m, these epimorphisms are given by

π^{+} : σ ↦ \frac{1}{m} ∑_{r(m)∈ℤ/mℤ} \frac{b_{r(m)}}{|a_{r(m)}|}

and

π^{−} : σ ↦ (−1)π^{+}(σ) + ∑_{r(m): a_{r(m)}<0} \frac{m − 2r}{m} ,

respectively (see Sections 2.11 and 2.12 in Kohl [13]).

Definition 6.1. We denote the kernels of π^{+} and π^{−} by K^{+} and K^{−}, respectively.

It is easy to see that CT(ℤ) < K^{+} < K^{−} < RCWA(ℤ).

Our simple groups will be the subgroups of K^{+} and K^{−}, respectively, which are generated by the elements which are tame in the following sense:

Definition 6.2. We call an element σ ∈ RCWA(ℤ) tame if it permutes a partition of ℤ into finitely many residue classes on each of which it is affine, and wild otherwise. We call a group G < RCWA(ℤ) tame if there is a common such partition for all elements of G, and wild otherwise. We call the specified partitions respected partitions of σ, respectively, G.

For an alternative characterization of this notion of tameness and a generalization of it to not necessarily bijective residue-class-wise affine mappings, see Kohl [13], [15].

Obviously, finite residue-class-wise affine groups and integral residue-class-wise affine permutations are tame.

Tameness is invariant under conjugation: If α ∈ RCWA(ℤ) respects a partition P, then a conjugate α^{β} respects the partition consisting of the images of the intersections of the residue classes in P with the sources of the affine partial mappings of β under β.

The product of two tame permutations is in general not tame. Tameness of products also does not induce an equivalence relation on the set of tame permutations: let for example a := τ_{1(6),4(6)}, b := τ_{0(5),2(5)} and c := τ_{3(4),4(6)}. Then ab and bc are tame, but ac is not.

If a tame group does not act faithfully on a respected partition, then the kernel of the action clearly does not act on ℕ_{0}. Thus as the group CT(ℤ) acts on ℕ_{0}, its tame subgroups are finite.

Definition 6.3. We denote the normal subgroups of K^{+} and K^{−} which are generated by the tame elements by K̃^{+} and K̃^{−}, respectively.

It is easy to see that all tame elements of RCWA(ℤ) can be factored into class transpositions and members of the following two series:

Definition 6.4. Let r(m) ⊆ ℤ be a residue class.

(1) We define the class shift ν_{r(m)} ∈ RCWA(ℤ) by

ν_{r(m)} : n ↦ \begin{cases}n + m & if n ∈ r(m), \\ n & otherwise. \end{cases}

(2) We define the class reflection ς_{r(m)} ∈ RCWA(ℤ) by

ς_{r(m)} : n ↦ \begin{cases}−n + 2r & if n ∈ r(m), \\ n & otherwise, \end{cases}

where we assume that 0 ⩽ r < m.

For convenience, we set ν := ν_{ℤ} : n ↦ n + 1 and ς := ς_{ℤ} : n ↦ −n.

Obviously, class shifts and class reflections do not lie in K^{−}.

Theorem 6.5. We have (1) K̃^{+} = ⟨CT(ℤ), ν_{1(3)} · ν_{2(3)}^{−1}⟩, and

(2) K̃^{−} = ⟨CT(ℤ), ν_{1(3)} · ν_{2(3)}, ς_{0(2)} · ν_{0(2)}⟩.

Proof. We determine series of generators:

(1) Considering respected partitions, we check that K̃^{+} is generated by (a) all class transpositions and

(b) all quotients of two class shifts with disjoint supports whose union has a nontrivial complement in ℤ.

For this we look at the process of factoring a given tame ϑ ∈ K^{+} into these elements: ad (a) Let P be a respected partition of ϑ. Divide ϑ by a product of class transpo-

sitions which respects P as well and which induces on P the same permutation as ϑ does. Now ϑ is integral and fixes P.

ad (b) Finally factor ϑ into quotients of two class shifts whose supports are distinct residue classes in P. This is possible since the lattice in ℤ^{|P|} which consists of all vectors with zero coordinate sum is spanned by the differences of two distinct canonical basis vectors.

(2) Considering respected partitions, we check that K̃^{−} is generated by

(a) all products of a class reflection and a class shift with the same support which has a nontrivial complement in ℤ,

(b) all class transpositions and

(c) all products of two class shifts with disjoint supports whose union has a nontrivial complement in ℤ.

For this we look at the process of factoring a given tame ϑ ∈ K^{−} into these elements: ad (a) Let P be a respected partition of ϑ of length at least 3. Divide ϑ from the

left by products ς_{r(m)} ·ν_{r(m)}, where r(m) runs over all residue classes in P on which ϑ is order-reversing. Now ϑ is class-wise order-preserving.

ad (b) Divide ϑ by a product of class transpositions which respects the partition P as well, and which also induces the same permutation on it. Now ϑ is integral and fixes P.

ad (c) Finally factor ϑ into products of two class shifts whose supports are distinct residue classes in P and inverses of such products. This is possible since the lattice in ℤ^{|P|} which consists of all vectors with even coordinate sum is spanned by the sums of two distinct canonical basis vectors.

Now we collapse series 1.(b), 2.(a) and 2.(c) by taking orbit representatives under the conjugation action of the group CT(ℤ) to obtain the indicated single generators. □

Theorem 6.6. The groups K̃^{+} and K̃^{−} are simple.

Proof. By Remark 3.5, nontrivial normal subgroups of K̃^{+} and K̃^{−} contain CT(ℤ).

(1) Let N be a nontrivial normal subgroup of K̃^{+}. Given disjoint residue classes r_{1}(m_{1}) and r_{2}(m_{2}) whose union has a nontrivial complement in ℤ, for an arbitrary residue class r_{3}(m_{3}) ⊆ ℤ \ (r_{1}(m_{1}) ∪ r_{2}(m_{2})) we have

ν_{r_{1}(m_{1})} · ν_{r_{2}(m_{2})}^{−1} = [τ_{r_{1}(m_{1}),r_{2}(m_{2})}, ν_{r_{3}(m_{3})} · ν_{r_{2}(m_{2})}^{−1}] ∈ N.

Putting r_{1}(m_{1}) := 1(3) and r_{2}(m_{2}) := 2(3), the simplicity of K̃^{+} follows from Theorem 6.5, Assertion (1).

(2) Let N be a nontrivial normal subgroup of K̃^{−}. Given disjoint residue classes r_{1}(m_{1}) and r_{2}(m_{2}) whose union has a nontrivial complement in ℤ, for an arbitrary residue class r_{3}(m_{3}) ⊆ ℤ \ (r_{1}(m_{1}) ∪ r_{2}(m_{2})) we have

ν_{r_{1}(m_{1})} · ν_{r_{2}(m_{2})} = [τ_{r_{1}(m_{1}),r_{2}(m_{2})}, ν_{r_{3}(m_{3})} · ς_{r_{1}(m_{1})}]
· [τ_{r_{1}(m_{1}),r_{2}(m_{2})}, ς_{r_{1}(m_{1})} · ν_{r_{1}(m_{1})}] ∈ N.

This shows in particular that N contains ν_{1(3)} · ν_{2(3)}. Let r(m) ⊂ ℤ be a residue class. Then for any residue class r̃(m̃) ⊆ ℤ \ r(m) we have

ς_{r(m)} · ν_{r(m)} = [τ_{r(m),r̃(m̃)}, ς_{r(m)} · ν_{r̃(m̃)}] · [τ_{r̃(2m̃),r̃+m̃(2m̃)}, ς_{r̃(2m̃)} · ν_{r̃(2m̃)}]
· (ν_{r̃(2m̃)} · ν_{r̃+m̃(2m̃)} · τ_{r̃(2m̃),r̃+m̃(2m̃)})^{−1} ∈ N.

This shows in particular that N contains also ς_{0(2)} · ν_{0(2)}, and the simplicity of the group K̃^{−} follows from Theorem 6.5, Assertion (2). □

Theorem 6.7. The groups K̃^{+} and K̃^{−} act highly transitively on ℤ.

Proof. Since K̃^{+} < K̃^{−} it is sufficient to prove the assertion for K̃^{+}. Let k be a positive integer, and let (n_{1}, …, n_{k}) and (ñ_{1}, …, ñ_{k}) be two k-tuples of pairwise distinct integers. We have to show that there is an element σ ∈ K̃^{+} such that (n_{1}^{σ}, …, n_{k}^{σ}) = (ñ_{1}, …, ñ_{k}).

Let m := 2k + 1, and choose a residue class r(m) which does not contain one of the points n_{i} or ñ_{i}. Define σ_{1}, σ̃_{1} ∈ K̃^{+} by

σ_{1} := ∏_{i:n_{i}<0}(ν_{r(m)} · ν_{n_{i}(m)}^{−1})^{⌊ \frac{n_{i}}{m} ⌋} and σ̃_{1} := ∏_{i:ñ_{i}<0}(ν_{r(m)} · ν_{ñ_{i}(m)}^{−1})^{⌊ \frac{ñ_{i}}{m} ⌋},

respectively. Then the images of all points n_{i} under σ_{1} are nonnegative, and the same holds for the images of the points ñ_{i} under σ̃_{1}. Since CT(ℤ) acts highly transitively on ℕ_{0}, we can choose an element σ_{2} ∈ CT(ℤ) < K̃^{+} which maps the images of the n_{i} under σ_{1} to the images of the ñ_{i} under σ̃_{1}. Now the permutation σ := σ_{1} · σ_{2} · σ̃_{1}^{−1} serves our purposes. □

Conjecture 6.8. The group RCWA(ℤ) is generated by its tame elements.

Remark 6.9. Conjecture 6.8 is equivalent to the assertion that K̃^{+} = K^{+} and K̃^{−} = K^{−}. If it holds, we have RCWA(ℤ) = ⟨CT(ℤ), ς_{0(2)}⟩:

(1) It is ν = ς_{0(2)} · τ · (ς_{0(2)}^{τ_{1(4),2(4)}} · ς_{0(2)}^{τ_{1(2),0(4)}})^{τ_{0(2),1(4)}} ∈ ⟨CT(ℤ), ς_{0(2)}⟩.

(2) It is ν_{0(2)} = τν, ν_{1(2)} = ν_{0(2)}^{τ}, ς_{1(2)} = ς_{0(2)}^{τ} and ς = ς_{0(2)} · ν_{1(2)} · ς_{1(2)}. Therefore we know that {ν_{0(2)}, ν_{1(2)}, ς_{1(2)}, ς} ⊂ ⟨CT(ℤ), ς_{0(2)}⟩.

(3) Let r(m) ⊂ ℤ be a residue class ≠ 1(2). We choose an arbitrary residue class r̃(m̃) ⊆ ℤ \ (0(2) ∪ r(m)), and put ϑ := τ_{0(2),r̃(m̃)} · τ_{r̃(m̃),r(m)} ∈ CT(ℤ). Then we have {ν_{r(m)}, ς_{r(m)}} = {ν_{0(2)}^{ϑ}, ς_{0(2)}^{ϑ}} ⊂ ⟨CT(ℤ), ς_{0(2)}⟩.

The factorization routine in RCWA [14] provides some evidence for Conjecture 6.8.

Acknowledgements

I thank Bettina Eick for her numerous and valuable hints regarding the layout of this article. Likewise I thank Laurent Bartholdi for pointing out that the classes of subgroups of CT(ℤ) and RCWA(ℤ) are closed under taking restricted wreath products with (ℤ, +).

References

1. Reinhold Baer, Die Kompositionsreihe der Gruppe aller eineindeutigen Abbildungen einer unendlichen Menge auf sich, Studia Math. 5 (1934), 15–17.

2. Gilbert Baumslag, Wreath products and finitely presented groups, Math. Z. 75 (1961), 22–28. MR 0120269 (22 #11026)

3. W. W. Boone, The word problem, Ann. of Math. 70 (1959), 207–265. MR 0179237 (31 #3485)

4. Roger W. Carter, Simple groups of Lie type, Wiley Classics Library Edition, John Wiley & Sons, 1972. MR 0407163 (53 #10946)

5. C. G. Chehata, An algebraically simple ordered group, Proc. London Math. Soc. (3) 2 (1952), 183–197. MR 0047031 (13,817b)

6. Pierre de la Harpe, Topics in geometric group theory, Chicago Lectures in Mathematics, The University of Chicago Press, 2000. MR 1786869 (2001i:20081)

7. John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, no. 163, Springer, 1996. MR 1409812 (98m:20003)

8. The GAP Group, GAP – Groups, Algorithms, and Programming; Version 4.4.10, 2007, http://www.gapsystem.org.

9. Graham Higman, Finitely presented infinite simple groups, Notes on Pure Mathematics, Department of Pure Mathematics, Australian National University, Canberra, 1974. MR 0376874 (51 #13049)

10. Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall / CRC, Boca Raton, FL, 2005. MR 2129747 (2006f:20001)

11. Otto H. Kegel and Bertram A. F. Wehrfritz, Locally finite groups, North-Holland Publishing Company, 1973. MR 0470081 (57 #9848)

12. Timothy P. Keller, Finite cycles of certain periodically linear permutations, Missouri J. Math. Sci. 11 (1999), no. 3, 152–157. MR 1717767

13. Stefan Kohl, Restklassenweise affine Gruppen, Dissertation, Universität Stuttgart, 2005, published at http://deposit.d-nb.de/cgi-bin/dokserv?idn=977164071.

14. , RCWA - Residue-Class-Wise Affine Groups; Version 2.5.4, 2007, GAP package, published at http://www.gap-system.org/Packages/rcwa.html.

15. , Wildness of iteration of certain residue-class-wise affine mappings, Adv. in Appl. Math. 39 (2007), no. 3, 322–328. MR 2352043

16. , Algorithms for a class of infinite permutation groups, J. Symb. Comp. 43 (2008), no. 8, 545–581. MR 2415857

17. Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer, 1977, Reprinted in the Springer Classics in Mathematics Series, 2000. MR 1812024 (2001i:20064)

18. K. A. Mihailova, The occurrence problem for direct products of groups. (Russian), Mat. Sb. 70 (1966), no. 112, 241–251. MR 0194497 (33 #2707)

19. P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory. (Russian), Trudy Math. Inst. Steklov 44 (1955), 143. MR 0075197 (17,706b)

20. Alexander Yu. Ol’shanskii, Infinite groups with cyclic subgroups. (Russian), Dokl. Akad. Nauk. SSSR 245 (1979), no. 4, 785–787. MR 527709 (80i:20013)

21. Melanie Stein, Groups of piecewise linear homoeomorphisms, Trans. Amer. Math. Soc. 332 (1992), no. 2, 477–514. MR 1094555 (92k:20075)

22. Günther J. Wirsching, The dynamical system on the natural numbers generated by the 3n+1 function, Habilitationsschrift, Katholische Universität Eichstätt, 1996.

Universiteti “Ismail Qemali” Vlore, Lagja: Pavaresia, Vlore / Albania

E-mail address: kohl@univlora.edu.al