A REFORMULATION OF THE 3N+1 CONJECTURE IN TERMS OF A MAPPING FROM THE FREE MONOID OF RANK 2 TO THE POSITIVE INTEGERS

STEFAN KOHL

Abstract. The 3n+1 Conjecture asserts that iterated application of the Collatz mapping T : ℤ → ℤ, n ↦ (n/2 if n even, (3n + 1)/2 if n odd) to any positive integer yields 1 after a finite number of steps.

We construct a mapping from the free monoid of rank 2 to the set of positive integers, which is bijective if and only if the 3n + 1 Conjecture holds. We also rewrite the 3n + 1 Conjecture as a conjugacy problem for transformation monoids.

1. Introduction

In the 1930s, Lothar Collatz made the following conjecture which is still open today:

Conjecture 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.

For a survey article on this conjecture, we refer to [2].

As formulating a problem in a different way often helps in finding a solution, the 3n+1 Conjecture has already been reformulated in a large number of ways. For details, see Lagarias’ 3n + 1 problem annotated bibliography [3] and the publications indexed there.

In this article we construct a mapping from the free monoid of rank 2 to the set of positive integers, which is bijective if and only if the 3n + 1 Conjecture holds. We also rewrite the 3n + 1 Conjecture as a conjugacy problem for transformation monoids.

2. The 3n+1 Tree

Obviously, the 3n + 1 Conjecture is equivalent to the assertion that for any n ∈ ℕ there is a k ∈ ℕ_{0} such that n lies in the preimage of 1 under T^{(k)}. This motivates the following definition:

Definition 2.1. Let T_{0} be the tree with root 8 in which the left child of a vertex n is 2n, and in which the right child of a vertex n ≡ 2 mod 3 is (2n − 1)/3. We call this infinite rooted tree the 3n + 1 tree.

In this notation, we ask whether all positive integers except of 1, 2 and 4 are vertices of T_{0}. The reason for not taking 1 as the root of T_{0} is that due to the cycle (1 2) of the Collatz mapping, T_{0} would not be cycle-free otherwise.

2000 Mathematics Subject Classification. Primary 11B99.

3. Turning the 3n+1 Tree Into a Complete Binary Tree

The automorphism group of the 3n + 1 tree is trivial. This holds since there is no vertex whose left and right subtree are isomorphic. Investigating more symmetric trees is usually easier. The most symmetric trees are the ones in which any vertex has the same number c of child vertices. For the sake of minimality, we choose c = 2 and try to turn the 3n + 1 tree into a complete infinite binary tree.

For this purpose we cut away all vertices which either have no right child or whose right subtree is degenerate. This means that precisely the vertices remain that lie in the set (2(9) ∪ 8(9)) ∩ ℕ. Since any trajectory of the Collatz mapping contains a number not divisible by 3 and since we have

1(3) ∪ 2(3) = ⋃_{k=0}^{3} T^{(k)}(2(9) ∪ 8(9)),

the 3n + 1 Conjecture is equivalent to the assertion that the vertices of the resulting tree T_{1} are precisely the numbers n ∈ (2(9) ∪ 8(9)) ∩ ℕ \ {2}.

Elementary calculations show that starting from some vertex n of T_{1}, following the left respectively right branch means applying the injective mappings

l : n ↦ \begin{cases}4n & if n ∈ 2(9), \\ 16n & if n ∈ 8(9), \\ n & otherwise, \end{cases} or r : n ↦ \begin{cases}\frac{2n−1}{3} & if n ∈ 17(27) ∪ 26(27), \\ \frac{4n−2}{3} & if n ∈ 2(27) ∪ 20(27), \\ \frac{8n−4}{3} & if n ∈ 8(27), \\ \frac{16n−8}{3} & if n ∈ 11(27), \\ n & otherwise, \end{cases}

respectively. Although our tree has only positive integers n ∈ 2(9) ∪ 8(9) as vertices, we take ℤ as the source of our mappings – this makes the notation easier, and does not cause any harm. The images of 2(9) ∪ 8(9) under l and r are 8(36) ∪ 128(144) and 11(18)∪17(18)∪2(36)∪26(36)∪20(72)∪56(144), respectively, thus form a partition of 2(9) ∪ 8(9). Hence there is a mapping d such that ld = rd = 1. This mapping is given by

d : n ↦ \begin{cases}\frac{n}{4} & if n ∈ 8(36), \\ \frac{n}{16} & if n ∈ 128(144), \\ \frac{3n+1}{2} & if n ∈ 11(18) ∪ 17(18), \\ \frac{3n+2}{4} & if n ∈ 2(36) ∪ 26(36), \\ \frac{3n+4}{8} & if n ∈ 20(72), \\ \frac{3n+8}{16} & if n ∈ 56(144), \\ n & if n ∈ ℤ \ (2(9) ∪ 8(9)). \end{cases}

Applying d to a vertex means going down one level in the tree.

It is not nice that the vertices of our tree T_{1} are all in 2(9) ∪ 8(9). It would be much nicer to reformulate the problem in such a way that the question is whether a given tree with root 1 has any positive integer as a vertex.

We can do this as follows: First we choose an injective mapping f whose image is 2(9) ∪ 8(9), which maps 1 to 8 and which does not map positive integers to negative ones or vice versa:

f : n ↦ \begin{cases}\frac{9n+4}{2} & if n ∈ 0(2), \\ \frac{9n+7}{2} & if n ∈ 1(2). \end{cases}

Then we determine the unique mappings L, R and D such that fl = Lf, fr = Rf and fd = Df, that L and R are injective and that we have LD = RD = 1. Straightforward calculations with the GAP [4] package RCWA [1] yield

L : n ↦ \begin{cases}4n + 1 & if n ∈ 0(2), \\ 16n + 12 & if n ∈ 1(2), \end{cases}

R : n ↦ \begin{cases}\frac{4n}{3} & if n ∈ 0(6), \\ \frac{8n+4}{3} & if n ∈ 1(6), \\ \frac{16n+4}{3} & if n ∈ 2(6), \\ \frac{2n}{3} & if n ∈ 3(6), \\ \frac{4n−1}{3} & if n ∈ 4(6), \\ \frac{2n−1}{3} & if n ∈ 5(6), and \end{cases}

D : n ↦ \begin{cases}\frac{n−1}{4} & if n ∈ 1(8), \\ \frac{n−12}{16} & if n ∈ 28(32), \\ \frac{3n}{4} & if n ∈ 0(8), \\ \frac{3n−4}{8} & if n ∈ 4(16), \\ \frac{3n−4}{16} & if n ∈ 12(32), \\ \frac{3n}{2} & if n ∈ 2(4), \\ \frac{3n+1}{4} & if n ∈ 5(8), \\ \frac{3n+1}{2} & if n ∈ 3(4). \end{cases}

The images of L and R are 1(8) ∪ 28(32) and ℤ \ (1(8) ∪ 28(32)), respectively. Hence they form a partition of ℤ. Let T_{2} be the complete infinite binary tree with root 1 and in which the left or right child of a vertex n is L(n) or R(n), respectively. It is easy to see that this tree has the desired properties.

4. The 3n+1 Conjecture as an Assertion on a Monoid

In the last section, we have transformed the 3n + 1 Conjecture into the assertion that all positive integers occur as vertices of a certain tree T_{2}. We can also rewrite it in terms of the following monoid:

Definition 4.1. Let C be the free monoid of rank 2 which is generated by the restrictions of the mappings L and R introduced in Section 3 to the positive integers.

Theorem 4.2. The 3n + 1 Conjecture is equivalent to the assertion that the mapping

γ : C → ℕ, c ↦ c(1)

is bijective.

Remark 4.3. It is obvious that the mapping γ in Theorem 4.2 is injective. The problem is to show that it is surjective as well.

It is also easy to see that we can rewrite the 3n + 1 Conjecture in the following way as a conjugacy problem for monoids:

Theorem 4.4. The 3n + 1 Conjecture is equivalent to the assertion that the monoids C and C_{0} := ⟨n ↦ 2n, n ↦ 2n + 1⟩ are conjugate in the full symmetric group Sym(ℕ).

References

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

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

3. , The 3x+1 problem: An annotated bibliography, 2006, http://arxiv.org/abs/math.NT/0309224.

4. The GAP Group, GAP – Groups, Algorithms, and Programming; Version 4.4.9, 2006, 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