A Chaotic Extension of the 3x + 1 Function to ℤ_{2}[i]

John A. Joseph

December 28, 1995

Abstract

We construct a non-trivial extension of the 3x + 1 function to the 2-adic integers adjoined with i (where i = \sqrt{−1}). We show that our extension is non-trivial in that not only is it not the cross product of the original function with itself, but it is not even conjugate to the cross product via a ℤ_{2}-module isomorphism (though they are topologically conjugate). We then prove that most of the interesting properties of the original function are preserved by the extension. Finally, we prove that the extension is chaotic.

1 Introduction

The 3x + 1 problem is most elegantly expressed in terms of iteration of the function T : ℤ^{+} → ℤ^{+} by

T (n) = \{ \begin{matrix}\frac{3n+1}{2} & if n is odd \\ \frac{n}{2} & if n is even. \end{matrix}

The conjecture attributed to Collatz [Lag] is that for every positive integer n, T^{(k)}(n) = 1 for some k.

The function T can be extended in a natural manner to the 2-adic integers, ℤ_{2}, and this extension has proven to be quite fruitful. In this paper, we further extend the domain of T to ℤ_{2}[i], hoping to increase our understanding of the problem.

2 Summary of Main Results

In this section we provide an overview of our main results. A more detailed discussion of the definitions, theorems, and proofs can be found in the remainder of the paper.

We construct an extension, T̃, of the 3x + 1 function, T : ℤ_{2} → ℤ_{2} to the metric space (ℤ_{2}[i], D).

Definition 1 Let T̃ : ℤ_{2}[i] → ℤ_{2}[i] by

T̃(α) = \{ \begin{matrix}\frac{α}{2} & if α ∈ [0] \\ \frac{3α+1}{2} & if α ∈ [1] \\ \frac{3α+i}{2} & if α ∈ [i] \\ \frac{3α+1+i}{2} & if α ∈ [1 + i] \end{matrix}

where [x] denotes the equivalence class of x in ℤ_{2}[i]/2ℤ_{2}[i].

Our main results separate naturally into roughly three areas.

First, T̃ is an extension of the original function and is non-trivial in the following sense:

Theorem A

(a) T̃|ℤ_{2} = T

(b) T̃ is not conjugate to T × T via a ℤ_{2}-module isomorphism.

(c) T̃ is, however, topologically conjugate to T × T.

Second, T̃ preserves the salient qualities of the original function. In particular there is a “parity vector function”, Q_{∞}, for T which has been extremely important in understanding the nature of the problem. We show that Q_{∞} can also be extended in an analogous manner. The original parity vector function and the extended parity vector function share several important properties (c.f. [Lag: Theorem B]). We simply state the results here, saving the details for later in the paper.

Theorem B The extended parity vector function Q̃_{k} is periodic with period 2^{k}. In addition, Q̃_{∞} is an isometric homeomorphism.

Finally, T and T × T are both chaotic functions (in the sense of [Dev]) and thus it follows from part (c) of Theorem A that

Theorem C T̃ is chaotic.

We have constructed T̃ in the hope that by applying the tools of chaos, complex analysis, and algebraic number theory the theorems presented above might provide future researchers with further insight into the 3x + 1 problem and others like it.

3 Background and Notation

In this section, we develop our notation and discuss the relevant background material. Jeffrey C. Lagarias has written an excellent exposition containing the history of the 3x+1 problem and a survey of the literature on the subject [Lag] and we use his notation whenever possible.

The sequence n, T (n), T^{(2)}(n), T^{(3)}(n), … is called the orbit of n under T. Another way to state the 3x+1 conjecture is that for all n ∈ ℤ^{+}, the orbit of n under T enters the cycle 2 → 1 → 2 → 1 → …. Since T extends naturally to the ring of 2-adic integers, ℤ_{2}, the statement of the 3x + 1 problem is also valid on ℤ_{2}. For brevity, we shall often refer to a 2-adic integer as simply a “2-adic”. Recall that an element, a, of ℤ_{2} is just a formal power series of the form Σ_{i=0}^{∞}a_{i}2^{i} where a_{i} ∈ {0, 1}. As is common, we will often abbreviate this by writing the sequence of 0s and 1s a_{0}, a_{1}, a_{2}, …_{2}. Note that we add the subscript 2 (to distinguish from base 10) when writing 2-adics and use an overbar to denote a repeating pattern. Note that both ℤ and the set of rationals with odd denominators are subrings of ℤ_{2} and thus, for clarity, we will frequently write an integer or rational number in place of its 2-adic representation. For example, \overline{10}_{2} denotes the 2-adic Σ_{i=0}^{∞}2^{2i} associated with −\frac{1}{3}.

Define the parity vector of length k for T of a [Lag] to be the sequence given by the function Q_{k} : ℤ_{2} → ℤ_{2}/2^{k}ℤ_{2} by

Q_{k}(a) = x_{0}(a), x_{1}(a), …, x_{k−1}(a)

where

x_{i}(n) ≡ T^{(i)}(n) mod 2

and

x_{i}(n) ∈ {0, 1}

for all i ≥ 0. The parity vector, Q_{k}(a), completely describes the behavior of the first k iterates of a under T. Q_{∞}(a) is defined in a similar manner and completely describes all iterates of a under T.

Q_{k} and Q_{∞} have several interesting properties: Q_{k} is periodic with period 2^{k} and induces a permutation of ℤ_{2}/2^{k}ℤ_{2}, denoted \overline{Q}_{k}; Q_{∞} is a continuous bijection. The proofs of these properties of Q_{k} and Q_{∞} may be found in [Lag]. Both have proven to be extremely useful in the study of the 3x + 1 problem.

In this paper we extend T to the 2-adic integers adjoined with i, ℤ_{2}[i]. We choose to extend to ℤ_{2}[i] because many number theoretic problems in ℤ have been solved by generalizing to the Gaussian integers ℤ[i]. In keeping with this theme, we shall refer to ℤ_{2}[i] as the set of Gaussian 2-adic integers or simply, the Gaussian 2-adics.

By freely associating a + bi ∈ ℤ_{2}[i] with (a, b) ∈ ℤ_{2} × ℤ_{2} we can define the metric D on ℤ_{2}[i] to be the product metric on ℤ_{2} × ℤ_{2} induced by the usual metric on ℤ_{2} which is derived from the 2-adic valuation. Addition and multiplication in ℤ_{2}[i] are defined in the usual manner. It is important to note that ℤ_{2}[i] is a commutative ring with identity, but not a field. In addition, ℤ_{2} is a commutative subring of ℤ_{2}[i] with identity and is also not a field.

4 Extension to ℤ_{2}[i]

Since T was piecewise defined depending on equivalence in ℤ/2ℤ, our extension is piecewise defined depending on equivalence in ℤ_{2}[i]/2ℤ_{2}[i] = {[0], [1], [i], [1 + i]}.

Definition 1 Let T̃ : ℤ_{2}[i] → ℤ_{2}[i] by

T̃(α) = \{ \begin{matrix}\frac{α}{2} & if α ∈ [0] \\ \frac{3α+1}{2} & if α ∈ [1] \\ \frac{3α+i}{2} & if α ∈ [i] \\ \frac{3α+1+i}{2} & if α ∈ [1 + i]. \end{matrix}

Notice that T̃ resembles T ×T to a great degree. It is then natural to ask how T̃ is different from T and T ×T; after all, we claim that T̃ is a non-trivial extension of T. Our response may be surprising: not only is T̃ not equal to T ×T, but T̃ and T ×T are not even conjugate via a ℤ_{2}-module isomorphism (though they are topologically conjugate, as we shall see in section 7.)

Notice that T̃ is an extension of the T, i.e. T̃|ℤ_{2} = T. It is also clear that T̃ is not the trivial extension T × T : ℤ_{2} × ℤ_{2} → ℤ_{2} × ℤ_{2}, e.g. T × T ((1, 2)) = (2, 1) while T̃(1 + 2i) = 2 + 3i.

What is more surprising, though, is that T̃ and T × T are not conjugate via a ℤ_{2}-module isomorphism. In order to show this, we must formalize our association between elements of ℤ_{2}[i] and ℤ_{2} × ℤ_{2}. Define a continuous bijection B : ℤ_{2}[i] → ℤ_{2}×ℤ_{2} by B(a+bi) = (a, b). Let T̂ : ℤ_{2}×ℤ_{2} → ℤ_{2}×ℤ_{2} by T̂ = B ∘ T̃ ∘ B^{−1}.

Theorem 1 There is no ℤ_{2}-module isomorphism A : ℤ_{2} × ℤ_{2} → ℤ_{2} × ℤ_{2} such that T̂ = A^{−1} ∘ T × T ∘ A.

Proof. Assume that such a ℤ_{2}-module isomorphism A exists. Let e_{1} = (1, 0) and e_{2} = (0, 1). Then Ae_{1} = (x_{1}, y_{1}) and Ae_{2} = (x_{2}, y_{2}) where x_{1}, x_{2}, y_{1} and y_{2} are 2-adics and (a, b) ∈ ℤ_{2} × ℤ_{2}. Then for all a, b ∈ ℤ_{2} × ℤ_{2}, A ∘ T̂((a, b)) = T × T ∘ A((a, b)). Let (a, b) ∈ (1, 0).

\begin{aligned}T × T (A((a, b))) & = & A(T̂((a, b))) \\ ⇒ T × T (( \begin{matrix}x_{1} & x_{2} \\ y_{1} & y_{2} \end{matrix} ) ( \begin{matrix}a \\ b \end{matrix} )) & = & A((\frac{3a+1}{2}, \frac{3b}{2})) \\ ⇒ T × T ((ax_{1} + bx_{2}, ay_{1} + by_{2})) & = & ( \begin{matrix}x_{1} & x_{2} \\ y_{1} & y_{2} \end{matrix} ) ( \frac{3a+1}{2} ; \frac{3b}{2} ) \\ ⇒ T × T ((ax_{1} + bx_{2}, ay_{1} + by_{2})) & = & (\frac{3ax_{1}+3bx_{2}+x_{1}}{2} , \frac{3ay_{1}+3by_{2}+y_{1}}{2} ) \end{aligned}

Thus, we have T × T ((ax_{1} + bx_{2}, ay_{1} + by_{2})) = (\frac{3ax_{1}+3bx_{2}+x_{1}}{2} , \frac{3ay_{1}+3by_{2}+y_{1}}{2} ). In order to evaluate T × T ((ax_{1} + bx_{2}, ay_{1} + by_{2})), we must determine the parities of ax_{1} + bx_{2} and ay_{1} + by_{2}. Because b is even and a is odd, the parities are completely determined by, and equivalent to, the parities of x_{1} and y_{1}. This yields the following four cases:

T ×T ((ax_{1}+bx_{2}, ay_{1}+by_{2})) = \{ \begin{matrix}(\frac{ax_{1}+bx_{2}}{2} , \frac{ay_{1}+by_{2}}{2} ) & if x_{1} even, y_{1} even \\ (\frac{3ax_{1}+3bx_{2}+1}{2}, \frac{ay_{1}+by_{2}}{2} ) & if x_{1} odd, y_{1} even \\ (\frac{ax_{1}+bx_{2}}{2} , \frac{3ay_{1}+3by_{2}+1}{2}) & if x_{1} even, y_{1} odd \\ (\frac{3ax_{1}+3bx_{2}+1}{2}, \frac{3ay_{1}+3by_{2}+1}{2}) & if x_{1} odd, y_{1} odd \end{matrix}

From this it is easy to check that T × T ((ax_{1} + bx_{2}, ay_{1} + by_{2})) = (\frac{3ax_{1}+3bx_{2}+x_{1}}{2} , \frac{3ay_{1}+3by_{2}+y_{1}}{2} ) if and only if x_{1} = 1 and y_{1} = 1. Thus, A must be

of the form ( \begin{matrix}1 & x_{2} \\ 1 & y_{2} \end{matrix} ).

Similarly, choosing (a, b) ∈ (0, 1) implies x_{2} = y_{2} = 1.

This means A = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ), but ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) is not invertible, which contradicts

our assumption.

QED

Since T̂ is conjugate to T̃ via the ℤ_{2}-module isomorphism B, we have:

Corollary 1 T̃ is not conjugate to T × T via a ℤ_{2}-module isomorphism.

5 Extension of Q_{k} and Q_{∞}

One of our main reasons for extending to ℤ_{2}[i] was to add the tools associated with ℤ_{2}[i] to the current tools for studying the 3x + 1 problem. With this in mind, we redefine Q_{k} in terms of T̃. Let Q̃_{k} : ℤ_{2}[i] → ℤ_{2}[i]/2^{k}ℤ_{2}[i] by

Q̃_{k}(α) = x̃_{0}(α), x̃_{1}(α), x̃_{2}(α), … x̃_{k−1}(α)

where

x̃_{i}(α) ≡ T̃^{(i)}(α) mod 2 for all i ≥ 0

and

x̃_{i}(α) ∈ {0, 1, i, 1 + i}

be the parity vector of length k for T̃ of α.

As with Q_{k}, Q̃_{k} completely describes the behavior of the first k iterates of α under T̃.

We also define Q̃_{∞} : ℤ_{2}[i] → ℤ_{2}[i] in a similar manner and note that, as you would expect, Q̃_{∞} completely describes the behavior of all iterates of α under T̃.

Q̃_{k} and Q̃_{∞} have properties similar to Q_{k} and Q_{∞} as will be demonstrated in the following theorems which mirror analogous theorems for Q_{k} and Q_{∞} found in [Lag]:

Theorem 2 The function Q̃_{k} : ℤ_{2}[i] → ℤ_{2}[i]/2^{k}ℤ_{2}[i] is periodic with period 2^{k}.

In order to show that Q̃_{k} is periodic, we begin by showing:

Lemma 1 T̃^{k}(α + ω2^{k}) ≡ T̃^{k}(α) + ω mod 2, for any α, ω ∈ ℤ_{2}[i].

Proof. We will proceed by induction on k. Let α, ω ∈ ℤ_{2}[i]. Base Case: (k = 1) In this case,

T̃(α + ω2) = \{ \begin{matrix}\frac{α}{2} + ω ≡ T̃(α) + ω mod 2 & if α ∈ [0] \\ \frac{3α+1}{2} + 3ω ≡ T̃(α) + ω mod 2 & if α ∈ [1] \\ \frac{3α+i}{2} + 3ω ≡ T̃(α) + ω mod 2 & if α ∈ [i] \\ \frac{3α+1+i}{2} + 3ω ≡ T̃(α) + ω mod 2 & if α ∈ [1 + i]. \end{matrix}

General Case: Assume T̃^{k−1}(α + ω2^{k−1}) ≡ T̃^{k−1}(α) + ω mod 2 for all n (inductive hypothesis).

Case 1: α ∈ [0]. Then

T̃^{k}(α + ω2^{k}) = T̃^{k−1}(T̃(α + ω2^{k}))
= T̃^{k−1}(\frac{α+ω2^{k}}{2} )  (since α ∈ [0])
= T̃^{k−1}(\frac{α}{2} + ω2^{k−1})
≡ T̃^{k−1}(\frac{α}{2}) + ω mod 2 (by ind hyp)
≡ T̃^{k}(α) + ω mod 2 (since α ∈ [0])

Case 2: α ∈ [1]. Then

T̃^{k}(α + ω2^{k}) = T̃^{k−1}(T̃(α + ω2^{k}))
= T̃^{k−1}(\frac{3(α+ω2^{k})+1}{2})  (since α ∈ [1])
= T̃^{k−1}(\frac{3α+1}{2} + ω2^{k} + ω2^{k−1})
≡ T̃^{k−1}(\frac{3α+1}{2} + ω2^{k}) + ω mod 2 (by ind hyp)
≡ T̃^{k−1}(\frac{3α+1}{2} + ω2^{k−1}) mod 2  (by ind hyp)
≡ T̃^{k−1}(\frac{3α+1}{2}) + ω mod 2  (by ind hyp)
≡ T̃^{k}(α) + ω mod 2  (since α ∈ [1])

Case 3 (α ∈ [i]) and Case 4 (α ∈ [1 + i]) are very similar to this case. Therefore, T̃^{k}(α + ω2^{k}) ≡ T̃^{k}(α) + ω mod 2 for all k by induction on k. QED It follows easily that x̃_{k} is also periodic in the same sense.

Corollary 2 For every α, ω ∈ ℤ_{2}[i], x̃_{j}(α + ω2^{j}) ≡ x̃_{j}(α) + ω mod 2 for all 0 ≤ j ≤ ∞.

From this we obtain Theorem 2.

Proof of Theorem 2. We shall proceed using induction on k.

Base Case :(k = 1)

Q̃_{1}(α + 2ω) = x̃_{0}(α + 2ω)
= x̃_{0}(α)  (by Corollary 2)
= Q̃_{1}(α)

General Case: Assume Q̃_{k−1}(α + ω2^{k−1}) = Q̃_{k−1}(α) (inductive hypothesis).

Q̃_{k}(α + ω2^{k}) = ∑_{j=0}^{k−1} x̃_{j}(α + ω2^{k})2^{j}
= ∑_{j=0}^{k−2} x̃_{j}(α + ω2^{k})2^{j} + x̃_{k−1}(α + ω2^{k})2^{k−1}
= Q̃_{k−1}(α + ω2^{k}) + x̃_{k−1}(α)2^{k−1} (by Corollary 2)
= Q̃_{k−1}(α) + x̃_{k−1}(α)2^{k−1}  (by ind hyp)
= ∑_{j=0}^{k−2} x̃_{j}(α)2^{j} + x̃_{k−1}(α)2^{k−1}
= ∑_{j=0}^{k−1} x̃_{j}(α)2^{j}
= Q̃_{k}(α)

QED

Theorem 3 Q̃_{∞} is an isometric homeomorphism.

Proof. We begin by showing that Q̃_{∞} is one-to-one.

Let α, β ∈ ℤ_{2}[i], α ≠ β. Then there exists ω ∈ ℤ_{2}[i] such that α = β + ω2^{k} where k = min{j : α_{j} ≠ β_{j}}, α = α_{0}, α_{1}, …, β = β_{0}, β_{1}, …, and ω is not equivalent to 0 mod 2. By Corollary 2, x̃_{k}(α) ≡ x̃_{k}(β + ω2^{k}) ≡ x̃_{k}(β) + ω mod 2. Consequently, x̃_{k}(α) − x̃_{k}(β) ≡ ω mod 2. Since ω is not equivalent to 0 mod 2, x̃_{k}(α) ≠ x̃_{k}(β) and therefore by definition of Q̃_{∞}, Q̃_{∞}(α) ≠ Q̃_{∞}(β). Thus, Q̃_{∞} is one-to-one.

Next we show that Q̃_{∞} preserves the metric (and is therefore continuous). Let α, β ∈ ℤ_{2}[i] where α = α_{0}, α_{1}, …, β = β_{0}, β_{1}, . . .. Choose k so that

D(α, β) = 2^{−k}. Then α ≡ β mod 2^{k}. By Theorem 2, Q̃_{k}(α) = Q̃_{k}(β), so Q̃_{∞}(α) ≡ Q̃_{∞}(β) mod 2^{k}. Thus, D(Q̃_{∞}(α), Q̃_{∞}(β)) ≤ 2^{−k}. However, because α is not equivalent to β mod 2^{k+1}, α = β + ω2^{k} for some ω ∈ ℤ_{2}[i], where ω is not equivalent to 0 mod 2. Hence, x̃_{k}(α) = x̃_{k}(β +ω2^{k}) ≡ x̃_{k}(β)+ ω mod 2 by Corollary 2. However, because ω is not equivalent to 0 mod 2, x̃_{k}(α) ≠ x̃_{k}(β). It follows that Q̃_{∞}(α) is not equivalent to Q̃_{∞}(β) mod 2^{k+1}. Therefore, D(Q̃_{∞}(α), Q̃_{∞}(β)) = 2^{−k} and so Q̃_{∞} preserves the metric.

Finally, we show that Q̃_{∞} is onto.

Let α = α_{0}, α_{1}, … ∈ ℤ_{2}[i], α′_{k} = α_{0}, …, α_{k}, \overline{0} ∈ ℤ_{2}[i], and α̂_{k} ∈ ℤ_{2}[i]/2^{k}ℤ_{2}[i] such that α ∈ α̂_{k}. We first note that Q̃_{k} is onto as can be seen by induction on k using Corollary 2. There exists a β′_{k} such that Q̃_{k}(β′_{k}) = α̂_{k}. Let β′_{k} = β_{0}, …, β_{k}, \overline{0}. We can see that Q̃_{∞}(β′_{k}) = α′_{k} mod 2^{k}. Thus, lim_{k→∞} D(Q̃_{∞}(β), α′_{k})) = 0. Consequently, lim_{k→∞} Q̃_{∞}(β′_{k}) = lim_{k→∞} α′_{k} = α. Now, because Q̃_{∞} is continuous, lim_{k→∞} Q̃_{∞}(β′_{k}) = Q̃_{∞}(lim_{k→∞} β′_{k}) = α. So all that remains is to show that lim_{k→∞} β′_{k} exists as a Gaussian 2-adic. Since the sequence {Q̃_{∞}(β′_{k})} converges to α it is Cauchy. Because Q̃_{∞} preserves the metric, the sequence {β′_{k}} in ℤ_{2}[i] is also a Cauchy sequence. Now, ℤ_{2}[i] is a compact metric space by the Tychonoff theorem, so every Cauchy sequence in ℤ_{2}[i] has a limit in ℤ_{2}[i]. Thus the sequence {β′_{k}} converges to some β ∈ ℤ_{2}[i] and Q̃_{∞}(β) = α. Therefore Q̃_{∞} is onto.

Q̃_{∞}^{−1} is continuous because Q̃_{∞} is an isometry and therefore Q̃_{∞} is an isometric homeomorphism.

QED

Now that we have shown Q̃_{∞} is a continuous bijection, we shall see just how powerful a tool it is in our exploration of the dynamics of T̃.

6 Chaos and the 3x + 1 Problem

Chaoticity in the sense of [Dev] is preserved by topological conjugacy, so we can show that a function is chaotic if it is topologically conjugate to a known chaotic map. Such a map is the shift map on the sequence space, σ : Σ → Σ, where

Σ = {s_{0}, s_{1}, s_{2}, … |s_{j} ∈ {0, 1}}

and

σ(s_{0}, s_{1}, s_{2}, …) = s_{1}, s_{2}, s_{3}, ….

Q_{∞} provides a conjugacy between T and σ. Thus we have shown: Theorem 4 T : ℤ_{2} → ℤ_{2} is chaotic.

Since the product of chaotic maps is itself a chaotic map, we have: Corollary 3 T × T is chaotic

Certainly if T is chaotic, any reasonable extension of T should also be chaotic. We show that T̃ is chaotic by showing that it is conjugate to some known chaotic system. With this in mind we define σ_{4} :(Σ_{4}, d_{δ})→(Σ_{4}, d_{δ}) and show that σ_{4} and σ × σ are conjugate via a homeomorphism, F.

Let σ_{4} :(Σ_{4}, d_{δ})→(Σ_{4}, d_{δ}) be the shift map on the sequence space with four elements {0, 1, i, 1 + i} where

d_{δ}((s_{0}, s_{1}, …), (t_{0}, t_{1}, …)) = Σ_{k=0}^{∞} \frac{δ_{k}(s, t)}{4^{k}}

and

δ_{k} = \{ \begin{matrix}0 & if s_{k} = t_{k} \\ 1 & otherwise. \end{matrix}

It can easily be shown that σ_{4} :(Σ_{4}, d_{δ})→(Σ_{4}, d_{δ}) is chaotic. Lemma 2 The function F : Σ_{4} → Σ × Σ by

F (s) = ((a_{1}(s), a_{2}(s), a_{3}(s), …), (b_{1}(s), b_{2}(s), b_{3}(s), …))

where each

a_{i}(s) = \{ \begin{matrix}0 & if s_{i} = 0 or i \\ 1 & if s_{i} = 1 or 1 + i \end{matrix}

and each

b_{i}(s) = \{ \begin{matrix}0 & if s_{i} = 0 or 1 \\ 1 & if s_{i} = i or 1 + i. \end{matrix}

is a homeomorphism.

Proof. It is clear that F is a bijection. We now show that F is continuous. Let ϵ > 0, δ = 4^{−k} where k is chosen to make 2^{−k} < ϵ, s = s_{0}, s_{1}, … ∈

Σ_{4}, t = t_{0}, t_{1}, … ∈ Σ_{4}. If d_{δ}(s, t) < δ then s_{j} = t_{j} for all 0 ≤ j ≤ k. Consequently, if we consider that F (s) = (x, y) and F (t) = (z, w) for some (x, y), (z, w) ∈ Σ × Σ where x = x_{0}, x_{1}, … ∈ Σ, y = y_{0}, y_{1}, … ∈ Σ, z = z_{0}, z_{1}, … ∈ Σ, and w = w_{0}, w_{1}, … ∈ Σ then x_{j} = z_{j} and y_{j} = w_{j} for all 0 ≤ j ≤ k by definition of d_{δ}. Thus, by definition of F, d_{x}(F (s), F (t)) ≤ 2^{−k} < ϵ where d_{x} is the product metric on Σ. So F is continuous.

By letting ϵ > 0 and choosing δ = 2^{−k} where k is such that 4^{−k} < ϵ, we can apply a similar argument to show that F^{−1} is continuous. Therefore, F is a homeomorphism.

QED

It easily follows that:

Corollary 4 σ_{4} and σ × σ are conjugate via F.

Since T̃ is conjugate to σ_{4} via Q̃_{∞} we have:

Theorem 5 T̃ is chaotic.

It turns out that in proving the chaoticity of T, T̃, and T × T we have defined some very useful conjugacies as we shall see in the next section.

7 Relationship between T̃ and T × T

Though T̃ and T ×T are not conjugate via a ℤ_{2}-module isomorphism, they are topologically conjugate. Since topological conjugacy is transitive, T̃ ˜=σ_{4} ˜=σ× σ ˜=T × T where ˜= denotes topological conjugacy and thus:

Theorem 6 T̃ and T × T are topologically conjugate (via (Q_{∞} × Q_{∞})^{−1} ∘ F ∘ Q̃_{∞}).

These theorems allow us to work in the system of our choice and then convert the results to any other system using the homeomorphisms defined above.

8 Acknowledgement

This paper was completed as a result of three years of work by the author as an undergraduate in the Faculty/Student Research Program at the University of Scranton under the direction of Dr. Kenneth Monks. I would like to dedicate this paper to Dr. Monks for all of his time, effort and assistance without which this paper could not have been completed.

References

[Lag] J. C. Lagarias, The 3x+1 Problem and Its Generalizations, American Mathematics Monthly 92 (1985), 3-23.

[Dev] R.L. Devaney A First Course in Chaotic Dynamical Systems: Theory and Experiment (Addison-Wesley Pub Co, 1992).

Department of Mathematics and Statistics University of Massachusetts Amherst, MA 01003 E-mail address: joseph@math.umass.edu