CYCLES FOR THE 3X+1 MAP ON THE GAUSSIAN INTEGERS

GINA I. KUCINSKI

Abstract. The Collatz Conjecture states that for every positive integer n, there exists a positive

integer k such that T^{(k)}(n) = 1, where T : ℤ^{+} → ℤ^{+} by T (n) = \{ \begin{matrix}\frac{n}{2} & if n is even \\ \frac{3n+1}{2} & if n is odd. \end{matrix} The

Finite Cycles Conjecture states that there are only finitely many distinct cycles for T extended to the set of integers. Using Joseph’s extension of T to the Gaussian integers, we prove that if z ∈ ℤ[i] is cyclic with extended-T -orbit \overline{z_{0,}z_{1}, ..., z_{n−1}} and parity vector \overline{v_{0,}v_{1}, ..., v_{n−1}}, where k = |{j | v_{j} = 1}| , l = |{j | v_{j} = i}| , and m = |{j | v_{j} = 1 + i}| , then

\frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2} ≤ n ≤ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{α} )}{ln 2}

when αβ > 0, where

α ≤ min {Re (z_{j}) | 0 ≤ j ≤ n − 1} ≤ max {Re (z_{j}) | 0 ≤ j ≤ n − 1} ≤ β. Using this result, we explore the existence of cycles for Joseph’s extension of T and determine all cycles having period less than or equal to 400. We also determine all cycles having parity vector of the form \overline{v_{0,}v_{1}, ..., v_{n−1}} with |\{j | v_{j} ≠ 0\}| ≤ 230 or |\{j | v_{j} = 0\}| ≤ 131.

1. Introduction

The 3x + 1 Conjecture, or Collatz Conjecture, traditionally attributed to Lothar Collatz of the University of Hamburg and dating back to the 1930s, involves the iteration of the function T : ℤ^{+} → ℤ^{+} by

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

The conjecture states that for every positive integer n, there exists a positive integer k such that T^{(k)}(n) = 1.

The T -orbit of a point z_{0} ∈ ℤ[i] is defined to be the sequence z_{0}, z_{1}, z_{2}, ... where

z_{j} = T (z_{j−1}) for all j ≥ 1.

We say a point z_{0} is cyclic if z_{0} = z_{j} for some j ≠ 0 and is eventually cyclic if z_{i} = z_{j} for some i ≠ j. If z_{0} is cyclic, we denote its T -orbit by \overline{z_{0}, z_{1}, ..., z_{n−1}} and say that \overline{z_{0}, z_{1}, ..., z_{n−1}} is a cycle with period or length n. We say that two cycles are equivalent if the sets containing the elements of their orbits are equal. For example, the cycle \overline{1, 2} is equivalent to \overline{2, 1}. In this paper, we will use the term distinct to describe a set of cycles in which none of the cycles are equivalent.

The Finite Cycles Conjecture, proposed by several authors, states that there are only finitely many distinct cycles for T : ℤ → ℤ, and the five distinct cycles starting from −17, −5, −1, 0, and 1 are believed to be the only such cycles [3].

Date: May 2000.

1991 Mathematics Subject Classification. Primary 39B12; Secondary 11B37, 58F08.

The function T can be extended to the 2-adic integers, ℤ_{2}, and further extended to ℤ_{2}[i] given by

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

where [x] denotes the equivalence class of x in ℤ_{2}[i]/2ℤ_{2}[i] [2]. Notice that T (ℤ[i]) ⊆ ℤ[i], the Gaussian integers, so that we may consider T : ℤ[i] → ℤ[i] as well, as we shall do for the remainder of the paper.

The following information regarding parity vectors may be found in [2].

The parity vector function for T, Q : ℤ_{2}[i] → ℤ_{2}[i], is given by the infinite sequence

Q(n) = v_{0}(n), v_{1}(n), v_{2}(n), ...

where

v_{j}(n) ∈ {0, 1, i, 1 + i}

and

v_{j}(n) ≡ T^{(j)}(n) mod 2 for all j ≥ 0.

(Note that Q is called Q_{∞} in [1], [2], and [3].)

Similarly, the parity vector function of length k for T, Q_{k} : ℤ_{2}[i] → ℤ_{2}[i]/2^{k}ℤ_{2}[i], is given by the sequence

Q_{k}(n) = v_{0}(n), v_{1}(n), v_{2}(n), ..., v_{k}(n).

Joseph shows that Q_{k} is periodic with period 2^{k} and that Q is a bijection. Thus, every z ∈ ℤ_{2}[i] has a unique parity vector and every element v ∈ ℤ_{2}[i] is the parity vector of some z ∈ ℤ_{2}[i], namely Q^{−1} (v) . In particular, we define a periodic parity vector as the parity vector of a cycle.

It is reasonable to ask if a conjecture analogous to the Finite Cycles Conjecture can be formulated concerning the existence of cycles for T on ℤ[i]. Determining all cycles for T on ℤ[i], or, equivalently, determining which periodic parity vectors are the parity vector of a cycle whose terms are Gaussian integers, would settle the original Finite Cycles Conjecture. Hence, studying the cycles for the extended function can have much to say about the original Collatz problem. By using the main theorem of this paper, we can determine all cycles having period less than or equal to 400 and all cycles having periodic parity vectors \overline{v_{0}, v_{1}, ..., v_{n−1}} such that t_{v} = |\{0 ≤ j ≤ n − 1 | v_{j} ≠ 0\}| ≤ 230 or n − t_{v} ≤ 131.

2. Main Results

The proofs of the theorems in this section will be discussed in a subsequent section of the paper. Let \overline{z_{0}, z_{1}, ..., z_{n−1}} be the T -orbit of z. Define min_{x}(z) = min \{Re(z_{j}) | 0 ≤ j ≤ n − 1\} and

max_{x}(z) = max \{Re(z_{j}) | 0 ≤ j ≤ n − 1\} . If v = \overline{v_{0}, v_{1}, ..., v_{n−1}} is the periodic parity vector of z, then let k_{v} = |{j | v_{j} = 1}| , l_{v} = |{j | v_{j} = i}| , m_{v} = |{j | v_{j} = 1 + i}| , and t_{v} = k_{v} + l_{v} + m_{v}. Thus, t_{v} represents the number of nonzero entries of v under its overbar. In this paper, we will substitute t, k, l, and m for t_{v}, k_{v}, l_{v}, and m_{v}, respectively, when v is clear from context.

We state the following theorem, our main result.

Theorem 1. Let α, β ∈ ℝ with αβ > 0 and let z ∈ ℤ[i] be cyclic and v its parity vector. If α ≤ min_{x}(z) ≤ max_{x}(z) ≤ β then

\frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2} ≤ n ≤ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{α})}{ln 2}.

From this, we can prove the following corollary.

Corollary 2. If 0 < α < β, then

\frac{ln 2}{ln (3 + \frac{1}{α})} ≤ \frac{t}{n} ≤ \frac{ln 2}{ln 3}.

If α < β < 0, then

\frac{ln 2}{ln 3} ≤ \frac{t}{n} ≤ \frac{ln 2}{ln (3 + \frac{1}{β} )}.

Notice that \frac{t}{n} represents the percentage of non-zero elements under the overbar of a periodic parity vector.

A set theoretic discrete dynamical system (or simply dynamical system, in this paper) is a pair (X, f) where X →^{f} X. If X →^{f} X is a dynamical system, then S ⊆ X is a subdynamical system of X if f(S) ⊆ S. In this situation, we will write S →^{f} S.

Two functions X →^{f} X and Y →^{g} Y are said to be set theoretically conjugate (or simply conjugate, in this paper) if there exists a bijection X →^{h} Y such that

X ⟶^{f} X
h ↓  ↓ h
Y ⟶_{g} Y

commutes, i.e. h ∘ f = g ∘ h. Conjugacy is an equivalence relation on any set of dynamical systems. There are several important subdynamical systems of T : ℤ[i] → ℤ[i]. Let

W_{1} = {x + yi | 0 < y < x}
W_{2} = {x + yi | 0 < x < y}
W_{3} = {x + yi | y < x < 0}
W_{4} = {x + yi | x < y < 0} .

Theorem 3. The following subsets of ℤ[i] are conjugate subdynamical systems of T : ℤ[i] → ℤ[i]:

(a) the real axis, the imaginary axis, and the y = x line.

(b) the second and fourth quadrants.

(c) W_{1} and W_{2}.

(d) W_{3} and W_{4}.

An important property of conjugacy is that it preserves the dynamics of a function. Here, we are concerned mainly with the preservation of cycles by conjugacy. Using this property, we need only examine one set from each of (a)-(d) above in order to determine all cycles. Our work is reduced further by the following two results.

Theorem 4. The following subsets of ℤ[i] contain no cyclic points for T : ℤ[i] → ℤ[i]:

(a) the second and fourth quadrants.

(b) {a − i | a ≤ −2} ∪ {−1 + ai | a ≤ −2} .

Combining the above results gives an efficient method for determining all cycles of a given period. Theorem 4(a) states that there are no cyclic points for T : ℤ[i] → ℤ[i] in the second and fourth quadrants. Thus, if we are in search of cycles, we need only look in the first and third quadrants (including the real and imaginary axes). However, by Theorem 3(c) and 3(d), we have that {x + yi | y < x} and {x + yi | x < y} are conjugate subdynamical systems in both the first and third quadrants. By Theorem 3(a), we know that the real axis, the imaginary axis, and the line y = x are conjugate subdynamical systems as well. Therefore, we need only look in {x + yi | 0 ≤ y < x} and {x + yi | x < y ≤ 0} in order to find cycles. If we determine that a point a + bi in one of these two sets is cyclic, then we know that the point b + ai is cyclic as well (and if b = 0, then a + ai is also cyclic). Furthermore, by Theorem 4(b), we have that there are no cyclic points for T : ℤ[i] → ℤ[i] in the two subsets {a − i | a ≤ −2} and {−1 + ai | a ≤ −2} of the third quadrant.

Given α ∈ ℤ^{+}, let I_{α} = [_{\frac{ln 2}{ln(3+ \frac{1}{α})}}, \frac{ln 2}{ln 3}] . Note that the interval I_{α} gets smaller as α gets larger and

that lim_{α→∞}_{\frac{ln 2}{ln(3+ \frac{1}{α})}} = \frac{ln 2}{ln 3}. Let N_{α} be the least positive integer such that \frac{j}{N_{α}} ∈ I_{α} for some j ∈ ℤ. If z

is a cyclic point with α ≤ min_{x} (z) , v = \overline{v_{0}, v_{1}, ..., v_{n−1}} the parity vector of z, and t = |\{j | v_{j} ≠ 0\}| , then by Corollary 2, \frac{t}{N_{α}} ∈ I_{α}. Then, n ≥ N_{α} by the definition of N_{α}. Conversely, if Re (z) > 0 and z is cyclic with period n < N_{α}, then 0 < min_{x} (z) < α.

Combining the results of the last two paragraphs, we find that in order to determine all cycles in the first quadrant having period less than N_{α} for a given α, we need only examine the finite set W_{α} = {x + yi | 0 < x < α and 0 ≤ y < x} . More specifically, we need only compute the first N_{α} terms in the T -orbit of all z ∈ W_{α} to completely determine all cycles in the first quadrant of period less than N_{α}.

This procedure for determining cycles is paralleled in the third quadrant. Here, we again use

Corollary 2 and let I_{β} = [\frac{ln 2}{ln 3}, _{\frac{ln 2}{ln(3+ \frac{1}{β})}}] . As in the first quadrant, it suffices to examine the finite

set W_{β} = {x + yi | β < x < 0 and x < y ≤ 0} to determine all cycles in the third quadrant having period less than N_{β}.

In order to determine all cycles having period less than or equal to 400, we must have N_{α} and N_{β} at least 401. The least value of α for which N_{α} ≥ 401 is α = 12825, in which case N_{α} = 401. The largest value of β such that N_{β} ≥ 401 is β = −8461, in which case N_{β} = 569. Using a Maple program, we computed the first 401 terms of the T -orbit for all z ∈ {x + yi | 0 < x < 12825 and 0 ≤ y < x} ∪ {x + yi | −8461 < x < 0 and x < y ≤ 0} , thus determining all cycles having period less than or equal to 400. Table 1 shows the distribution of all 77 such distinct cycles.

Period Number of Cycles
1  4
2  3
3  9
5  2
8  10
11  5
19  30
46  2
84  10
103  2

Table 1

In order to refer to individual cycles, we define a particular term in the cycle to be its representative as follows. For a + bi, c + di ∈ ℤ[i] define a + bi ≪ c + di if and only if |a| < |c| or (|a| = |c| and |b| < |d|) . For cycles whose terms are in W_{1} ∪ W_{4} ∪ ℤ, the representative is chosen to be the ≪-least term in the cycle. For other cycles, the representative is chosen to be the conjugate image of the representative of the cycle in W_{1} ∪ W_{4} ∪ ℤ that it corresponds to via the conjugacies of Theorem 3.

Figures 1 through 4 below show the distribution of the representatives of the cycles in ℤ[i]. Here, the plotted points and numbers indicate the representative elements of each cycle and their periods, respectively.

Figure 1: 1st Quadrant  Figure 2: 3rd Quadrant

Figure 3: a zoom of Figure 2  Figure 4: a zoom of Figure 3

In addition to determining cycles of a given period, we can use our main results to determine all cycles having a periodic parity vector of a given composition.

Corollary 5. Let z be cyclic with period n and parity vector v having either t_{v} ≤ 230 or n−t_{v} ≤ 131. Then n ≤ 400, so the cycle containing z is listed in Table 2.

The following table is a list of representative elements of each of the 77 distinct cycles found, the period of each cycle, and t_{v} where v is the parity vector of the cycle.

Cycle Rep. Period t_{v} Cycle Rep. Period t_{v}  Cycle Rep. Period t_{v}
0  1  0  15 + 13i  8  5  −109 − 87i  19 12
−i  1  1  19 + 9i  8  5 −110 − 105i  19 12
−1  1  1  −17i  11  7  −113 − 54i  19 12
−1 − i  1  1 −11 − 14i  11  7  −113 − 93i  19 12
i  2  1 −14 − 11i  11  7 −113 − 101i  19 12
1  2  1  −17  11  7  −115 − 81i  19 12
1 + 1i  2  1 −17 − 17i  11  7  −125 − 90i  19 12
−5i  3  2 −24 − 73i  19 12 −133 − 87i  19 12
−2 − 3i  3  2 −54 − 113i  19 12 −133 − 99i  19 12
−2 − 5i  3  2 −73 − 24i  19 12 −134 − 101i  19 12
−3 − 2i  3  2 −73 − 79i  19 12 −134 − 107i  19 12
−3 − 5i  3  2 −79 − 73i  19 12  42 + 59i  46 29
−5  3  2 −79 − 97i  19 12  59 + 42i  46 29
−5 − 2i  3  2 −81 − 115i  19 12 −461 − 527i  84 53
−5 − 3i  3  2 −87 − 109i  19 12 −527 − 461i  84 53
−5 − 5i  3  2 −87 − 133i  19 12 −903 − 1117i  84 53
2 + 3i  5  3 −90 − 125i  19 12 −907 − 934i  84 53
3 + 2i  5  3 −93 − 103i  19 12 −934 − 907i  84 53
4 + 15i  8  5 −93 − 113i  19 12 −1012 − 1033i 84 53
9 + 10i  8  5 −97 − 79i  19 12 −1033 − 1012i 84 53
9 + 19i  8  5 −99 − 133i  19 12 −1117 − 903i  84 53
10 + 9i  8  5 −101 − 113i 19 12 −1134 − 1511i 84 53
10 + 15i  8  5 −101 − 134i 19 12 −1511 − 1134i 84 53
13 + 15i  8  5 −103 − 93i  19 12 −187 − 234i  103 65
15 + 4i  8  5 −105 − 110i 19 12 −234 − 187i  103 65
15 + 10i  8  5 −107 − 134i 19 12

Table 2

3. Proofs of Main Results

We begin by proving our main result, which we will restate here for convenience.

Theorem 1. Let α, β ∈ ℝ with αβ > 0 and let z ∈ ℤ[i] be cyclic and v its parity vector. If α ≤ min_{x}(z) ≤ max_{x}(z) ≤ β then

\frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2} ≤ n ≤ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{α})}{ln 2}.

Proof. Let \overline{z_{0}, z_{1}, ..., z_{n−1}} be an n-cycle for T and v = \overline{v_{0}, v_{1}, ..., v_{n−1}} be its parity vector. Let 0 < α ≤ min_{x} (z_{0}) and z_{0} = x_{0} + y_{0}i.

If z = x + yi ∈ Z[i], then

T (x + yi) = \{ \begin{matrix}\frac{1}{2}x + \frac{1}{2}yi & if x, y even \\ (\frac{3}{2}x + \frac{1}{2}) + \frac{3}{2}yi & if x odd, y even \\ \frac{3}{2}x + (\frac{3}{2}y + \frac{1}{2}) i & if x even, y odd \\ (\frac{3}{2}x + \frac{1}{2}) + (\frac{3}{2}y + \frac{1}{2}) i & if x, y odd. \end{matrix}

Define

T_{0} (x + yi) = \frac{1}{2}x + \frac{1}{2}yi
T_{1} (x + yi) = (\frac{3}{2}x + \frac{1}{2}) + \frac{3}{2}yi
T_{i} (x + yi) = \frac{3}{2}x + (\frac{3}{2}y + \frac{1}{2}) i
T_{1+i} (x + yi) = (\frac{3}{2}x + \frac{1}{2}) + (\frac{3}{2}y + \frac{1}{2}) i.

Let j ∈ {0, 1, i, 1 + i} . Notice that the real parts of T_{j} (z) depend only on Re (z) = x. Define R_{j} (x) = Re (T_{j} (x + yi)) so that:

R_{j} (x) = Re (T_{j} (x + yi))
R_{0} (x) = \frac{1}{2}x
R_{1} (x) = \frac{3}{2}x + \frac{1}{2}
R_{i} (x) = \frac{3}{2}x
R_{1+i} (x) = \frac{3}{2}x + \frac{1}{2}.

Let U_{j} (x) = ω_{j}x with ω_{j} ∈ ℝ be an upper bound on R_{j} (x) for all x ≥ α. Thus,

Upper bound U_{j} (x) = ω_{j}x on R_{j} (x)
U_{0} (x) = \frac{1}{2}x
U_{1} (x) = ωx
U_{i} (x) = \frac{3}{2}x
U_{1+i} (x) = ωx

with ω = \frac{1}{2} (3 + \frac{1}{α}) . By the definition of cycle, we have

z_{0} = T_{v_{n−1}} ∘ T_{v_{n−2}} ∘ ... ∘ T_{v_{1}} ∘ T_{v_{0}} (z_{0}) .

8 GINA I. KUCINSKI

So,

x_{0} = Re (z_{0})
= Re (T_{v_{n−1}} ∘ T_{v_{n−2}} ∘ ... ∘ T_{v_{1}} ∘ T_{v_{0}} (z_{0}))
= R_{v_{n−1}} ∘ R_{v_{n−2}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0})  by definition of R_{j}.

Before we continue, we must prove the following lemma. Lemma 1. R_{v_{n−1}} ∘ R_{v_{n−2}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0}) ≤ U_{v_{n−1}} ∘ U_{v_{n−2}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0}) . Proof. We will show something stronger, namely

R_{v_{j}} ∘ R_{v_{j−1}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0}) ≤ U_{v_{j}} ∘ U_{v_{j−1}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0})

for all 0 ≤ j ≤ n − 1 by finite mathematical induction on j. Base Case: Let j = 0. Then, R_{v_{0}} (x_{0}) ≤ U_{v_{0}} (x_{0}) by construction since α ≤ min_{x} (z_{0}) ≤ x_{0}. Inductive Step: Assume

R_{v_{j}} ∘ R_{v_{j−1}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0}) ≤ U_{v_{j}} ∘ U_{v_{j−1}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0}) .

Then,

R_{v_{j+1}} ∘ R_{v_{j}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0}) = R_{v_{j+1}} [R_{v_{j}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0})]
≤ R_{v_{j+1}} [U_{v_{j}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0})]

(since R_{v_{j+1}} is an increasing map)

≤ U_{v_{j+1}} [U_{v_{j}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0})]

(since R_{v_{j+1}} (x) ≤ U_{v_{j+1}} (x) )

= U_{v_{j+1}} ∘ U_{v_{j}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0}) .

Therefore, by induction, R_{v_{n−1}} ∘ R_{v_{n−2}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0}) ≤ U_{v_{n−1}} ∘ U_{v_{n−2}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0}) .

Hence, we have

x_{0} = R_{v_{n−1}} ∘ R_{v_{n−2}} ∘ ... ∘ R_{v_{1}} ∘ R_{v_{0}} (x_{0})
≤ U_{v_{n−1}} ∘ U_{v_{n−2}} ∘ ... ∘ U_{v_{1}} ∘ U_{v_{0}} (x_{0})  by Lemma 1
= ω^{k} (\frac{3}{2})^{l} ω^{m} (\frac{1}{2})^{n−k−l−m} x_{0}  since U_{v_{i}} ∘ U_{v_{j}} (x) = U_{v_{j}} ∘ U_{v_{i}} (x)
= \frac{3^{l}}{2^{n}} · (3 + \frac{1}{α})^{k+m} x_{0}.

Since x_{0} > 0, we have

1 ≤ \frac{3^{l}}{2^{n}} · (3 + \frac{1}{α})^{k+m} .

Solving for n we obtain

n ≤ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{α})}{ln 2}.

By a similar argument, if 0 < max_{x} (z_{0}) ≤ β, we can show

\frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2} ≤ n.

Similarly, if α ≤ min_{x} (z_{0}) ≤ max_{x} (z_{0}) ≤ β < 0, we can show that the bounds on n are the same as those above. Therefore, if αβ > 0, then

\frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2} ≤ n ≤ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{α})}{ln 2}.

Using this result, we may now prove the following corollary.

Corollary 2. If 0 < α < β, then

\frac{ln 2}{ln (3 + \frac{1}{α})} ≤ \frac{t}{n} ≤ \frac{ln 2}{ln 3}.

If α < β < 0, then

\frac{ln 2}{ln 3} ≤ \frac{t}{n} ≤ \frac{ln 2}{ln (3 + \frac{1}{β} )}.

Proof. Let 0 < α < β. Then,

n ≥ \frac{l ln 3 + (k + m) ln (3 + \frac{1}{β} )}{ln 2}

by Theorem 1. So,

n ln 2 ≥ l ln 3 + (k + m) ln (3 + \frac{1}{β} )
≥ l ln 3 + (k + m) ln 3  since ln x is increasing and β > 0
= t ln 3.

Therefore,

\frac{t}{n} ≤ \frac{ln 2}{ln 3}.

Similarly, from the inequality n ≤ \frac{l ln 3+(k+m) ln(3+ \frac{1}{α})}{ln 2} we obtain

\frac{ln 2}{ln (3 + \frac{1}{α})} ≤ \frac{t}{n}.

We can prove the case α < β < 0 in a similar manner.

Theorem 3. The following subsets of ℤ[i] are conjugate subdynamical systems of T : ℤ[i] → ℤ[i]:

(a) the real axis, the imaginary axis, and the y = x line.

(b) the second and fourth quadrants.

(c) W_{1} and W_{2}.

(d) W_{3} and W_{4}.

Proof. Let

W_{5} = ℤ  (the real axis)
W_{6} = {zi | z ∈ ℤ}  (the imaginary axis)
W_{7} = {z + zi | z ∈ ℤ}  (the y = x line)
W_{8} = {x + yi | x ∈ ℤ^{−} and y ∈ ℤ^{+}} (the 2nd quadrant)
W_{9} = {x + yi | x ∈ ℤ^{+} and y ∈ ℤ^{−}} (the 4th quadrant).

Then it is elementary to verify that T (W_{j}) ⊆ W_{j} for all j, where 1 ≤ j ≤ 9. Therefore, W_{j} is a subdynamical system of T. Let

h_{1} : W_{5} → W_{6} by h_{1} (z) = zi,
h_{2} : W_{5} → W_{7} by h_{2} (z) = z + zi,

and for any x + yi ∈ ℤ[i] define h (x + yi) = y + xi. Then, it is an elementary, but tedious, exercise to show that h_{1}, h_{2}, and the restrictions of h to W_{1}, W_{3}, and W_{8} are conjugacies with h (W_{1}) = W_{2}, h (W_{3}) = W_{4}, and h (W_{8}) = W_{9}. We omit the proof.

We may now prove our next result.

Theorem 4. The following subsets of ℤ[i] contain no cyclic points for T : ℤ[i] → ℤ[i]:

(a) the second and fourth quadrants.

(b) {a − i | a ≤ −2} ∪ {−1 + ai | a ≤ −2} .

Proof. (a) Let U = {x + yi | x ∈ ℤ^{−}, y ∈ ℤ^{+}} and V = {x + yi | x ∈ ℤ^{+}, y ∈ ℤ^{−}} . Let x+yi ∈ V. Let r = |x + yi| so that x + yi = re^{i arctan(\frac{y}{x})}. Then,

T (re^{i arctan(\frac{y}{x})}) = \{ \begin{matrix}r_{1}e^{i arctan(\frac{y}{x})} & if x, y are even \\ r_{2}e^{i arctan(\frac{3y}{3x+1})} & if x odd, y even \\ r_{3}e^{i arctan(\frac{3y+1}{3x})} & if x even, y odd \\ r_{4}e^{i arctan(\frac{3y+1}{3x+1})} & if x, y odd \end{matrix}

for some r_{1}, r_{2}, r_{3}, and r_{4} in ℝ^{+}.

If x and y are both even, then arg (x + yi) = arg (T (x + yi)) . If x and y are not both even, then arg (T (x + yi)) = arctan (\frac{3y+ε_{2}}{3x+ε_{1}} ) for some ε_{1}, ε_{2} ∈ \{0, 1\} with ε_{1} + ε_{2} > 0. Then,

y < x
⟹ ε_{1}y < ε_{2}x
⟹ 3xy + ε_{1}y < 3xy + ε_{2}x
⟹ \frac{y}{x} < \frac{3y + ε_{2}}{3x + ε_{1}} .

Therefore, arctan (\frac{y}{x}) < arctan (\frac{3y+ε_{2}}{3x+ε_{1}} ) since arctan is an increasing map. This implies that arg (x + yi) < arg (T (x + yi)) for all x + yi such that x and y are not both even. Therefore, if z ∈ V, then arg (z) = arg (T (z)) if z ≡ 0 mod 2 and arg (z) < arg (T (z)) otherwise. By mathematical induction on n, we see that if z ∈ V, then arg (z) ≤ arg (T^{(n)} (z)) for all n.

Assume z ∈ V is cyclic of period n. Thus, n ≥ 1. Since z ≠ 0, the parity vector of z is not \overline{0}. Therefore, there exists a j such that T^{(j)} (z) ≢ 0 mod 2. So,

arg (T^{(j)} (z)) = arg (T^{(j+n)} (z))
= arg (T^{((n−1)+(j+1))} (z))
= arg (T^{(n−1)} (T^{(j+1)} (z)))
≥ arg (T^{(j+1)} (z))  since arg (z) ≤ arg (T^{(n)} (z))
> arg (T^{(j)} (z))  since arg (T (z)) > arg (z) when z ≢ 0 mod 2

which is a contradiction.

Therefore, z is not cyclic for all z ∈ V. Since U and V are conjugate subdynamical systems of T : ℤ[i] → ℤ[i] by Theorem 3(b) , then z is not cyclic for all z ∈ U. Therefore, there are no cyclic points for T in the second and fourth quadrants.

(b) Assume a − i is cyclic. Then, T^{(n)} (a − i) = a − i for some n ≥ 1. If a is even, then T (a − i) = \frac{3}{2}a − i. Since a < 0, 1 < \frac{3}{2} implies \frac{3}{2}a < a . Therefore, Re (T (a − i)) < Re (a − i) when a is even. If a is odd, then T (a − i) = \frac{3a+1}{2} − i. Since a < −1, we have 1 < −a ⇒ 1 < 2a − 3a ⇒ 3a + 1 < 2a ⇒ \frac{3a+1}{2} < a. Therefore, Re (T (a − i)) < Re (a − i) when a is odd. Thus, for all a ≤ −2, Re (T (a − i)) < Re (a − i) while Im (T (a − i)) = Im (a − i). Hence, there is no n such that T^{(n)} (a − i) = a − i and thus a − i is not cyclic for a ≤ −2. By a similar argument (or by the conjugacy h (x + yi) = y + xi), there are no cyclic points in {−1 + ai | a ≤ −2} .

We can use Corollary 2 to prove the following result.

Corollary 5. Let z be cyclic with period n and parity vector v having either t_{v} ≤ 230 or n−t_{v} ≤ 131. Then n ≤ 400, so the cycle containing z is listed in Table 2.

Proof. Let 0 < α ≤ min_{x} (z) ≤ max_{x} (z) ≤ β. It is easy to verify by direct calculation that the orbit of z enters a cycle listed in Table 2 for all z ∈ W_{1} ∪ ℤ^{+} such that Re (z) < 3. Thus we let α = 3. Hence, by Corollary 2, \frac{ln 2}{ln(\frac{10}{3})} ≤ \frac{t}{n}, so

n ≤ \frac{ln (\frac{10}{3})}{ln 2}t.

Also by Corollary 2, \frac{t}{n} ≤ \frac{ln 2}{ln 3}, so 1 − \frac{ln 2}{ln 3} ≤ 1 − \frac{t}{n} and therefore

n ≤ \frac{ln 3}{ln 3 − ln 2} (n − t) .

Now let α ≤ min_{x} (z) ≤ max_{x} (z) ≤ β < 0. It is easy to verify by direct calculation that the orbit of z either enters a cycle listed in Table 2 or is divergent by Theorem 4(b) for all z ∈ W_{4} ∪ ℤ^{−} such that Re (z) > −5. Thus we let β = −5. Hence, by Corollary 2, \frac{ln 2}{ln 3} ≤ \frac{t}{n}, so

n ≤ \frac{ln 3}{ln 2}t.

Also by Corollary 2, \frac{t}{n} ≤ _{\frac{ln 2}{ln(3+ \frac{1}{β})}}, so 1 − \frac{ln 2}{ln 2.8} ≤ 1 − \frac{t}{n} and therefore

n ≤ \frac{ln 2.8}{ln 2.8 − ln 2} (n − t) .

Let z ∈ W_{1} ∪ W_{4} ∪ ℤ be cyclic with period n. If −5 < min_{x} (z) < 3 then it is easy to verify by direct calculation that the cycle containing z is listed in Table 2. If min_{x} (z) is not between −5 and

3, then the inequalities above hold. In particular, either n ≤ \frac{ln 3}{ln 2}t or n ≤ \frac{ln(\frac{10}{3})}{ln 2}t, so in either case n ≤ \frac{ln(\frac{10}{3})}{ln 2}t. Hence, t ≤ 230 implies n < 400. Similarly, n ≤ \frac{ln 3}{ln 3−ln 2} (n − t) or n ≤ \frac{ln 2.8}{ln 2.8−ln 2} (n − t) , so in either case n ≤ \frac{ln 2.8}{ln 2.8−ln 2} (n − t) . Thus, n − t ≤ 131 implies n ≤ 400. Therefore, in every case, if t ≤ 230 or n − t ≤ 131, then the cycle containing z is listed in Table 2.

The approach of [1] for determining cycles utilized the parity vector function Q associated with T : ℤ_{2} → ℤ_{2}. The authors determined all integer cycles having periodic parity vector of the form v = \overline{\underbrace{000...0} 1}_{a zeros} by proving that Q^{−1} (v) was not an integer for a > 1. It is reasonable to ask if the

method and results of [1] can be extended to T : ℤ[i] → ℤ[i].

It is an elementary exercise to extend their method to T : ℤ[i] → ℤ[i] and in turn determine all cycles having periodic parity vector v, with t_{v} = 1. If the method of [1] could be generalized to arbitrary periodic parity vectors, then it would settle the Finite Cycles Conjecture. Using this method, we can, in fact, determine all cycles having periodic parity vector v, with t_{v} ≤ 3. However, this task becomes increasingly complicated as t_{v} increases. To illustrate, in order to determine all cycles having periodic parity vector of the form v = \overline{\underbrace{000...0}_{a zeros}p\underbrace{000...0}_{b zeros}q\underbrace{000...0}_{c zeros}r} where p, q, r ≠ 0 by the

method of [1], we first compute

Q^{−1} (v) = \frac{2^{a} (9ε_{1} + 3 · 2^{b+1}ε_{3} + 2^{b+c+2}ε_{5})}{2^{a+b+c+3} − 27} + \frac{2^{a} (9ε_{2} + 3 · 2^{b+1}ε_{4} + 2^{b+c+2}ε_{6})}{2^{a+b+c+3} − 27}i

where ε_{1} + ε_{2}i = p, ε_{3} + ε_{4}i = q, and ε_{5} + ε_{6}i = r. Then, we must determine which cases of a, b, c, and ε_{j}, with 1 ≤ j ≤ 6, imply Q^{−1} (v) ∈ ℤ[i]. This method seems to become intractably hard as t_{v} increases.

However, Theorem 1 and Corollary 2 are far more efficient for determining cycles for a given t_{v}. This efficiency is best illustrated by Corollary 5, resulting from our main Theorem and Corollary, which is used to determine all cycles having periodic parity vector v such that t_{v} ≤ 230 or n − t_{v} ≤ 131. This is clearly a vast improvement over the results obtained by the method discussed in the previous paragraph, which only determined all cycles having periodic parity vector v such that t_{v} ≤ 3.

4. Acknowledgment

This paper is the result of work completed under the direction of Dr. Kenneth G. Monks in the Faculty/Student Research Program at the University of Scranton. I thank Dr. Monks for his guidance and patience which he so greatly demonstrated throughout this project.

References

[1] Farruggia, C., Lawrence, M., and Waterhouse, B., The elimination of a family of periodic parity vectors in the 3x+1 problem, Pi Mu Epsilon J. 10, no. 4 (1996), 275-280.

[2] Joseph, J. A., A chaotic extension of the 3x + 1 function to ℤ_{2} [i] , Fibonacci Quart. 36.4 (Aug 1998), 309-316.

[3] Lagarias, J. C., The 3x + 1 problem and its generalizations, Am. Math. Monthly 92 (1985), 3-23.

University of Scranton Scranton, PA 18510 kucinski@bu.edu