Wildness of Iteration of Certain Residue-Class-Wise Affine Mappings

Stefan Kohl ^{∗}

Abstract

A mapping f : ℤ → ℤ is called residue-class-wise affine if there is a positive integer m such that f is affine on residue classes (mod m). The smallest such m is called the modulus of f. In this article it is shown that if the mapping f is surjective but not injective, then the set of moduli of its powers is not bounded. Further it is shown by giving examples that the three other combinations of (non-) surjectivity and (non-) injectivity do not permit a conclusion on whether the set of moduli of powers of a mapping is bounded or not.

Keywords: 3n + 1 Conjecture, residue-class-wise affine mapping, wildness criterion, Furstenberg topology.

MSC 2000: Primary 11B99, Secondary 54H99

1 Introduction

The following conjecture has been made by Lothar Collatz in the 1930s:

1.1 3n+1 Conjecture Iterated application of the mapping

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

to any positive integer yields 1 after a finite number of steps. In short this means that for all n ∈ ℕ, there exists k ∈ ℕ_{0} such that T^{(k)}(n) = 1.

This conjecture is still open today. See [7] for a survey article and [8] for an annotated bibliography.

∗Institut für Geometrie und Topologie, Pfaffenwaldring 57, Universität Stuttgart, 70550 Stuttgart / Germany. E-mail: kohl@mathematik.uni-stuttgart.de

Together with the fact that there is no k ∈ ℕ such that T^{(k)} maps all positive integers to smaller ones, a reason for the difficulty of this problem is that there is no upper bound on the number of different affine partial mappings of powers T^{(k)} of the Collatz mapping T.

The mapping T is surjective, but not injective. We ask whether in fact all surjective, but not injective mappings which are ‘similar to T ’ share the last-mentioned property. Further we ask how the situation looks like for the three other combinations of (non-) surjectivity and (non-) injectivity.

1.2 Definition 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. This means that for any residue class r(m) there are coefficients a_{r(m)}, b_{r(m)}, c_{r(m)} ∈ ℤ such that the restriction of the mapping f to the set r(m) = {r + km|k ∈ ℤ} is given by

f|_{r(m)} : r(m) → ℤ, n ↦ \frac{a_{r(m)} · n + b_{r(m)}}{c_{r(m)}} .

We call the smallest possible m the modulus of f, written Mod(f). To ensure uniqueness of the coefficients, 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 the least common multiple of the coefficients a_{r(m)}, and use the notation Mult(f). Similarly, we define the divisor of f by the least common multiple of the coefficients c_{r(m)}, and use the notation Div(f).

Now we can give a formal definition of the property mentioned above:

1.3 Definition Let f : ℤ → ℤ be a residue-class-wise affine mapping. We call f tame if the set {Mod(f^{(k)})|k ∈ ℕ} is bounded, and wild otherwise.

1.4 Examples For the Collatz mapping we have Mod(T) = 2, Mult(T) = 3 and Div(T) = 2. The Collatz mapping is surjective. However it is not injective – the preimage of n ∈ 2(3) under T is {2n, (2n − 1)/3}. For any k ∈ ℕ we have Mod(T^{(k)}) = 2^{k}. Therefore the mapping T is wild. Another mapping which is also surjective but not injective is

T_{1} : ℤ ⟶ ℤ, n ⟼ \begin{cases}\frac{n}{2} & if n even, \\ \frac{n+1}{2} & if n odd. \end{cases}

There we have Mod(T_{1}) = Div(T_{1}) = 2 and Mult(T_{1}) = 1, and the preimage of an integer n under T_{1} is {2n, 2n − 1}.

The main result of this article is that a residue-class-wise affine mapping which is surjective but not injective is always wild. Further it is shown by giving counterexamples that no such conclusion can be made if the mapping is either bijective or not surjective.

Surjectivity and injectivity are easily computable properties of residueclass-wise affine mappings. A couple of necessary and sufficient conditions can be found in [9]. Straightforward tests involve only computing images of residue classes under affine mappings, checking whether a given finite set of residue classes entirely covers the set of integers and checking whether two given residue classes intersect nontrivially (Chinese Remainder Theorem).

Detailed background on the subject is given in [6]. That thesis is mainly about residue-class-wise affine groups. These are permutation groups whose elements are bijective residue-class-wise affine mappings. However, apart from this also some further criteria are derived for deciding whether a given residue-class-wise affine mapping is tame or wild.

There is an article [11] by G. Venturini which certainly should be mentioned in this context. This article studies the iteration of residue-class-wise affine mappings. It is mainly concerned with classifying ergodic sets of such mappings which are unions of finitely many residue classes. It discusses a considerable number of examples.

Investigating residue-class-wise affine mappings and -groups by means of computation is feasible – see the package RCWA [5] for the computer algebra system GAP [2]. Both [6] and the manual of [5] discuss numerous examples.

2 Surjective and Non-Injective Means Wild

In the sequel it will be convenient to regard ℤ as a topological space with the following topology:

2.1 Definition The Furstenberg topology on ℤ (cf. [1], and see also [4] and [10]) is the topology which is induced by taking the set of residue classes (mod m) for all integers m ⩾ 1 as a basis.

We need a notion of density for open and closed subsets of ℤ:

2.2 Definition Given a residue class r(m) ⊆ ℤ, let μ(r(m)) := 1/m. Given a subset S ⊆ ℤ, let μ(ℤ \ S) := 1 − μ(S), and given two subsets S_{1}, S_{2} ⊆ ℤ let μ(S_{1} ∪ S_{2}) := μ(S_{1}) + μ(S_{2}) − μ(S_{1} ∩ S_{2}). We call μ(S) the natural density of S.

This notion of density complies in a natural way with the generally used definition of the natural density of a set of integers.

We need a basic lemma on the density of images and preimages of open sets under residue-class-wise affine mappings:

2.3 Lemma Let S ⊆ ℤ be an open set in the Furstenberg topology. Further let α ∈ Aff(ℚ) : n ↦ (an + b)/c, and let f be a residue-class-wise affine mapping. Then the following hold:

1. α(S) ⊆ ℤ ⟹ μ(α(S)) = μ(S) · |c/a|.

2. μ(f(S)) ⩽ μ(S) · Div(f).

Proof: By definition the set of residue classes is a basis of our topology on ℤ. Consequently there is a partition P of the open set S into residue classes.

1. This holds since provided that it is a subset of ℤ, the image of a residue class r(m) ∈ P under α is a residue class with modulus am/c.

2. This assertion follows from (1), applied to the affine partial mappings of f and the intersections of S with their sources. Images under constant mappings have natural density 0, thus can be ignored in this context. □

We need a term which denotes the sum of the densities of the images of the affine partial mappings of a residue-class-wise affine mapping:

2.4 Definition Let f be a residue-class-wise affine mapping, and let m be its modulus. Further assume that the restrictions of f to the residue classes r(m) ∈ ℤ/mℤ are given by n ↦ (a_{r(m)}n + b_{r(m)})/c_{r(m)}. Then we define the image density μ_{img}(f) of f by

μ_{img}(f) := ∑_{r(m)∈ℤ/mℤ}μ(f(r(m))).

If Mult(f) ≠ 0, as a consequence of Lemma 2.3, Assertion (1) we have μ_{img}(f) = ∑_{r(m)∈ℤ/mℤ} c_{r(m)}/(a_{r(m)} · m). From this we immediately read off that the image density of a residue-class-wise affine mapping with given multiplier and divisor can neither be arbitrary large nor arbitrary small, and that the denominator of the fraction is bounded as well:

2.5 Lemma Given a residue-class-wise affine mapping f with Mult(f) ≠ 0, it holds 1/ Mult(f) ⩽ μ_{img}(f) ⩽ Div(f) and Mod(f) · Mult(f) · μ_{img}(f) ∈ ℕ_{0}.

Stronger assertions hold under the assumption that the corresponding mapping is injective, surjective or even bijective:

2.6 Lemma Given a residue-class-wise affine mapping f, the following hold:

1. f is injective ⇒ μ_{img}(f) ⩽ 1.

2. f is surjective ⇒ μ_{img}(f) ⩾ 1.

3. f is bijective ⇒ μ_{img}(f) = 1.

In Assertion (1) and (2) equality holds for a mapping without constant affine partial mappings if and only if it is bijective.

Proof: The assertions follow from the additivity of the density function and from the setting μ(ℤ) := 1. □

We make use of the following property of non-injective residue-class-wise affine mappings:

2.7 Lemma Assume that f is a non-injective residue-class-wise affine mapping and that there is no residue class on which f is constant. Then there is a residue class r_{0}(m_{0}) and two disjoint residue classes r_{1}(m_{1}) and r_{2}(m_{2}) of ℤ such that r_{0}(m_{0}) = f(r_{1}(m_{1})) = f(r_{2}(m_{2})).

Proof: Let m be the modulus of f. Since f is not injective, there are two residue classes r̃_{1}(m) and r̃_{2}(m) whose images under f are not disjoint. Since we have required that f is not constant on any residue class, f(r̃_{1}(m)) and f(r̃_{2}(m)) are residue classes as well. Therefore r_{0}(m_{0}) := f(r̃_{1}(m))∩f(r̃_{2}(m)) is also a residue class. The preimages r_{1}(m_{1}) and r_{2}(m_{2}) of r_{0}(m_{0}) under the affine mappings f|_{r̃_{1}(m)} resp. f|_{r̃_{2}(m)} are residue classes, too. They are disjoint since they are subsets of distinct residue classes (mod m). □

Multiplying by a surjective, but not injective mapping increases the image density:

2.8 Lemma Let f and g be surjective residue-class-wise affine mappings without constant affine partial mappings, and assume that f is not injective. Then μ_{img}(f · g) > μ_{img}(g).

Proof: By Lemma 2.7, there are a residue class r_{0}(m_{0}) and two disjoint residue classes r_{1}(m_{1}) and r_{2}(m_{2}) such that f(r_{1}(m_{1})) = f(r_{2}(m_{2})) = r_{0}(m_{0}). Let m_{g} := Mod(g). Then the residue classes r_{0}(m_{g}) and r_{0}(m_{0}) intersect nontrivially. Let r_{0}(m) be their intersection. Due to the surjectivity of f we have μ_{img}(f ·g) ⩾ μ_{img}(g)+μ(g(r_{0}(m))) > μ_{img}(g), which had to be shown. □

Now we can prove the validity of our criterion:

2.9 Theorem Let f be a residue-class-wise affine mapping. If f is surjective but not injective, then f is wild.

Proof: Assume that f is tame. Let m := lcm_{k∈ℕ} Mod(f^{(k)}). Then the restrictions f^{(k)}|_{r(m)} (k ∈ ℕ) of powers of f to residue classes (mod m) are affine. The images of the residue classes r(m) under the mappings f^{(k)} are either single residue classes as well, or (caused by constant affine partial mappings) sets of cardinality 1. We have to distinguish two different cases:

1. The mapping f has a constant partial mapping f|_{r_{1}(m)} ≡ n. In this case, due to the surjectivity of the mapping f and the choice of m there is an infinite sequence r_{2}(m), r_{3}(m), r_{4}(m), … of pairwise distinct residue classes (mod m) such that ∀k ∈ ℕ f^{(k)}|_{r_{k}(m)} ≡ n. Since there are only finitely many residue classes (mod m), this yields a contradiction.

2. The mapping f does not have a constant partial mapping. In this case, we know from Lemma 2.8 that ∀k ∈ ℕ μ_{img}(f^{(k+1)}) > μ_{img}(f^{(k)}). By Lemma 2.5, Div(f^{(k)}) is an upper bound on μ_{img}(f^{(k)}). Since the divisor of a residue-class-wise affine mapping divides its modulus, we have Div(f^{(k)}) ⩽ m. Using the ‘denominator bound’ from Lemma 2.5, we conclude that the sequence (Mult(f^{(k)}))_{k∈ℕ} is not bounded.

Let d := m + 2. We can choose k_{0} ∈ ℕ and r_{1}(m) ∈ ℤ/mℤ such that μ(f^{(k_{0})}(r_{1}(m))) < 1/m^{d}. By choice of m, the set f^{(k_{0})}(r_{1}(m)) =: r_{0}(m̃) is a residue class as well. Since the divisor of a residue-class-wise affine mapping divides its modulus, we can conclude from Lemma 2.3, Assertion (2) that ∀k ∈ ℕ μ(f^{(k)}(r_{0}(m̃))) < 1/m^{d−1}. Using the method described below, we show that there is an exponent e ∈ ℕ such that for any k ∈ ℕ and any r(m) ∈ ℤ/mℤ the equation

μ(f^{(e+k)}(r(m))) < \frac{1}{m}  (1)

holds:

1. Put i := 2.

2. Since the mapping f^{(k_{0})} is surjective, there is an r_{i}(m) ∈ ℤ/mℤ such that μ(f^{(k_{0})}(r_{i}(m)) ∩ r_{i−1}(m)) ⩾ 1/m^{2}. According to the choice of m, for any k ∈ ℕ_{0} the mappings f^{((i−1)k_{0}+k)}|_{f^{(k_{0})}(r_{i}(m))} and f^{((i−1)k_{0}+k)}|_{r_{i−1}(m)} are affine and differ at most by their sources. Hence using this inequality one can conclude inductively that

μ(f^{(ik_{0})}(r_{i}(m))) ⩽ m^{i−1} · μ(f^{(k_{0})}(r_{1}(m))) < 1/m^{d−(i−1)}

and that μ(f^{(ik_{0}+k)}(r_{i}(m))) < 1/m^{d−i}. Thus in particular for i ⩽ m no image of f^{(ik_{0})}(r_{i}(m)) under a power of f can have an intersection of density ⩾ 1/m^{2} with any residue class rĩ(m).

3. If i < m, put i := i + 1 and continue with step (2), otherwise done.

Due to the last sentence of the description of step (2), the m residue classes r_{i}(m) ∈ ℤ/mℤ which we get this way are pairwise distinct. Hence Inequality (1) holds for e := m · k_{0}. This is a contradiction to the assumption that f is surjective. □

Three of the four possible combinations of (non-) injectivity and (non-) surjectivity do not permit a conclusion on whether the respective residue-class-wise affine mapping is tame or wild:

tame  wild

not injective,

not surjective n ↦ \begin{cases}2n & if n ∈ 0(2), \\ 2n + 2 & if n ∈ 1(2). \end{cases} n ↦ \begin{cases}\frac{3n}{2} & if n ∈ 0(2), \\ 2n + 2 & if n ∈ 1(2). \end{cases}

injective, not surjective

n ↦ 2n.

n ↦ \begin{cases}\frac{3n}{2} & if n ∈ 0(2), \\ 3n + 2 & if n ∈ 1(2). \end{cases}

not injective, surjective Does not exist,

by Theorem 2.9. n ↦ \begin{cases}\frac{n}{2} & if n ∈ 0(2), \\ \frac{3n+1}{2} & if n ∈ 1(2) \end{cases}

(cf. Conjecture 1.1).

bijective

n ↦ n + 1.

n ↦ \begin{cases}\frac{2n}{3} & if n ∈ 0(3), \\ \frac{4n−1}{3} & if n ∈ 1(3), \\ \frac{4n+1}{3} & if n ∈ 2(3) \end{cases}

(cf. [3], [7], [12]).

References

[1] H. Furstenberg. On the infinitude of primes. Amer. Math. Monthly, 62:353, 1955.

[2] The GAP Group. GAP – Groups, Algorithms, and Programming; Ver-

sion 4.4.7, 2006. (http://www.gap-system.org).

[3] T. P. Keller. Finite cycles of certain periodically linear permutations. Missouri J. Math. Sci., 11(3):152–157, 1999.

[4] J. Knopfmacher and S. Porubsky. Topologies related to arithmetical properties of integral domains. Exposition. Math., 15(2):131–148, 1997.

[5] S. Kohl. RCWA - Residue Class-Wise Affine Groups, 2005. GAP pack-

age (http://www.gap-system.org/Packages/rcwa.html).

[6] S. Kohl. Restklassenweise affine Gruppen. Dissertation, Universität Stuttgart, 2005.

[7] J. C. Lagarias. The 3x+1 problem and its generalizations. Amer. Math. Monthly, 92:1–23, 1985.

[8] J. C. Lagarias. The 3x+1 problem: An annotated bibliography, 2006.

(http://arxiv.org/abs/math.NT/0309224).

[9] D. Levy. Injectivity and surjectivity of Collatz functions. Discrete Math., 285:190–199, 2004.

[10] S. Porubsky. Arithmetically related ideal topologies and the infinitude of primes. Quaest. Math., 24(3):373–391, 2001.

[11] G. Venturini. Iterates of number-theoretic functions with periodic rational coefficients (generalization of the 3x+1 problem). Stud. Appl. Math., 86(3):185–218, 1992.

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