SIMPLE GROUPS GENERATED BY INVOLUTIONS INTERCHANGING RESIDUE CLASSES MODULO LATTICES IN ℤ^{d}

STEFAN KOHL

Abstract. We present a series of countable simple groups generated by involutions interchanging disjoint residue classes modulo lattices in ℤ^{d} (d ∈ ℕ).

1. Introduction

In this paper we generalize the construction of the simple group CT(ℤ) < Sym(ℤ) investigated in [1] to groups CT(ℤ^{d}) acting on ℤ^{d} (d ∈ ℕ).

Definition 1.1. Let d ∈ ℕ, and let L_{1}, L_{2} ∈ ℤ^{d×d} be matrices of full rank which are in Hermite normal form. Further let r_{1} +ℤ^{d}L_{1} and r_{2} +ℤ^{d}L_{2} be disjoint residue classes, and assume that the representatives r_{1} and r_{2} are reduced modulo ℤ^{d}L_{1} and ℤ^{d}L_{2}, respectively. Then we define the class transposition τ_{r_{1}+ℤ^{d}L_{1},r_{2}+ℤ^{d}L_{2}} ∈ Sym(ℤ^{d}) as the involution which interchanges r_{1} + kL_{1} and r_{2} + kL_{2} for all k ∈ ℤ^{d} and which fixes everything else.

Definition 1.2. Let CT(ℤ^{d}) denote the group which is generated by the set of all class transpositions of ℤ^{d}.

The purpose of this article is to prove the following generalization of Theorem 3.4 in [1]:

Theorem 1.3. The groups CT(ℤ^{d}) are simple.

The work which led to the discovery of the simple group CT(ℤ) was originally motivated by Lothar Collatz’ 3n+1 conjecture, which dates back to the 1930’s. This conjecture asserts that iterated application of the so-called Collatz mapping

T : ℤ ⟶ ℤ, n ⟼ \begin{cases}n/2 & if n is even, \\ (3n + 1)/2 & if n is odd \end{cases}

to any positive integer yields 1 after a finite number of steps. The 3n + 1 conjecture is still open today. Lagarias [3] has compiled a comprehensive annotated bibliography, which lists hundreds of publications related to this conjecture. A survey article and a monograph on Collatz’ conjecture are [2] and [4], respectively.

The elements of the group CT(ℤ) are bijective mappings which are ‘similar to T ’ in the sense that they are affine on residue classes as well. If one investigates the group CT(ℤ) by means of theory or by means of computation, it turns out that its subgroups and its elements can often be handled much more easily than T. So it seems conceivable that part of the problem is that Collatz’ mapping T is not injective.

2000 Mathematics Subject Classification. Primary 20E32, secondary 20B22.

However, a key observation is now that the mapping T can be extended in natural ways to permutations of ℤ^{2}. An example of such an extension is

σ_{T} ∈ Sym(ℤ^{2}) : (n, m) ⟼ \begin{cases}((3n + 1)/2, 2m + 1) & if n is odd, \\ (n/2, 2m) & if n ≡ 4 mod 6, \\ (n/2, m) & otherwise. \end{cases}

The permutation σ_{T} acts on the first coordinate like the Collatz mapping T. This motivates a move from ℤ to ℤ^{2}, and generalizing further, to ℤ^{d} for d ∈ ℕ.

2. Basic Terms

In order to prove the simplicity of CT(ℤ^{d}), we need to introduce some terms:

Definition 2.1. Let d ∈ ℕ. We call a mapping f : ℤ^{d} → ℤ^{d} residue-class-wise affine if there is a lattice L = ℤ^{d}M where M ∈ ℤ^{d×d} is a matrix of full rank, such that the restrictions of f to the residue classes r + L ∈ ℤ^{d}/L are all affine. This means that for any residue class r + L ∈ ℤ^{d}/L, there is a matrix A_{r+L} ∈ ℤ^{d×d}, a vector b_{r+L} ∈ ℤ^{d} and a positive integer c_{r+L} such that the restriction of f to r + L is given by

f|_{r+L} : r + L ⟶ ℤ^{d}, v ⟼ \frac{v · A_{r+L} + b_{r+L}}{c_{r+L}} .

For reasons of uniqueness, we assume that L is chosen maximal with respect to inclusion, and that no prime factor of c_{r+L} divides all coefficients of A_{r+L} and b_{r+L}. We call the lattice L the modulus of f, written Mod(f). Further we define the prime set of f as the set of all primes which divide the determinant of at least one of the coefficients A_{r+L} or which divide the determinant of M, and we call the mapping f class-wise translating if all coefficients A_{r+L} are identity matrices and all coefficients c_{r+L} are equal to 1.

For the sake of simplicity, we identify a lattice L with the Hermite normal form of the matrix by whose rows it is spanned, and denote the i-th row of the spanning matrix by L_{(i)}.

It is easy to see that the residue-class-wise affine permutations of ℤ^{d} form a countable supergroup of CT(ℤ^{d}).

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

A more or less immediate observation is the following:

Theorem 2.3. The groups CT(ℤ^{d}) and RCWA(ℤ^{d}) are not finitely generated.

Proof. It is easy to see that the prime set of a product of residue-class-wise affine permutations is a subset of the union of the prime sets of the factors, and that inversion leaves the prime set invariant. Therefore as there are infinitely many primes and as for any prime p there is a class transposition τ_{(1,0,...,0)+ℤ^{d}·diag(2,1,...,1),(0,0,...,0)+ℤ^{d}·diag(2p,1,...,1)} whose prime set is {2, p}, the assertion follows. □

3. The Simplicity of CT(ℤ^{d})

In order to show that the groups CT(ℤ^{d}) are simple, we need some lemmata:

Lemma 3.1. Given any two class transpositions τ_{r_{1}+L_{1},r_{2}+L_{2}} and τ_{r_{3}+L_{3},r_{4}+L_{4}} whose support is not all of ℤ^{d}, there is always a product π of 6 class transpositions such that τ_{r_{1}+L_{1},r_{2}+L_{2}}^{π} = τ_{r_{3}+L_{3},r_{4}+L_{4}}.

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

(1) τ_{r_{1}+L_{1},r_{2}+L_{2}}τ^{r_{1}+L_{1},r_{5}+L_{5}} · τ^{r_{2}+L_{2},r_{6}+L_{6}} = τ_{r_{5}+L_{5},r_{6}+L_{6}},

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

The assertion follows. □

Lemma 3.2. Let σ, υ ∈ RCWA(ℤ^{d}), and put L := Mod(σ). If the mapping υ is classwise translating and fixes all residue classes (mod L) setwise, then the commutator [σ, υ] is class-wise translating as well.

Proof. Since υ fixes all residue classes (mod L), an affine partial mapping α of [σ, υ] is given by α_{υ^{−1}}^{α_{σ}} · α_{υ} for certain affine partial mappings α_{σ}, α_{υ} and α_{υ^{−1}} of σ, υ and υ^{−1}, respectively. The assertion follows, since the translations form a normal subgroup of the affine group of ℚ^{d}. □

Lemma 3.3. Let G be a subgroup of RCWA(ℤ^{d}) which contains CT(ℤ^{d}). Then any nontrivial normal subgroup N ⊴ G has a class-wise translating element ι ≠ 1.

Proof. Let σ ∈ N \{1}, and put L := Mod(σ). Without loss of generality, we can assume that σ is not class-wise translating. We pick a residue class r + L such that σ|_{r+L} is not a translation. By Lemma 3.2, the mappings ι_{i,j,k} := [σ, τ_{r+iL_{(j)}+2kL,r+(i+k)L_{(j)}+2kL}] ∈ N (k ∈ ℕ, i ∈ {0, …, k − 1}, j ∈ {1, …, d}) are class-wise translating. Choose k sufficiently large; then σ does not map all residue classes r + iL_{(j)} + kL to themselves. Therefore not all ι_{i,j,k} are equal to 1. □

Now we can prove our theorem:

Theorem 3.4. The groups CT(ℤ^{d}) are simple.

Proof. Let d ∈ ℕ, and let N be a nontrivial normal subgroup of CT(ℤ^{d}). We have to show that N contains all class transpositions.

By Lemma 3.1, all class transpositions whose support is not all of ℤ^{d} are conjugate in CT(ℤ^{d}). Further, any class transposition can be written as a product of two class transpositions with disjoint supports: putting D := diag(1, …, 1, 2), we have τ_{r_{1}+L_{1},r_{2}+L_{2}} = τ_{r_{1}+DL_{1},r_{2}+DL_{2}} · τ_{r_{1}+(L_{1})_{(d)}+DL_{1},r_{2}+(L_{2})_{(d)}+DL_{2}}. Therefore it is already sufficient to show that N contains one class transposition whose support is a proper subset of ℤ^{d}.

By Lemma 3.3, the normal subgroup N has a class-wise translating element ι_{1} ≠ 1. Let L be a sublattice of the modulus of ι_{1} such that |ℤ/L| ⩾ 3, and choose a residue class r + L which is moved by ι_{1}. Then put L̃ := DL and

ι_{2} := τ_{r+L̃,r+L_{(d)}+L̃} · τ_{(r+L̃)^{ι_{1}} ,(r+L_{(d)}+L̃)^{ι_{1}}} = [τ_{r+L̃,r+L_{(d)}+L̃}, ι_{1}] ∈ N.

By the choice of L, we can now choose two distinct residue classes r_{1} + L̃ and r_{2} + L̃ in the complement of the support of ι_{2}. Putting L̂ := D^{2}L, we have now

τ_{r_{1}+L̃,r_{2}+L̃} = ι_{2}^{τ_{r+L̃,r_{1}+L̂}·τ_{r+L_{(d)}+L̃,r_{2}+L̂}}
· ι_{2}^{τ_{r+L̃,r_{1}+2L_{(d)}+L̂}·τ_{r+L_{(d)}+L̃,r_{2}+2L_{(d)}+L̂}} ∈ N,

which completes the proof of the theorem. □

There is a straightforward generalization of Definition 3.6 and Corollary 3.7 in [1]:

Definition 3.5. Given a set ℙ of odd primes, let CT_{ℙ}(ℤ^{d}) ⩽ CT(ℤ^{d}) denote the subgroup which is generated by all class transpositions whose prime sets are subsets of ℙ ∪ {2}.

Corollary 3.6. The groups CT_{ℙ}(ℤ^{d}) are simple.

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

4. Open Questions

It is not clear whether (CT(ℤ^{d}))_{d∈ℕ} is indeed a series of pairwise non-isomorphic groups. Furthermore, so far there is no answer to the following question:

Question 4.1. Are the groups CT(ℤ^{d}) all isomorphic to CT(ℤ)?

Also, so far there is no explicit characterization of the elements of CT(ℤ^{d}):

Question 4.2. How can it be decided whether a given element σ ∈ RCWA(ℤ^{d}) lies in the group CT(ℤ^{d})?

References

1. Stefan Kohl, 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. MR 2593301

2. Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly 92 (1985), 3–23. MR 777565 (86i:11043)

3. , The 3x+1 problem: An annotated bibliography, 2003+, http://arxiv.org/abs/math.NT/0309224 (part I), http://arxiv.org/abs/math.NT/0608208 (part II).

4. Günther J. Wirsching, The dynamical system generated by the 3n+1 function, Lecture Notes in Mathematics, no. 1681, Springer-Verlag, 1998.

   E-mail address: stefan@mcs.st-and.ac.uk