January 16, 2008 10:54 WSPC/INSTRUCTION FILE monoconj

ON CONJUGATES OF COLLATZ-TYPE MAPPINGS

STEFAN KOHL Institut für Geometrie und Topologie Pfaffenwaldring 57 Universität Stuttgart 70550 Stuttgart Germany kohl@mathematik.uni-stuttgart.de

Received 18 July 2006 Accepted 3 November 2006

Communicated by

A mapping f : ℤ → ℤ is called residue-class-wise affine if there is a positive integer m such that it is affine on residue classes (mod m). If there is a finite set S ⊂ ℤ which intersects nontrivially with any trajectory of f, then f is called almost contracting. Assume that f is a surjective but not injective residue-class-wise affine mapping, and that the preimage of any integer under f is finite. Then f is almost contracting if and only if there is a permutation σ of ℤ such that f^{σ} = σ^{−1} ∘ f ∘ σ is either monotonically increasing or monotonically decreasing almost everywhere. In this article it is shown that if there is no positive integer k such that applying f^{(k)} decreases the absolute value of almost all integers, then σ cannot be residue-class-wise affine itself. The original motivation for the investigations in this article comes from the famous 3n + 1 Conjecture.

Keywords: 3n+1 Conjecture; Collatz Conjecture; residue-class-wise affine mapping; conjugation.

Mathematics Subject Classification 2000: Primary 11B99, Secondary 20B99

1. Introduction

In the 1930s, Lothar Collatz made the following conjecture which is still open today (see [4] for a survey article and [5] for an annotated bibliography):

Conjecture 1.1 (3n+1 Conjecture) Iterated application of the mapping

T : ℤ ⟶ ℤ, n ⟼ \begin{cases}n/2 & if n even, \\ (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.

Obviously this conjecture holds if and only if there is a permutation σ of ℤ which maps positive integers to positive integers and fixes 1 such that T^{σ} = σ^{−1} ∘ T ∘ σ maps any integer n > 1 to a smaller one. Since T is surjective but not injective, this is essentially

2 Stefan Kohl

equivalent to requiring that T^{σ} is monotonically increasing almost everywhere (imagine the graph of a monotonically increasing conjugate!).

In this article, on the one hand we generalize the question for the existence of such a monotonically increasing conjugate to other mappings similar to the Collatz mapping T. On the other we specialize it to the case that the conjugating permutation σ itself is of a form similar to T, i.e. is residue-class-wise affine:

Definition 1.2 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 define the multiplier Mult(f) of f by lcm_{r(m)∈ℤ/mℤ} a_{r(m)} and the divisor Div(f) of f by lcm_{r(m)∈ℤ/mℤ} c_{r(m)}. We always assume that Mult(f) ≠ 0.

Definition 1.3 Let f : ℤ → ℤ be a mapping. We call f almost contracting if there is a finite set S ⊂ ℤ which intersects nontrivially with any trajectory of f.

Definition 1.4 Let f : ℤ → ℤ be a mapping. We call f monotonizable if there is a permutation σ ∈ Sym(ℤ) and a finite set S ⊂ ℤ such that f^{σ} is either monotonically increasing or monotonically decreasing on ℤ \ S. Further we call f rcwa-monotonizable if σ can be chosen to be residue-class-wise affine.

Remark 1.5 It is easy to see that surjective, but not injective monotonizable residue-class-wise affine mappings are also almost contracting, and that almost contracting such mappings are monotonizable.

Example 1.6 We look at the residue-class-wise affine mappings

f : n ↦ \begin{cases}(n + 1)/2 & if n ∈ 1(6), \\ (9n + 1)/2 & if n ∈ 3(6), \\ (9n + 11)/2 & if n ∈ 5(6), \\ (n − 2)/18 & if n ∈ 2(54), \\ (n + 8)/18 & if n ∈ 28(54), \\ n/2 & otherwise \end{cases} and σ : n ↦ \begin{cases}9n + 1 & if n ∈ 0(3), \\ (n − 1)/9 & if n ∈ 1(27), \\ n & otherwise. \end{cases}

The mapping f is surjective and rcwa-monotonizable. Indeed its conjugate under σ is f^{σ} : n ↦ ⌊(n + 1)/2⌋, which is monotonically increasing on ℤ. Therefore f is almost contracting. This is nontrivial, as there are trajectories like 21, 95, 433, 217, 109, 55, 28, … and 63, 284, 142, 71, 325, 163, 82, . . ..

On Conjugates of Collatz-Type Mappings 3

2. A Necessary Condition for rcwa-Monotonizability

In this article we derive a necessary condition for rcwa-monotonizability:

Theorem 2.1 Assume that f is a residue-class-wise affine mapping which is not injective, but is surjective and rcwa-monotonizable. Then there is a k ∈ ℕ such that there are at most finitely many n ∈ ℤ which satisfy |f^{(k)}(n)| ⩾ |n|.

In the proof we need the following lemmata:

Lemma 2.2 Assume that f is a non-injective residue-class-wise affine mapping. Then there are 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 := Mod(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. The images f(r̃_{1}(m)) and f(r̃_{2}(m)) are also residue classes. Thus their intersection r_{0}(m_{0}) is a residue class, too. The preimages r_{1}(m_{1}) and r_{2}(m_{2}) of r_{0}(m_{0}) under the affine mappings of f|_{r̃_{1}(m)} resp. f|_{r̃_{2}(m)} are residue classes as well. They are disjoint since they are subsets of distinct residue classes (mod m).

Lemma 2.3 Given a residue-class-wise affine mapping f, there is a constant c ∈ ℕ such that ∀n ∈ ℤ |f(n)| ⩽ Mult(f) · |n| + c.

Proof. Take upper bounds on the absolute values of the images of n under the affine partial mappings of f.

Proof of Theorem 2.1: By assumption, we can choose a residue-class-wise affine permutation σ and a finite set S ⊂ ℤ such that μ := f^{σ} is monotonically increasing or monotonically decreasing on ℤ \ S.

Surjectivity and non-injectivity are inherited from f to μ. Hence by Lemma 2.2 there is a residue class r(m) such that any n ∈ r(m) has at least two distinct preimages under μ.

From the surjectivity of μ, the monotonity of μ on ℤ \ S and the finiteness of S we can conclude that there is a constant c′ ∈ ℕ such that we have ∀n ∈ ℤ |μ(n)| < m/(m + 1) · |n| + c′, and induction over k ∈ ℕ yields

∀k ∈ ℕ ∀n ∈ ℤ |μ^{(k)}(n)| < (m/(m + 1))^{k} · |n| + k · c′.

For any k ∈ ℕ we have f^{(k)}(n) = σμ^{(k)}σ^{−1}(n). We choose k such that

(m/(m + 1))^{k} < 1/ (2 · Mult(σ) · Div(σ)) .

Since inversion interchanges multiplier and divisor, by Lemma 2.3 for some constant c depending on σ the following holds:

|f^{(k)}(n)| = |σμ^{(k)}σ^{−1}(n)| < Mult(σ) · (m/(m + 1))^{k} · |n| · Div(σ) + c < |n|/2 + c.

Since neither k nor c depends on n, this completes our proof. □

4 Stefan Kohl

Example 2.4 Let f be as in Example 1.6. Then Theorem 2.1 asserts that there is some k ∈ ℕ such that for almost all n ∈ ℤ we have |f^{(k)}(n)| < |n|. An easy computation with the GAP [1] package RCWA [2] shows indeed that k = 7 is the smallest value which satisfies this condition. Further one can check that the integers n ∉ {−1, 0, 1} which fail to satisfy the inequality |f^{(k)}(n)| < |n| for all k ⩽ 6 are the n ≡ 21, 63 or 105 (mod 192).

Theorem 2.1 has consequences for the 3n + 1 Conjecture:

Corollary 2.5 The Collatz mapping T is not rcwa-monotonizable.

Proof. The Collatz mapping T is surjective and not injective. Further, given n = 2^{k}m − 1 for some k, m ∈ ℕ we have T^{(k)}(n) = (3^{k}n + (3^{k} − 2^{k}))/2^{k} > n. Hence if there is a conjugate T^{σ} (σ ∈ Sym(ℤ)) which is monotonically increasing almost everywhere, then by Theorem 2.1, the permutation σ is not residue-class-wise affine.

Remark 2.6 Corollary 2.5 shows mainly that a ‘conjugating’ permutation which certifies that the Collatz mapping is almost contracting cannot be ‘very simple’. To the author it seems likely that it must be quite complicated.

The unboundedness of the moduli of powers of the Collatz mapping T is another reason for the difficulty of proving the 3n + 1 Conjecture. In [3], the author has shown that if a residue-class-wise affine mapping is surjective but not injective, then the set of moduli of its powers is never bounded.

References

[1] The GAP Group. GAP – Groups, Algorithms, and Programming; Version 4.4.9, 2006. http://www.gap-system.org.

[2] Stefan Kohl. RCWA - Residue-Class-Wise Affine Groups, 2005. GAP package, available at http://www.gap-system.org/Packages/rcwa.html.

[3] Stefan Kohl. Wildness of iteration of certain residue-class-wise affine mappings. Adv. in Appl. Math., 39(3):322–328, 2007.

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

[5] Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography, 2006. available at http://arxiv.org/abs/math.NT/0309224.