Conjugacy and the 3x + 1 Conjecture

Michael Fraboni

May 12, 1997

Abstract

The 3x + 1 conjecture states that for all x ∈ ℤ^{+}, there exists a positive integer k such that T^{k}(x) = 1 where T : ℤ^{+} → ℤ^{+} by

T (x) =\begin{cases}x/2 & if x is even \\ (3x + 1)/2 & if x is odd \end{cases}. We construct an infinite family of

functions, F, whose members are topologically conjugate to the extension of T on ℤ_{2}. We then show that every function which is conjugate to T by a linear homeomorphism is a member of this family. In addition we show there is a function which is a member of F and which is conjugate to T by a nonlinear homeomorphism. Finally, we construct a function which is topologically conjugate to T and which is not a member of F.

1 Introduction

The 3x + 1 conjecture, also known as the Collatz conjecture, involves the iteration of the function T : ℤ^{+} → ℤ^{+} by

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

The conjecture states that for every positive integer x, there exists a positive integer k such that T^{k}(x) = 1 where T^{k} is the k-fold composition of T with itself. The function T may be extended to the 2-adic integers ℤ_{2} (see section 3.1) in a natural manner, and for the remainder of the paper we will consider T to be a map on ℤ_{2}.

One approach to take in trying to solve this problem is to investigate the behavior of T by studying the dynamics of functions which are topologically conjugate to T. If f : X → X and g : Y → Y where X and Y are topological spaces then f is conjugate to g if there exists a bijection h : X → Y such that the diagram

\begin{matrix}X & ⟶^{f} & X \\ h ↓ & & ↓ h \\ Y & ⟶_{g} & Y \end{matrix}

commutes, that is, h ∘ f = g ∘ h. The map h is called a conjugacy. If the function h is also a homeomorphism then we say that f and g are topologically conjugate, and we call h a topological conjugacy. One property of conjugacy is that it preserves the dynamics of a function. So, if we find a function, f, which is conjugate to T by a relatively simple bijection then we will be able to understand the behavior of T by describing the behavior of f, and thus hopefully answer the conjecture.

For example, it is shown in [Lag] that T is topologically conjugate to the shift map, σ (see section 3.2), on ℤ_{2} and thus chaotic. Although σ is easy to understand, the conjugacy between σ and T is very complicated, so we cannot use it to describe the behavior of T in full. This leads us to search for functions not only whose dynamics are easy to understand, but which have accessible conjugacies with T. To this end, we find a family, F, of functions on the 2-adics whose elements are topologically conjugate to T. This family contains all functions which are conjugate to T by linear maps –certainly the simplest of homeomorphisms. F does not contains all functions which are topologically conjugate to T, but it does contain some which are topologically conjugate by nonlinear homeomorphisms, in particular σ ∈ F.

2 Summary of Results

In this section we state our main theorems, leaving their proofs for later in the paper.

The most obvious first step when looking for maps topologically conjugate to T is to use functions that “look like” the 3x + 1 map. One such family of functions is given in the following definition.

Definition. A function f_{a,b,c,d} : ℤ_{2} → ℤ_{2} is modular if it is of the form:

f_{a,b,c,d}(x) = \begin{cases}\frac{ax+b}{2} & if x is even \\ \frac{cx+d}{2} & if x is odd \end{cases}

with a, b, c, d ∈ ℤ_{2}.

We should note that f_{a,b,c,d} does not define a function for every a, b, c and d. However, the definition of modular requires that f_{a,b,c,d} be a function.

Obviously T itself is a modular function (with a = d = 1, b = 0, c = 3), and we might say that functions which are modular “look like” T. We define an infinite family of modular functions.

Definition. Let F be the set of modular functions, f_{a,b,c,d}, such that a, c and d are odd and b is even.

Example 1. Since T = f_{1,0,3,1} we see that T ∈ F.

Example 2. The shift map, σ, is f_{1,0,1,−1}, and thus is a member of F as well.

The importance of this family is illustrated by the following theorems.

Theorem 1. Let f : ℤ_{2} → ℤ_{2} be a modular function. Then f is conjugate to T if and only if f ∈ F. Furthermore, every f ∈ F is topologically conjugate to T.

In order to use these maps to study the conjecture we also need to understand the behavior of the conjugacies between the maps and T. To be a conjugacy, a function must be bijective, and one simple type of bijective function is the linear map. Are functions which are conjugate to T by linear maps in our set F? We have the following.

Theorem 2. Every map which is conjugate to T by a linear homeomorphism is a member of F. In fact, a map is conjugate to T by a linear homeomorphism if and only if it is of the form f_{1,q,3,p−q} where p is odd and q is even or f_{3,p−q,1,q} where both p and q are odd.

As we will see, the shift map is not conjugate to T by a linear conjugacy. Thus not all elements of F are conjugate to T by linear maps. Additionally, there are maps which are conjugate to T that are not members of F. Specifically, we will show that a map which is conjugate to T by a piecewise linear function is not necessarily in F.

The parity vector function (see section 3.2) has played an important part in work done in the past on the 3x+1 problem ([Lag], [FLW], [Jos]). In order to prove Theorems 1 and 2 above we generalize several of the technical results concerning the properties of the parity vector function to show that they apply to all elements of F in general, and not just to T. These generalizations are described in Section 4.

3 Background and Notation

3.1 Meet the 2-adics

A 2-adic integer is an infinite sequence

s_{0}, s_{1}, s_{2}, ...

where s_{i} ∈ {0, 1} for all i ≥ 0. When writing a 2-adic integer we will often omit the commas. We say that s_{0}, s_{1}, s_{2}, ... ∈ ℤ_{2} is even if s_{0} = 0 and is odd if s_{0} = 1. We may consider ℤ^{+} to be a subset of ℤ_{2} by identifying n ∈ ℤ^{+} with its base-2 expansion (written in reverse order) and completed with an infinite string of zeros (denoted ¯0).

Example 3. The 2-adic representation of 5 is 101¯0.

Addition and multiplication are easily defined on the 2-adics by extending the usual algorithms for adding and multiplying integers in base 2 (see [Jos] for a nice exposition). With these operations, ℤ_{2} becomes a ring containing ℤ as a subring. Just as in ℤ, s ∈ ℤ_{2} is odd or even based on its equivalence in ℤ_{2}/2ℤ_{2} = {[0], [1]}. Notice that s ∈ ℤ_{2} is even if and only if s ≡ 0 mod 2, and is odd if and only if s ≡ 1 mod 2. Since even and odd are well defined on ℤ_{2} the map T extends nicely.

ℤ_{2} is also a metric space with distance function defined by

d(a, b) = |a − b|_{2}

where | |_{2} is the 2-adic valuation given by

|s|_{2} = \begin{cases}0 & if s = 0 \\ 2^{−min\{i|s_{i}=1\}} & if s ≠ 0 \end{cases}

where s_{0}, s_{1}, ... are the 2-adic digits of s. A nice visualization of ℤ_{2} as a metric space can be found in [Fus].

It is also well known that ℤ_{2} contains the ring of rational numbers with odd denominators. Note that 2 has no multiplicative inverse in ℤ_{2}, and therefore ℤ_{2} does not contain the reciprocal of any even integer.

We will now review some results obtained from extending T to ℤ_{2} which are important to this paper.

3.2 Parity Vectors for T

The information in this section may be found in [Lag].

The parity vector function of length k associated with T, Q_{k}, is given by the sequence

Q_{k}(α) = x_{0}(α), x_{1}(α), x_{2}(α), ..., x_{k−1}(α)

where α ∈ ℤ_{2}, x_{i}(α) ∈ {0, 1} and

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

for all 0 ≤ i ≤ k − 1.

Similarly, we may define the parity vector function associated with T, Q, as the infinite sequence

Q(α) = x_{0}(α), x_{1}(α), x_{2}(α), ...

where α ∈ ℤ_{2}, x_{i}(α) ∈ {0, 1} and

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

for all 0 ≤ i. Thus Q is a map from ℤ_{2} to ℤ_{2} (note that Q is called Q_{∞} in [Lag], [Jos] and [FLW]).

Lagarias shows that Q_{k} is periodic with period 2^{k}, and uses this to prove that Q is a homeomorphism.

Another important function is the shift map, σ : ℤ_{2} → ℤ_{2} by

σ(x) = \begin{cases}\frac{x}{2} & if x is even \\ \frac{x−1}{2} & if x is odd. \end{cases}

This function simply “removes” the first digit of a 2-adic integer. Interestingly enough, this function is chaotic. This is important because T has been proven to be topologically conjugate to σ using Q [Lag], and hence T is chaotic.

3.3 Parity Vectors for Functions in F

Recall F is the set of functions

{f_{a,b,c,d} : ℤ_{2} → ℤ_{2}|a, b, c, d ∈ ℤ_{2} where a, c and d are odd, and b is even}

where

f_{a,b,c,d}(x) = \begin{cases}\frac{ax+b}{2} & if x is even \\ \frac{cx+d}{2} & if x is odd. \end{cases}

Let f : ℤ_{2} → ℤ_{2}. The parity vector function of length k associated with f, Φ_{k}, is given by the sequence

Φ_{k}(α) = x_{0}(α), x_{1}(α), x_{2}(α), ..., x_{k−1}(α)

where α ∈ ℤ_{2}, x_{i}(α) ∈ {0, 1} and

x_{i}(α) ≡ f^{i}(α) mod 2

for all 0 ≤ i ≤ k − 1.

Similarly, we may define the parity vector function associated with f, Φ, as the infinite sequence

Φ(α) = x_{0}(α), x_{1}(α), x_{2}(α), ...

where α ∈ ℤ_{2}, x_{i}(α) ∈ {0, 1} and

x_{i}(α) ≡ f^{i}(α) mod 2

for all 0 ≤ i. Thus Φ is a map from ℤ_{2} to ℤ_{2}.

We will continue to refer to the parity vector function associated with T as Q, and the parity vector function of length k associated with T as Q_{k}.

4 Technical Results and Proofs

4.1 All members of F are conjugate to T

We will begin by showing that the parity vector functions, Φ, retain the important properties of Q. Specifically, we will show that Φ_{k} is periodic with period 2^{k}, and that Φ is a homeomorphism. We will then use this to show that elements of the set F are topologically conjugate to T.

Theorem 3. Let f ∈ F and let Φ_{k} be the parity vector function of length k associated with f. Then for any positive integer k, Φ_{k} is periodic with period 2^{k}.

Before showing this we need two lemmas.

Lemma 1. Let f ∈ F then for any non-negative integer k, f^{k}(α + ω2^{k}) ≡ f^{k}(α) + ω mod 2, for any α, ω ∈ ℤ_{2}.

Proof. Let f ∈ F then f = f_{a,b,c,d} for some a, b, c, d ∈ ℤ_{2}, with a, c, d odd and b even. Then let α, ω ∈ ℤ_{2}. We will use induction on k.

Base Case: Let k = 0. Then

\begin{aligned}f^{0}(α + ω) & = & α + ω \\ & ≡ & f^{0}(α) + ω mod 2. \end{aligned}

Inductive Hypothesis: Assume f^{k−1}(α + ω2^{k−1}) ≡ f^{k−1}(α) + ω mod 2.

We now have two cases depending on the parity of α.

Case 1: α is even.

f^{k}(α + ω2^{k}) = f^{k−1}(f(α + ω2^{k}))
= f^{k−1}(\frac{a(α+ω2^{k})+b}{2})  (since α is even)
= f^{k−1}(\frac{aα+b}{2} + aω2^{k−1})
≡ f^{k−1}(\frac{aα+b}{2}) + aω mod 2 (by ind. hyp.)
≡ f^{k−1}(\frac{aα+b}{2}) + ω mod 2 (since a is odd)
≡ f^{k−1}(f(α)) + ω mod 2 (since α is even)
≡ f^{k}(α) + ω mod 2

Case 2: α is odd.

f^{k}(α + ω2^{k}) = f^{k−1}(f(α + ω2^{k}))
= f^{k−1}(\frac{c(α+ω2^{k})+d}{2})  (since α is odd)
= f^{k−1}(\frac{cα+d}{2} + cω2^{k−1})
≡ f^{k−1}(\frac{cα+d}{2}) + cω mod 2 (by ind. hyp.)
≡ f^{k−1}(\frac{cα+d}{2}) + ω mod 2 (since c is odd)
≡ f^{k−1}(f(α)) + ω mod 2 (since α is odd)
≡ f^{k}(α) + ω mod 2

Thus, f^{k}(α + ω2^{k}) ≡ f^{k}(α) + ω mod 2 for all positive integers k.

Now we produce a similar result concerning the elements of a parity vector.

Lemma 2. Let f ∈ F and let x_{k−1}(α) be the k^{th} term in the parity vector function associated with f. Then for every α, ω ∈ ℤ_{2}, x_{k}(α + ω2^{k}) ≡ x_{k}(α) + ω mod 2 for all 0 ≤ k ≤ ∞.

Proof. Let f ∈ F. Then let α, ω ∈ ℤ_{2} and let x_{k−1}(α) be the k^{th} element in the parity vector function associated with f. Then for all 0 ≤ k ≤ ∞ we have the following.

x_{k}(α + ω2^{k}) ≡ f^{k}(α + ω2^{k}) mod 2
≡ f^{k}(α) + ω mod 2 (by Lemma 1)
≡ x_{k}(α) + ω mod 2

We are now ready to prove Theorem 3.

Proof of Theorem 3. Let f ∈ F, let Φ_{k} be the parity vector function of length k associated with f, and let α, ω ∈ ℤ_{2}. Again, we will use induction on k.

Base Case: Let k = 1. Then

Φ_{1}(α + 2ω) = x_{0}(α + 2ω)
= x_{0}(α)  (by Lemma 2)
= Φ_{1}(α).

Inductive Hypothesis: Assume Φ_{k−1}(α + ω2^{k−1}) = Φ_{k−1}(α). Then we have

Φ_{k}(α + ω2^{k}) = x_{0}(α + ω2^{k}), x_{1}(α + ω2^{k}), …, x_{k−1}(α + ω2^{k})
= Φ_{k−1}(α + ω2^{k}), x_{k−1}(α + ω2^{k})
= Φ_{k−1}(α + ω2^{k}), x_{k−1}(α)  (by Lemma 2)
= Φ_{k−1}(α), x_{k−1}(α)  (by ind. hyp.)
= x_{0}(α), x_{1}(α), …, x_{k−1}(α)
= Φ_{k}(α).

Thus Φ_{k} is periodic with period 2^{k}.

Now, to show that Φ is a homeomorphism we use a result whose proof is mentioned in [Lag] for the case Φ = Q. For a more detailed exposition see [Jos]. Their proofs for Q carry over exactly for any Φ.

Theorem 4. ([Lag],[Jos]) If f : ℤ_{2} → ℤ_{2} is a function whose parity vector functions of length k, Φ_{k}, are periodic with period 2^{k} and for which x_{k}(α + ω2^{k}) ≡ x_{k}(α) + ω mod 2 for all k, then the parity vector function associated with f, Φ, is a measure preserving homeomorphism.

So, by Theorem 3 and Lemma 2, for any f ∈ F the parity vector function associated with f is a homeomorphism. Now recall Theorem 1.

Theorem 1. Let f : ℤ_{2} → ℤ_{2} be a modular function. Then f is conjugate to T if and only if f ∈ F. Furthermore, every f ∈ F is topologically conjugate to T.

We use several lemmas to show this result.

Lemma 3. Let f ∈ F then f is topologically conjugate to σ.

Proof. Let f ∈ F and let Φ be the parity vector function associated with f. Theorem 4 tells us that Φ is a homeomorphism. Then for any α ∈ ℤ_{2} we have

(Φ ∘ f)(α) = Φ(f(α))
= x_{0}(f(α)), x_{1}(f(α)), x_{2}(f(α)), …
= x_{1}(α), x_{2}(α), x_{3}(α), …
= σ(x_{0}(α), x_{1}(α), x_{2}(α), …)
= σ(Φ(α))
= (σ ∘ Φ)(α).

Thus, f is topologically conjugate to σ.

Lemma 4. Let f, g ∈ F then f and g are topologically conjugate.

Proof. Let f, g ∈ F. By Lemma 3, f and g are topologically conjugate to σ. Topological conjugacy is well known to be an equivalence relation and thus transitive. So we see that f and g are topologically conjugate.

We should note that for f, g ∈ F with parity vector functions Φ and Ψ respectively, the conjugacy between f and g is the homeomorphism Ψ^{−1} ∘ Φ.

Lemma 5. Let f ∈ F then f is topologically conjugate to T.

Proof. Let f ∈ F. Then, we know from Lemma 4 that any two elements of F are topologically conjugate. Therefore, since T ∈ F we know that f is topologically conjugate to T.

Lemma 6. Let a, b, x, y ∈ ℤ_{2} where a ≠ 0. If ax + b = ay + b then x = y.

Proof.

ax + b = ay + b ⇒ ax = ay
⇒ ax − ay = 0
⇒ a(x − y) = 0

It is well known (e.g. [Ser]) that ℤ_{2} is an integral domain. Since a ≠ 0 we must have (x − y) = 0, and thus x = y.

Lemma 7. Let f : ℤ_{2} → ℤ_{2}. If f is conjugate to T and modular then f ∈ F.

Proof. Let f_{a,b,c,d} be a modular function and assume that f_{a,b,c,d} is conjugate to T. Then f_{a,b,c,d} must have the same dynamics as σ since σ is conjugate to T. In particular, every number in ℤ_{2} has exactly two distinct preimages under σ, so the same must hold for f_{a,b,c,d}.

First, we note that if a = 0 then \frac{b}{2} has infinitely many preimages, contradicting the assumption that f is conjugate to σ. Similarly, if c = 0 then \frac{d}{2} has infinitely many preimages, again contradicting the assumption that f is conjugate to σ. Thus a, c ≠ 0.

Now, in order for a point n to have two preimages, we must have f_{a,b,c,d}(x) = n and f_{a,b,c,d}(y) = n for some x, y ∈ ℤ_{2}. Note that since a ≠ 0, \frac{as+b}{2} = \frac{at+b}{2} ⇒ as + b = at + b ⇒ s = t by Lemma 6. Similarly, since c ≠ 0, \frac{cs+d}{2} = \frac{ct+d}{2} ⇒ cs + d = ct + d ⇒ s = t by Lemma 6. Therefore, one of the x or y must be even, and the other must be odd. Without loss of generality assume x is even and y is odd.

Since x is even we note that n = \frac{ax+b}{2} and then b = 2n − ax. We may conclude from this equation that b is even.

For any n we must find an x such that ax = 2n − b. If we let n = 1 + \frac{b}{2} then we have ax = 2(1 + \frac{b}{2}) − b = 2. Then ax = 2, and since x is even this implies that a is odd. Therefore, if f_{a,b,c,d} is conjugate to T then a is odd.

Now, since y is odd we note that n = \frac{cy+d}{2} then cy = 2n − d. We conclude from this equation that c ≡ d mod 2.

Assume c and d are even, and let n = c+ \frac{d}{2}. Then cy = 2(c+ \frac{d}{2})−d = 2c. Then since c ≠ 0, Lemma 6 implies that y = 2, which contradicts our assumption that y is odd. Therefore, if f_{a,b,c,d} is conjugate to T then c and d are odd.

Thus, if f_{a,b,c,d} is conjugate to T then f_{a,b,c,d} ∈ F.

Proof of Theorem 1. Let f : ℤ_{2} → ℤ_{2} be a modular function. If f is conjugate to T then by Lemma 7, f ∈ F.

If f ∈ F then by Lemma 5 f is topologically conjugate to T. However, whenever two functions are topologically conjugate they are also conjugate. Thus f is conjugate to T.

4.2 Some Simple Conjugacies

Now that we have established that our family F contains all the modular functions which are topologically conjugate to T we proceed to show that some of these functions are conjugate by simple, namely linear, homeomorphisms.

4.2.1 Linear Conjugacies

We will begin with linear conjugacies. It is easy to check that linear bijections with 2-adic coefficients are continuous with linear inverses, and thus homeomorphisms. Therefore, all linear conjugacies are also topological conjugacies.

First we will show what conditions are necessary for a linear function with 2-adic coefficients to be a bijection. The following is a corollary to Theorem 5 (see section 4.2.2).

Corollary 1. Let G : ℤ_{2} → ℤ_{2} by G(x) = px + q with p, q ∈ ℤ_{2}. Then G is a bijection if and only if p is odd.

Proof. Let p = r and q = s in Theorem 5.

Recall Theorem 2.

Theorem 2. Every map which is conjugate to T by a linear homeomorphism is a member of F. In fact, a map is conjugate to T by a linear homeomorphism if and only if it is of the form f_{1,q,3,p−q} where p is odd and q is even or f_{3,p−q,1,q} where both p and q are odd.

Proof. Let f : ℤ_{2} → ℤ_{2} with G(x) = px+q a linear conjugacy between T and f where p, q ∈ ℤ_{2}. Then, f(x) = (G ∘ T ∘ G^{−1})(x) and G is a homeomorphism. Since G is a homeomorphism, it is a bijection, and then from Corollary 1 we know p is odd.

We will compute (G ∘ T ∘ G^{−1})(x).

G^{−1}(x) = \frac{x − q}{p}

(T ∘ G^{−1})(x) = \begin{cases}\frac{x−q}{2p} & if x − q is even \\ \frac{3x−3q+p}{2p} & if x − q is odd \end{cases}

(G ∘ T ∘ G^{−1})(x) = \begin{cases}\frac{x+q}{2} & if x − q is even \\ \frac{3x+p−q}{2} & if x − q is odd \end{cases}

Now we note that when q is even we have x − q is even if and only if x is even and x − q is odd if and only if x is odd. If q is odd just the opposite is true. Now f is given by the following cases.

Case 1: q is even.

f(x) = (G ∘ T ∘ G^{−1})(x) = \begin{cases}\frac{x+q}{2} & if x is even \\ \frac{3x+p−q}{2} & if x is odd \end{cases}
= f_{1,q,3,p−q}(x)

Case 2: q is odd.

f(x) = (G ∘ T ∘ G^{−1})(x) = \begin{cases}\frac{3x+p−q}{2} & if x is even \\ \frac{x+q}{2} & if x is odd \end{cases}
= f_{3,p−q,1,q}(x)

Thus, any function topologically conjugate to T by a linear map is of the form f_{1,q,3,p−q} when p is odd and q is even, or of the form f_{3,p−q,1,q} when p is odd and q is odd.

Even though all functions conjugate to T by a linear conjugacy belong to F, not all functions in F are conjugate to T by a linear conjugacy. For instance σ = f_{1,0,1,−1} is not of either form stated in Theorem 2. From this reasoning follows directly that the conjugacy between T and σ, Q, is a nonlinear function (this can also be proven quite easily by simply computing the images of 3 values under Q and noting that they are not collinear).

This result is actually somewhat unfortunate since σ has very easy to understand behavior, and if we knew what the image of ℤ^{+} was under Q we would certainly be able to say much about T. Unfortunately the behavior of Q is very complex and anything but linear.

4.2.2 Piecewise Linear Conjugacies

Finally, we look at piecewise linear conjugacies. First we describe what conditions are necessary and sufficient for a piecewise linear function to be bijective.

Theorem 5. Let p, q, r, s ∈ ℤ_{2}, and let G : ℤ_{2} → ℤ_{2} by

G(x) = \begin{cases}px + q & if x is even \\ rx + s & if x is odd. \end{cases}

Then G is a bijection if and only if p and r are odd and q ≡ s mod 2

We need a lemma before proving this theorem.

Lemma 8. Let G : ℤ_{2} → ℤ_{2} as above. If G is onto then

G([0]) = [0] and G([1]) = [1] or
G([0]) = [1] and G([1]) = [0].

That is, either G maps evens to evens and odds to odds, or else G maps evens to odds and odds to evens.

Proof. Let G be onto, and x ∈ ℤ_{2}.

If x is even, then px ≡ 0 mod 2. So G(x) = px + q ≡ q mod 2 and thus G([0]) ⊆ [q]. Since q is either even or odd, we have G([0]) ⊆ [0], or G([0]) ⊆ [1].

If x is odd, then rx ≡ r mod 2, so G(x) = rx+s ≡ r+s mod 2 and thus G([1]) ⊆ [r + s]. Since r + s is either even or odd, we have G([1]) ⊆ [1], or G([1]) ⊆ [0].

If G([0]) ⊆ [0] then G([1]) ⊆ [1] since G is onto and in fact, G([0]) = [0] and G([1]) = [1]. Similarly if G([0]) ⊆ [1] then G([1]) ⊆ [0] since G is onto and in fact, G([0]) = [1] and G([1]) = [0].

Now we are ready to prove Theorem 5.

Proof of Theorem 5. Let G : ℤ_{2} → ℤ_{2} as stated in Theorem 5. (⇒) We will begin by showing that if G is a bijection then p and r are odd and q ≡ s mod 2. Note that if p = 0 then G(0) = G(2) which contradicts the assumption that G is bijective. Similarly, if r = 0 then G(1) = G(3) contradicting the assumption that G is bijective. Thus p, r ≠ 0.

First, assume p is not odd, then we have two cases.

Case 1: p is even and q is even.

G(0) = q is even and so G([0]) = [0] by Lemma 8. Since p + q is even there exists an even x such that G(x) = p + q. Then px + q = p + q and since p ≠ 0 Lemma 6 implies that x = 1 which is odd, contradicting our assumption about x.

Case 2: p is even and q is odd.

G(0) = q is odd and so G([0]) = [1] by Lemma 8. Since p + q is odd there exists an even x such that G(x) = p + q. Then px + q = p + q and since p ≠ 0 Lemma 6 implies that x = 1 which is odd, contradicting our assumption about x.

Therefore whenever G is a bijection p is odd.

Now, assume r is not odd, then we have two more cases.

Case 3: r is even and s is even.

G(1) = r + s is even and so G([1]) = [0] by Lemma 8. Then since 2r + s is even there exists an odd x such that G(x) = 2r + s. Thus rx + s = 2r + s and since r ≠ 0 Lemma 6 implies that x = 2 which is even, contradicting our assumption about x.

Case 4: r is even and s is odd.

G(1) = r + s is odd and so G([1]) = [1] by Lemma 8. Then since 2r + s is odd there exists an odd x such that G(x) = 2r + s. Thus rx + s = 2r + s and since r ≠ 0 Lemma 6 implies that x = 2 which is even, contradicting our assumption about x.

Therefore whenever G is a bijection r is odd.

Now we will show that if G is a bijection then q ≡ s mod 2

Case 1: Let q be even. Then G(0) = q is even which implies that G([0]) = [0], and G([1]) = [1] by Lemma 8. Then G(1) = r + s is odd and since r is odd s must be even. So q ≡ s mod 2.

Case 2: Now let q be odd. Then G(0) = q is odd which implies that G([0]) = [1], and G([1]) = [0] by Lemma 8. Then G(1) = r + s is even and since r is odd s must be odd. So q ≡ s mod 2.

Therefore when G is a bijection, q ≡ s mod 2

(⇐) Now we will show that if p and r are odd and q ≡ s mod 2 then G is a bijection.

Assume p and r are odd and q ≡ s mod 2. Note that since p and r are odd p, r ≠ 0.

First we will show that G is injective. Let x, y ∈ ℤ_{2} and let G(x) = G(y). Now we have several cases to consider.

Case 1: When x is even and y is even we have px + q = py + q. Thus x = y by Lemma 6.

Case 2: When x is even, and y is odd we have

px + q = ry + s ⇒ px ≡ ry mod 2 ⇒ x ≡ y mod 2

which is a contradiction. Therefore, we cannot have an even x and an odd y.

Case 3: When x is odd and y is even we have

rx + s = py + q ⇒ rx ≡ py mod 2 ⇒ x ≡ y mod 2

which is a contradiction. Therefore, we cannot have an odd x and an even y.

Case 4: When x is odd and y is odd we have rx + s = ry + s. Thus x = y by Lemma 6.

Therefore, G(x) = G(y) implies x = y, so G is injective.

Now we show that G is a surjection.

Let y ∈ ℤ_{2}. If y is odd and q and s are odd then, \frac{y−q}{p} is even, and G(\frac{y−q}{p}) = y.

If y is odd and q and s are even then, \frac{y−s}{r} is odd, and G(\frac{y−s}{r}) = y

If y is even and q and s are odd then, \frac{y−s}{r} is odd, and G(\frac{y−s}{r}) = y.

If y is even and q and s are even then, \frac{y−q}{p} is even, and G(\frac{y−q}{p}) = y

Therefore, for any y ∈ ℤ_{2} there exists an x such that G(x) = y, and so G is a surjection.

Thus G is a bijection.

Now we will derive the general form of a map which is conjugate to T by a piecewise linear map in order to see if any of these are not members of F.

Let p, q, r, s ∈ ℤ_{2} where p and r are odd, q ≡ s mod 2 and G : ℤ_{2} → ℤ_{2} by

G(x) = \begin{cases}px + q & if x is even \\ rx + s & if x is odd. \end{cases}

Then by Theorem 5 G is a bijection. Let f = (G ∘ T ∘ G^{−1}). We wish to compute f(x).

First we compute G^{−1}(x) Case 1: q and s are even.

G^{−1}(x) = \begin{cases}\frac{x−q}{p} & if x is even \\ \frac{x−s}{r} & if x is odd \end{cases}

Case 2: q and s are odd.

G^{−1}(x) = \begin{cases}\frac{x−s}{r} & if x is even \\ \frac{x−q}{p} & if x is odd \end{cases}

Now we compute f(x) by computing (G ∘ T ∘ G^{−1})(x). Case 1: q and s are even.

(T ∘ G^{−1})(x) = \begin{cases}\frac{x−q}{2p} & if x is even \\ \frac{3x−3s+r}{2r} & if x is odd \end{cases}

Case 2: q and s are odd.

(T ∘ G^{−1})(x) = \begin{cases}\frac{3x−3s+r}{2r} & if x is even \\ \frac{x−q}{2p} & if x is odd \end{cases}

At this point the function becomes rather complicated, so we will employ a slight abuse of notation to express it more compactly.

(G∘T ∘G^{−1})(x) = \begin{cases}\frac{x+q}{2} & if x is even; q, s are even; \frac{x−q}{2} is even \\ \frac{rx−rq+2ps}{2p} & if x is even; q, s are even; \frac{x−q}{2} is odd \\ \frac{x+q}{2} & if x is odd; q, s are odd; \frac{x−q}{2} is even \\ \frac{rx−rq+2ps}{2p} & if x is odd; q, s are odd; \frac{x−q}{2} is odd \\ \frac{3px−3ps+pr+2qr}{2r} & if x is odd; q, s are even; \frac{3x−3s+r}{2} is even \\ \frac{3x−s+r}{2} & if x is odd; q, s are even; \frac{3x−3s+r}{2} is odd \\ \frac{3px−3ps+pr+2qr}{2r} & if x is even; q, s are odd; \frac{3x−3s+r}{2} is even \\ \frac{3x−s+r}{2} & if x is even; q, s are odd; \frac{3x−3s+r}{2} is odd \end{cases}

In particular, if we let r ≡ 1 mod 4 and q, s ≡ 0 mod 4 then the function may be simplified to

f(x) = \begin{cases}\frac{x+q}{2} & if x ≡ 0 mod 4 \\ \frac{3px−3ps+pr+2qr}{2r} & if x ≡ 1 mod 4 \\ \frac{rx−rq+2ps}{2p} & if x ≡ 2 mod 4 \\ \frac{3x−s+r}{2} & if x ≡ 3 mod 4. \end{cases}

Now we will show that this function is not, in general, a member of F. Let q = 0, s = 4, and p = r = 1. Then for all even x

f(x) = \begin{cases}\frac{x}{2} & if x ≡ 0 mod 4 \\ \frac{x+8}{2} & if x ≡ 2 mod 4. \end{cases}

If f ∈ F then f = f_{a,b,c,d} for some a, b, c, d ∈ ℤ_{2} where a, c and d are odd and b is even. Now, if x = 0 we have f(0) = 0 so f_{a,b,c,d}(0) = \frac{b}{2} = 0 so b = 0. If x = 4 then we have f(4) = 2 so f_{a,b,c,d}(4) = \frac{4a}{2} = 2 so a = 1. Now f(2) = \frac{2+8}{2} = 5 but f_{a,b,c,d}(2) = \frac{2}{2} = 1. So f(2) ≠ f_{a,b,c,d}(2) therefore f is not a member of F. Thus not all functions which are topologically conjugate to T by a piecewise linear map are members of F.

5 Acknowledgments

This paper is the result of work done in the Faculty/Student Research Program at the University of Scranton under the guidance of Dr. Ken Monks. I would like to thank Dr. Monks for his guidance and patience.

References

[FLW] C. Farruggia, M. Lawrence, and B. Waterhouse, The Elimination of a Family of Periodic Parity Vectors in the 3x+1 Problem, Pi Mu Epsilon Journal, Vol. 10 No. 4 (1996), 275-280.

[Fus] Fusaro, Marc, A Visual Representation of Sequence Space, to appear, Pi Mu Epsilon Journal.

[Jos] Joseph, John, A Chaotic Extension of the 3x+1 problem to ℤ_{2}[i], preprint.

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

[Ser] Serre, Jean-Pierre, A Course in Arithmetic, Springer-Verlag, (1973), ISBN: 0-387-90040-3.

University of Scranton Scranton, Pa. 18510 mjf1@uofs.edu