TWO INVARIANTS OF RESIDUE-CLASS-WISE AFFINE PERMUTATIONS OF THE INTEGERS

STEFAN KOHL

Abstract. A permutation of ℤ is called residue-class-wise affine if there is a positive integer m such that it is affine on residue classes (mod m). It is further called class-wise order-preserving if it is order-preserving on residue classes (mod m).

We determine two in some sense canonical epimorphisms π^{+} : RCWA^{+}(ℤ) → (ℤ, +) and π^{−} : RCWA(ℤ) → ℤ^{×}, where RCWA(ℤ) denotes the group consisting of all residue-class-wise affine permutations of ℤ, and RCWA^{+}(ℤ) denotes its subgroup formed by the class-wise order-preserving elements.

1. Introduction

The subject of this note are bijective mappings of the following type:

Definition 1.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 ↦ \frac{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 smallest 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 call f class-wise order-preserving if all a_{r(m)} are positive.

The permutations of this kind obviously form a countable subgroup of Sym(ℤ).

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

Further we denote the subgroup of RCWA(ℤ) which consists of all class-wise orderpreserving elements by RCWA^{+}(ℤ).

In this note, we prove the following:

Theorem 1.3. There are epimorphisms

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

and

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

where we use the notation for the coefficients introduced in Definition 1.1.

2000 Mathematics Subject Classification. Primary 20B22, Secondary 20B27, 20B40.

The relevance of these results is basically the following:

In [1] it is shown that the subgroups of the kernels of π^{+} resp. π^{−} which are generated by the torsion elements are simple. Further it is conjectured that these subgroups are improper, i.e. that the kernels are in fact equal to these simple groups.

For a general introduction to residue-class-wise affine groups, we refer to [2]. These groups are accessible to computational methods. In this context we refer to the package RCWA [3] for the computer algebra system GAP [4].

2. The Epimorphism π^{+}

In this section we construct our epimorphism π^{+} from RCWA^{+}(ℤ) to (ℤ, +).

Definition 2.1. Let r(m) be a residue class and let α : n ↦ (an + b)/c be an orderpreserving affine mapping with source r(m). Then we put π^{+}(α) := b/(am).

Further given σ ∈ RCWA^{+}(ℤ), we put π^{+}(σ) := ∑_{r(m)∈ℤ/mℤ} π^{+}(σ|_{r(m)}), where m denotes the modulus of σ.

It is easy to see that π^{+} is the mapping given in Theorem 1.3.

Evaluating the expression given there for an arbitrary residue-class-wise affine mapping usually does not yield an integer, unless the mapping is bijective and class-wise orderpreserving.

In the sequel it will turn out to be useful to consider residue classes with distinguished representatives:

Definition 2.2. We denote a residue class r(m) with distinguished representative r and signed modulus m by [r/m]. We define the image [r/m]^{α} of such a residue class under an affine mapping α by the residue class r(m)^{α} with distinguished representative r^{α} and modulus am/c. Let k ∈ ℕ. We call the decomposition

[r/m] = [r/(km)] ∪ [(r + m)/(km)] ∪ ⋯ ∪ [(r + (k − 1)m)/(km)]

of a residue class [r/m] representative-stabilizing and orientation-preserving.

Let P be a partition of ℤ into finitely many residue classes with distinguished representatives and signed moduli. Then we call a refinement of P representative-stabilizing and orientation-preserving if it is obtained by successive decomposition of residue classes in P in the above way.

We assign rational numbers to such residue classes:

Definition 2.3. Given a residue class [r/m], let δ ([r/m]) := r/m − 1/2. Given a partition P of ℤ into finitely many residue classes with distinguished representatives, let δ (P) := ∑_{[r/m]∈P} δ ([r/m]). Furthermore we define the value δ (ℤ) by δ (P) − ⌊δ (P)⌋.

We need to show that δ (ℤ) is well-defined:

Lemma 2.4. The value δ (ℤ) is independent of the choice of the partition P.

Proof. We need to show that δ (P) mod 1 is invariant under representative-stabilizing refinements of P and under changes of the representatives of the residue classes in P. Given a residue class [r/m] and k ∈ ℕ, we have

δ ([r/m]) = r/m − 1/2 = r/m + k(k − 1)/(2k) − k/2
= kr/(km) + (1 + ⋯ + (k − 1))/k − k/2
= ∑_{i=0}^{k−1}((r + im)/(km) − 1/2) = ∑_{i=0}^{k−1} δ ([(r + im)/(km)]).

It follows that δ (P) is invariant under representative-stabilizing refinement of the partition P. Furthermore, for a residue class [r/m] and k ∈ ℤ we have

δ ([r/m]) = r/m − 1/2 = (r + km)/m − 1/2 − k = δ ([(r + km)/m]) − k.

Hence changes of the choice of the distinguished representatives of the residue classes can change δ (P) only by an integer. □

Remark 2.5. It is δ (ℤ) = δ ([0/1]) = 0/1 − 1/2 − ⌊0/1 − 1/2⌋ = 1/2. However this value is not needed in the sequel.

Definition 2.6. Let σ ∈ RCWA(ℤ). We say that a partition P of ℤ into finitely many residue classes with distinguished representatives is a base for σ if all restrictions of σ to residue classes [r/m] ∈ P are affine.

Lemma 2.7. Let α : n ↦ (an+b)/c be an order-preserving affine mapping whose source is a residue class [r/m]. Then, δ ([r/m]^{α}) = δ ([r/m]) + π^{+}(α). Let σ ∈ RCWA^{+}(ℤ), and let P be a base for σ. Then, δ (P^{σ}) = δ (P) + π^{+}(σ).

Proof. We have δ ([r/m]^{α}) = δ ([((ar + b)/c)/(am/c)]) = r/m − 1/2 + b/(am) = δ ([r/m]) + π^{+}(α). The second assertion is now immediate. □

Now we have all necessary prerequisites needed for proving our first result:

Theorem 2.8. The mapping π^{+} : RCWA^{+}(ℤ) → (ℤ, +) is an epimorphism.

Proof. Let σ_{1}, σ_{2}, σ ∈ RCWA^{+}(ℤ). We have to show that π^{+}(σ) is an integer, that π^{+}(σ_{1}σ_{2}) = π^{+}(σ_{1}) + π^{+}(σ_{2}) and that 1 lies in the image of π^{+}.

(1) We show that π^{+}(σ) ∈ ℤ.

By Lemma 2.7 we have δ (ℤ) = δ (ℤ) + π^{+}(σ) − ⌊δ (ℤ) + π^{+}(σ)⌋. Thus π^{+}(σ) = ⌊δ (ℤ) + π^{+}(σ)⌋ ∈ ℤ.

(2) We show that π^{+}(σ_{1}σ_{2}) = π^{+}(σ_{1}) + π^{+}(σ_{2}).

Let m := Mod(σ_{1}) · Mod(σ_{2}), and P := {[0/m], [1/m], …, [(m − 1)/m]}. By construction, P is a base for σ_{1} and σ_{2}. Furthermore it is easy to see that it is a base for σ_{1}σ_{2} as well, and that P^{σ_{1}} is a base for σ_{2}. Hence by Lemma 2.7 we have

δ (P) + π^{+}(σ_{1}σ_{2}) = δ (P^{σ_{1}σ_{2}}) = δ (P^{σ_{1}}) + π^{+}(σ_{2})
= δ (P) + π^{+}(σ_{1}) + π^{+}(σ_{2}).

Subtracting δ (P) from the leftmost and the rightmost term reveals the claimed additivity of π^{+}.

(3) We have already shown that π^{+} is an homomorphism from RCWA^{+}(ℤ) to (ℤ, +). It is indeed an epimorphism, since n ↦ n + 1 lies in the preimage of 1. □

3. The Epimorphism π^{−}

In this section we construct our epimorphism π^{−} from RCWA(ℤ) to ℤ^{×}.

Definition 3.1. Let r(m) ⊆ ℤ be a residue class, and let α : n ↦ (an + b)/c be an affine mapping with source r(m). Further let exp : z ↦ e^{2πiz}. We put

π^{−}(α) := \begin{cases}exp (+b/(2am)) & if a > 0, \\ exp (−b/(2am) − r/m + 1/2) & if a < 0. \end{cases}

Further, given σ ∈ RCWA(ℤ) we put π^{−}(σ) := ∏_{r(m)∈ℤ/mℤ} π^{−}(σ|_{r(m)}), where m denotes the modulus of σ.

It is easy to see that π^{−} is the mapping given in Theorem 1.3.

We assign complex numbers with absolute value 1 to residue classes [r/m]:

Definition 3.2. Given a residue class [r/m] with signed modulus and distinguished representative, we set ϱ ([r/m]) := exp (sgn(m) · (r/m − 1/2)/2). Given a partition P of ℤ into a finite number of residue classes with signed moduli and distinguished representatives, we set ϱ (P) := ∏_{[r/m]∈P} ϱ ([r/m]) and ϱ (ℤ) := (−1)^{ϵ} · ϱ (P), where ϵ ∈ {0, 1} is chosen such that ϱ (ℤ) = exp (t) for some t ∈ [0, \frac{1}{2}[.

We have to show that ϱ (ℤ) is well-defined:

Lemma 3.3. Let P be a partition of ℤ into finitely many residue classes with signed moduli and distinguished representatives. Then the following hold:

(1) The value ϱ (P) is invariant under representative-stabilizing and orientation-pre-serving refinements of P.

(2) Changes of the distinguished representatives of the residue classes in P can only change the sign of ϱ (P).

(3) Changes of the signs of the moduli of the residue classes in P affect only the sign

of ϱ (P). In particular, the value ϱ (ℤ) does not depend on the choice of the partition P, i.e. is well-defined.

Proof. (1) For any residue class [r/m] with positive modulus m and any k ∈ ℕ the following holds:

ϱ ([r/m]) = exp ((r/m − 1/2)/2)
= exp ((r/m + k(k − 1)/(2k) − k/2)/2)
= exp ((kr/(km) + (1 + ⋯ + (k − 1))/k − k/2)/2)
= ∏_{i=0}^{k−1} exp (((r + im)/(km) − 1/2)/2)
= ∏_{i=0}^{k−1} ϱ ([(r + im)/(km)]).

In case m < 0 just the signs of all exponents are changed, thus ϱ (P) is invariant under representative-stabilizing and orientation-preserving refinements of P.

(2) For any m > 0 and any k ∈ ℤ, the following holds:

ϱ ([r/m]) = exp ((r/m − 1/2)/2)
= exp ((r + km)/(2m) − 1/4 − k/2)
= exp (((r + km)/m − 1/2)/2) · exp (−k/2)
= ϱ ([(r + km)/m]) · (−1)^{k}.

In case m < 0 just the signs of all exponents are changed, thus changing the distinguished representative of a residue class in P can at most change the sign of ϱ (P).

(3) Changing the sign of the modulus of a residue class [r/m] ∈ P changes the value of ϱ (P) by a factor of

\begin{matrix}ϱ & ([r/-m]) \\ ϱ & ([r/m]) \end{matrix} = \begin{matrix}exp & (−(r/-m − 1/2)/2) \\ exp & ((r/m − 1/2)/2) \end{matrix} = exp (1/2) = −1,

as claimed.

□

Remark 3.4. We can explicitly determine ϱ (ℤ): It is ϱ (ℤ) = exp (1/4) = i. However we will not need this value in the sequel.

Lemma 3.5. Let α be an affine mapping with source r(m). Then we have ϱ ([r/m]^{α}) = ϱ ([r/m]) · π^{−}(α).

Let σ ∈ RCWA(ℤ), and let P be a partition of ℤ into finitely many residue classes with distinguished representatives and signed moduli. Then we have ϱ (P^{σ}) = ϱ (P) · π^{−}(σ). Therefore for suitable ϵ ∈ {0, 1} it is ϱ (ℤ^{σ}) = (−1)^{ϵ} · ϱ (ℤ) · π^{−}(σ).

Proof. We assume that the mapping α is given by n ↦ (an + b)/c for certain coefficients a, b, c ∈ ℤ. First assume a > 0. Then we have

ϱ ([r/m]^{α}) = ϱ ([((ar + b)/c)/(am/c)])
= exp ((r/m + b/(am) − 1/2)/2)
= ϱ ([r/m]) · π^{−}(α).

Now assume a < 0. Then we have

ϱ ([r/m]^{α}) = ϱ ([((ar + b)/c)/(am/c)])
= exp (−((ar + b)/(am) − 1/2)/2)
= exp (−r/(2m) − b/(2am) + 1/4)
= exp ((r/m − 1/2)/2) · exp (−b/(2am) − r/m + 1/2)
= ϱ ([r/m]) · π^{−}(α),

thus our first assertion.

In order to get the corresponding assertion for a residue-class-wise affine mapping σ and a partition P, we simply refine P to a base for σ by successive representative-stabilizing and orientation-preserving decomposition of residue classes in P. Then we can apply the assertion proved above to the restrictions of σ to the residue classes in the refined partition. This way to proceed is correct due to Lemma 3.3. □

Now we can prove our second result:

Theorem 3.6. The mapping π^{−} is an epimorphism from RCWA(ℤ) to ℤ^{×}.

Proof. Let σ_{1}, σ_{2}, σ ∈ RCWA(ℤ). We have to show that π^{−}(σ) is a unit of ℤ, that π^{−}(σ_{1}σ_{2}) = π^{−}(σ_{1}) · π^{−}(σ_{2}) and that -1 lies in the image of π^{−}.

(1) We show that the sign of σ is a unit of ℤ. By Lemma 3.5, for suitable ϵ ∈ {0, 1} we have ϱ (ℤ) = ϱ (ℤ^{σ}) = (−1)^{ϵ} · ϱ (ℤ) · π^{−}(σ). Dividing the leftmost and the rightmost term by ϱ (ℤ) completes the proof.

(2) We show that π^{−}(σ_{1}σ_{2}) = π^{−}(σ_{1})·π^{−}(σ_{2}). Let P be a partition of ℤ into finitely many residue classes with signed moduli and distinguished representatives. By Lemma 3.5 we have

ϱ (P) · π^{−}(σ_{1}σ_{2}) = ϱ (P^{σ_{1}σ_{2}}) = ϱ (P^{σ_{1}}) · π^{−}(σ_{2})
= ϱ (P) · π^{−}(σ_{1}) · π^{−}(σ_{2}).

Dividing the leftmost and the rightmost term by ϱ (P) finishes the proof of our assertion.

(3) The images of n ↦ n + 1 and n ↦ −n under π^{−} are -1.

□

4. Acknowledgements

I thank Wolfgang Rump for the idea of introducing the invariant δ in the proof of Theorem 2.8.

References

1. Stefan Kohl, A simple group generated by involutions interchanging residue classes of the integers, Preprint, http://www.cip.mathematik.uni-stuttgart.de/ kohlsn/preprints/simplegp.pdf.

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

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

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

Institut für Geometrie und Topologie, Pfaffenwaldring 57, Universität Stuttgart 70550 Stuttgart, Germany

   E-mail address: kohl@mathematik.uni-stuttgart.de