THE AUTOCONJUGACY OF THE 3x + 1 FUNCTION

KENNETH G. MONKS AND JONATHAN YAZINSKI

Abstract. The 3x + 1 map T is defined on the 2-adic integers by T (x) = x/2 for even x and T (x) = (3x + 1) /2 for odd x and the 3x + 1 conjecture states that the T -orbit of any positive integer contains 1. We define and study properties of the unique nontrivial autoconjugacy Ω of T. This autoconjugacy sends x to the unique 2-adic integer whose parity vector is the one’s complement of the parity vector of x. We prove that if Ω maps rational numbers to rational numbers then there are no divergent T -orbits of positive integers. The map Ω is then used to restate the 3x+1 conjecture in a parity neutral form. We derive a necessary and sufficient condition for a cycle to be self conjugate and show that self conjugate cycles contain only positive elements. It is then shown that the only self-conjugate cycle of integers is {1, 2}. Finally, we prove that for any rational 2-adic integer x, \underline{lim} \frac{κ_{n}(x)}{n} + \overline{lim} \frac{κ_{n}(Ω(x))}{n} = 1 where κ_{n} (x) is the number of ones in the first n digits of the parity vector of x, and we use this along with generalizations of known restrictions on \underline{lim} \frac{κ_{n}(x)}{n} to prove most of the results in the paper.

1. Introduction

Let X be a topological space, f, g : X → X, and x ∈ X. The f-orbit of x is the infinite sequence

x, f (x) , f^{2} (x) , f^{3} (x) , …

where f^{k} = f ∘ f^{k−1}for all k ≥ 1 and f^{0} is the identity map. Define O_{f} (x) = {f^{k} (x) : k ∈ ℕ} . The f-orbit of x, x itself, and O_{f} (x) are all said to be eventually cyclic if O_{f} (x) is finite and divergent otherwise. If f^{k} (x) = x for some k ≥ 1 then O_{f} (x) is called an f-cycle and in this case we say x is cyclic. Maps f and g are conjugate with conjugacy h if and only if there exists a bijective homeomorphism h : X → X such that g ∘ h = h ∘ f. Conjugacy is an equivalence relation on the set of maps from X to X. The set of autoconjugacies of f forms a group under composition called Aut (f) .

Let ℤ_{2} denote the ring of 2-adic integers and define T : ℤ_{2} → ℤ_{2} by

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

In this terminology we have the famous

3x + 1 Conjecture: The T -orbit of any positive integer contains 1.

The shift map, σ : ℤ_{2} → ℤ_{2}, is defined by

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

Date: July 10, 2002. 1991 Mathematics Subject Classification. Primary 11B75 . Key words and phrases. 3x+1 problem, conjugacy, Collatz problem.

Lagarias [4] proved that T is conjugate to σ with conjugacy the parity vector map^{1} Φ^{−1} : ℤ_{2} → ℤ_{2} defined by Φ^{−1} (x) = ∑_{k=0}^{∞} (T^{k} (x) Mod 2) · 2^{k} where

a Mod 2 = \{ \begin{matrix}0 & if a is even \\ 1 & if a is odd \end{matrix} .

If x ∈ ℤ_{2} then Φ^{−1} (x) is called the parity vector of x. Bernstein [1] gives an explicit formula for the inverse conjugacy Φ, namely,

(1.1)  Φ (2^{d_{0}} + 2^{d_{1}} + 2^{d_{2}} + ⋯) = − ∑_{i} \frac{1}{3^{i+1}} 2^{d_{i}}

whenever 0 ≤ d_{0} < d_{1} < d_{2} < ⋯ is a finite or infinite sequence of natural numbers.

Hedlund [6] proved that Aut (σ) = {id, V } with respect to the standard 2-adic metric topology where id is the identity map and V (x) = −1 − x. If we define

Ω := Φ ∘ V ∘ Φ^{−1}

it follows immediately that

Aut (T) = {id, Ω} .

Thus Ω is the unique nontrivial autoconjugacy of the 3x + 1 map. Hence Ω ∘ T = T ∘ Ω and Ω^{2} = id.

The purpose of this paper is to describe some relationships between the map Ω and the 3x + 1 problem. In the next section we state our main results and illustrate their implications without proof. In Section 3 we provide some background on the qualitative behavior of the T -orbits of rational 2-adic integers. The proofs of theorems stated in Section 2 are then provided in Section 4.

2. Main Results

Let x ∈ ℤ_{2}. It can be expressed uniquely as a 0, 1-valued infinite sequence x_{0}x_{1}x_{2}x_{3} ⋯ where x_{k} = (σ^{k} (x) Mod 2) so that x = ∑_{k=0}^{∞} x_{k} ·2^{k}. We refer to this sequence as the binary representation of x.

Let ℚ_{odd} be the set of rational numbers which have an odd denominator in reduced fraction form^{2}. The elements of ℚ_{odd} are ordered by the usual relation < on ℚ ⊆ ℝ. It is well known that ℚ_{odd} is isomorphic to the subring of ℤ_{2} consisting of those 2-adic integers whose binary representation is eventually periodic, i.e. those which are eventually cyclic for σ. Since T and σ are conjugate and conjugacies map eventually cyclic points to eventually cyclic points, the parity vector of x is rational if and only if x is eventually cyclic for T. Furthermore, as eventually cyclic elements x satisfy T^{k} (x) = T^{j} (x) for some k, j with k ≠ j, they are the root of a linear polynomial with rational coefficients and so must be rational. Thus Φ (ℚ_{odd}) ⊆ ℚ_{odd}.

The binary representations of Φ^{−1} (x), σ (x), and V (x), can be easily described as follows: Φ^{−1} (x) = y_{0}y_{1}y_{2}y_{3} ⋯ where y_{k} = (T^{k} (x) Mod 2) for all k ∈ ℕ, σ (x) = x_{1}x_{2}x_{3} ⋯, and V (x) = x_{0}^{∗}x_{1}^{∗}x_{2}^{∗}x_{3}^{∗} ⋯ where 0^{∗} = 1 and 1^{∗} = 0. Thus the binary representation of Φ^{−1} (x) is obtained from the T -orbit of x by replacing each term with its value Mod 2, the shift map removes the leading binary digit of x, and V maps x to the 2-adic integer whose binary representation is the one’s complement of the binary representation of x.

Consequently the autoconjugacy Ω can be thought of in this way: Ω maps a 2-adic integer x to the unique 2-adic integer Ω (x) whose parity vector is the one’s complement of the parity vector of x. In other words, all corresponding terms in the T -orbits of x and Ω (x) have opposite parity.

1The map Φ^{−1} is called Q_{∞} in [4]

2ℚ_{odd} is called ℚ [(2)] in [5].

Example 1. The T -orbit of −11/3 is

−\frac{11}{3}, \overline{−5, −7, −10}

(where the overbar denotes a periodic sequence) and the T -orbit of 8/5 is

\frac{8}{5}, \overline{\frac{4}{5}, \frac{2}{5}, \frac{1}{5}}.

Since the corresponding terms of these orbits have opposite parity, by uniqueness we conclude that Ω (−11/3) = 8/5.

Example 2. Suppose we wish to compute Ω (3). Notice that the T -orbit of 3 is

3, 5, 8, 4, \overline{2, 1}

so that Φ^{−1} (3) = 1100\overline{01} and its one’s complement is V ∘ Φ^{−1} (3) = 0011\overline{10}. By (1.1) we obtain

Ω (3) = Φ ∘ V ∘ Φ^{−1} (3) = Φ (0011\overline{10}) = −\frac{4}{9}

whose T -orbit is

−\frac{4}{9}, −\frac{2}{9}, −\frac{1}{9}, \frac{1}{3}, \overline{1, 2}.

It is well known that the 3x+1 Conjecture is equivalent to the conjunction of the two conjectures:

Divergent Orbits Conjecture: No positive integer has a divergent T -orbit.

Nontrivial Cycles Conjecture: The only T -cycle of positive integers is {1, 2}.

Bernstein and Lagarias [2] have shown that the Divergent Orbits Conjecture is implied by their

Periodicity Conjecture: Φ^{−1} (ℚ_{odd}) ⊆ ℚ_{odd}.

Since Φ (ℚ_{odd}) ⊆ ℚ_{odd} and V (ℚ_{odd}) = ℚ_{odd}, the Periodicity Conjecture implies that Ω (ℚ_{odd}) = Φ ∘ V ∘ Φ^{−1} (ℚ_{odd}) ⊆ ℚ_{odd}. For this reason we are led to make the

Autoconjugacy Conjecture: Ω (ℚ_{odd}) ⊆ ℚ_{odd}.

Our first result is that the latter two conjectures are equivalent to a strong form of the Divergent Orbits Conjecture.

Theorem 2.1. The following are equivalent.

(a) The Periodicity Conjecture.

(b) The Autoconjugacy Conjecture.

(c) No rational 2-adic integer has a divergent T -orbit.

Furthermore, the statement Ω (ℤ^{+}) ⊆ ℚ_{odd} is equivalent to the Divergent Orbits Conjecture.

Thus in particular, the Autoconjugacy Conjecture implies the Divergent Orbits Conjecture, i.e. if Ω (x) is rational for every rational 2-adic integer x then there are no divergent T -orbits of positive integers.

It is also possible to restate the 3x + 1 Conjecture in terms of Ω. Define ξ : ℤ_{2} → ℤ_{2} by

ξ (x) = \{ \begin{matrix}\frac{x}{2} & if x is even \\ Ω (x) & if x is odd \end{matrix}

for all x ∈ ℤ_{2}.

Also define a relation ∼ on ℤ_{2} by

x ∼ y ⇔ (x = y or x = Ω (y))

for all x, y ∈ ℤ_{2}. It is easy to verify that ∼ is an equivalence relation on ℤ_{2} and that

ℤ_{2}/ ∼ = {{x, Ω (x)} : x ∈ ℤ_{2} and x is odd}

i.e. the equivalence classes are two element sets containing one odd 2-adic integer and one even 2adic integer that are Ω-conjugates of each other. For example, {−11/3, 8/5} is one such equivalence class (see Example 1). We write [x] as an abbreviation for {x, Ω (x)} , i.e. [x] denotes the equivalence class of x. For example, Ω (1) = 2 so that we have [1] = {1, 2} = [2]. Since Ω (T (x)) = T (Ω (x)), the map T induces a well defined map Ψ : ℤ_{2}/ ∼ → ℤ_{2}/ ∼ by Ψ ([x]) = [T (x)] for all x ∈ ℤ_{2}.

We can restate the 3x + 1 Conjecture in terms of both ξ and the induced map Ψ.

Theorem 2.2. The following are equivalent.

(a) The T -orbit of any positive integer contains 1.

(b) The ξ-orbit of any positive integer contains 1.

(c) The Ψ-orbit of the class of any positive integer contains [1].

Define T_{0} (x) = x/2 and T_{1} (x) = (3x + 1) /2 so that

T (x) = \{ \begin{matrix}T_{0} (x) & if x is even \\ T_{1} (x) & if x is odd. \end{matrix}

In this notation Theorem 2.2 (b) says that we can replace T_{1} by Ω in the definition of T, and an equivalent conjecture is obtained.

Example 3. The T -orbit of 3 is

3, 5, 8, 4, \overline{2, 1}

while the ξ-orbit of 3 is

3, −4/9, −2/9, −1/9, 8, 4, \overline{2, 1}

and the Ψ-orbit of [3] is

\{3, −\frac{4}{9}\} , \{−\frac{2}{9}, 5\} , \{−\frac{1}{9}, 8\} , \{4, \frac{1}{3}\} , \overline{\{2, 1\}}

The map Ψ is a parity neutral version of the 3x + 1 map in the following sense. Let z ∈ ℤ_{2}/ ∼. Then z = {a, b} for some a, b ∈ ℤ_{2} with a even and b odd. Hence Ψ (z) = {T_{0} (a) , T_{1} (b)}. Consequently each iteration of Ψ uses both branches of the 3x + 1 map simultaneously. Thus Ψ completely eliminates parity considerations but at the same time encodes the essential dynamics of T in the sense of Theorem 2.2.

In light of Theorems 2.1 and 2.2 we would very much like to understand the properties of the map Ω. In particular it would be quite valuable to have an explicit formula for the binary representation of Ω (x) in terms of the binary representation of x. Still, there are some properties of Ω which can be obtained without an explicit formula.

Since a conjugacy preserves cycles, Ω maps any cycle to another cycle. We say that a T -cycle C is self conjugate if Ω (C) = C. For example, {1, 2} is a self-conjugate T -cycle. We can determine all self-conjugate T -cycles by describing their parity vectors.

Theorem 2.3. A T -cycle C is self conjugate if and only if C = O_{T} (x) where

x = Φ (\overline{v_{0}v_{1} ⋯ v_{k}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k}^{∗}})

for some v_{0}, v_{1}, …, v_{k} ∈ {0, 1} .

Example 4. To illustrate the theorem, start with any finite binary sequence, e.g. 11, and catenate its one’s complement:

111^{∗}1^{∗} = 1100.

Extend this to a periodic sequence, \overline{1100}, and compute x = Φ (\overline{1100}) = 5/7 by (1.1). Then by Theorem 2.3 the T -orbit of 5/7 is self conjugate. Indeed O_{T} (\frac{5}{7}) = \{\frac{5}{7}, \frac{11}{7}, \frac{20}{7}, \frac{10}{7}\} and Ω (5/7) = 20/7. Table 1 lists all self conjugate cycles having ten elements or less.

Table 1: Self Conjugate T -cycles with ten elements or less

\{1, 2\}  \{\frac{13}{35}, \frac{37}{35}, \frac{73}{35}, \frac{127}{35}, \frac{208}{35}, \frac{104}{35}, \frac{52}{35}, \frac{26}{35}\}
\{\frac{5}{7}, \frac{11}{7}, \frac{20}{7}, \frac{10}{7}\}  \{\frac{211}{781}, \frac{707}{781}, \frac{1451}{781}, \frac{2567}{781}, \frac{4241}{781}, \frac{6752}{781}, \frac{3376}{781}, \frac{1688}{781}, \frac{844}{781}, \frac{422}{781}\}
\{\frac{19}{37}, \frac{47}{37}, \frac{89}{37}, \frac{152}{37}, \frac{76}{37}, \frac{38}{37}\}  \{\frac{373}{781}, \frac{950}{781}, \frac{475}{781}, \frac{1103}{781}, \frac{2045}{781}, \frac{3458}{781}, \frac{1729}{781}, \frac{2984}{781}, \frac{1492}{781}, \frac{746}{781}\}
\{\frac{17}{25}, \frac{38}{25}, \frac{19}{25}, \frac{41}{25}, \frac{74}{25}, \frac{37}{25}, \frac{68}{25}, \frac{34}{25}\} \{\frac{383}{781}, \frac{965}{781}, \frac{1838}{781}, \frac{919}{781}, \frac{1769}{781}, \frac{3044}{781}, \frac{1522}{781}, \frac{761}{781}, \frac{1532}{781}, \frac{766}{781}\}

One immediate consequence of Theorem 2.3 is that any self conjugate cycle must have an even number of elements. Notice also that all of the cycles listed in Table 1 contain only positive elements. This is not a coincidence as indicated by the following theorem. Let ℚ_{odd}^{+} = ℚ_{odd} ∩ (0 … ∞).

Theorem 2.4. If C is a self conjugate T -cycle then C ⊆ ℚ_{odd}^{+}, i.e. any self conjugate T -cycle contains only positive rational entries.

Given that {1, 2} is a self conjugate cycle of positive integers, one might ask if an analogue of the Nontrivial Cycles Conjecture holds for self conjugate cycles. We answer this question in the affirmative with the following theorem.

Theorem 2.5. For any self conjugate T -cycle C

min (C) ≤ 1 < max (C) .

Hence, the only self conjugate T -cycle of integers is {1, 2}.

In other words, all self conjugate T -cycles must contain an element that is less than or equal to 1 and another that is greater than 1. Thus if one could show, for example, that any cycle of positive integers must be self-conjugate, it would prove the Nontrivial Cycles Conjecture.

Example 5. For the five known integer T -cycles, the cycles {0} and {−1} are Ω-conjugates of each other, {1, 2} is self conjugate, and we have

Ω (\{−5, −7, −10\}) = \{\frac{4}{5}, \frac{2}{5}, \frac{1}{5}\},

and

Ω ({−17, −25, −37, −55, −82, −41, −61, −91, −136, −68, −34})
= \{\frac{5296}{1967}, \frac{2648}{1967}, \frac{1324}{1967}, \frac{662}{1967}, \frac{331}{1967}, \frac{1480}{1967}, \frac{740}{1967}, \frac{370}{1967}, \frac{185}{1967}, \frac{1261}{1967}, \frac{2875}{1967}\}.

The key idea behind the proofs of most of these results is that the sizes of the elements in the T -orbit of a rational number are restricted by the limiting ratio of odd elements to all elements in the finite initial subsequences of the orbit. More precisely, let x ∈ ℚ_{odd} and n ∈ ℕ^{+}. Define κ_{n} (x) = ∑_{i=0}^{n−1} (T^{i} (x) Mod 2), i.e. κ_{n} (x) is the number of ones in the first n digits of the parity vector of x.^{3} Since the parity vector of Ω (x) is the one’s complement of the parity vector of x, we have the following obvious but useful relationship

(2.1)  κ_{n} (x) + κ_{n} (Ω (x)) = n.

3κ_{n} (x) is called N^{∗} (n) in [4].

Dividing this by n gives us

(2.2)  \frac{κ_{n} (x)}{n} + \frac{κ_{n} (Ω (x))}{n} = 1

which says that the percentage of ones in the first n digits of the parity vectors of x and Ω (x) must sum to 1. However, it is easy to see that if a_{0}, a_{1}, … is any sequence of rational numbers in [0 … 1] then \underline{lim} a_{n} + \overline{lim} (1 − a_{n}) = 1, so we have

Theorem 2.6. Let x ∈ ℤ_{2}. Then

\underline{lim}\frac{κ_{n} (x)}{n} + \overline{lim}\frac{κ_{n} (Ω (x))}{n} = 1.

However, we have restrictions on these percentages for the T -orbits of rational numbers. For the remainder of the paper “orbits” refers to “T -orbits” and O (x) means O_{T} (x).

Eliahou [3, Thm 2.1] proved that if O (x) is a cycle, m = min O (x) , M = max O (x) , and p = |O (x)| then

(2.3)  \frac{ln 2}{ln (3 + \frac{1}{m})} ≤ \frac{κ_{p} (x)}{p} ≤ \frac{ln 2}{ln (3 + \frac{1}{M} )}.

In [4, equation (2.31)] Lagarias states that ln(2) ln(3) ≤ \underline{lim}\frac{κ_{n}(x)}{n} for integers x whose orbit diverges to ±∞. We will show that this inequality also holds for any divergent x ∈ ℚ_{odd} as well. The situation can be summarized as follows.

Theorem 2.7. Let x ∈ ℚ_{odd}.

(a) If the orbit of x is eventually cyclic then lim_{n→∞} \frac{κ_{n}(x)}{n} exists and

\frac{ln 2}{ln (3 + \frac{1}{m})} ≤ lim_{n→∞} \frac{κ_{n} (x)}{n} ≤ \frac{ln 2}{ln (3 + \frac{1}{M} )}

where m, M are the least and greatest cyclic elements in O (x).

(b) If the orbit of x is divergent then

\frac{ln 2}{ln 3} ≤ \underline{lim}\frac{κ_{n} (x)}{n}.

Combining this theorem with Theorem 2.6 allows us to prove most of the results in this paper. Thus a study of the properties of Ω reveals some essential features of the 3x + 1 map and shows

that further investigation of this interesting underlying duality can lead to important conclusions about the 3x + 1 problem itself.

3. Basic Facts about Rational Orbits

In this section we derive some useful lemmas that describe the qualitative behavior of the T -orbits of rational numbers. These facts will be required for the proofs in the next section.

We begin with the elementary fact that T maps positive rationals to themselves and cannot introduce new factors into the denominator.

Lemma 3.1. Let h be an odd positive integer. Then (a) T (\frac{1}{h}ℤ) ⊆ \frac{1}{h}ℤ.

(b) T (ℚ_{odd}^{+}) ⊆ ℚ_{odd}^{+}.

Proof: (a) Let h = 2j + 1 for some j ∈ ℕ. Let x ∈ T (\frac{1}{h}ℤ) . Then x = T (\frac{a}{h}) for some a ∈ ℤ. If a is even, then a = 2k for some k ∈ ℤ and so

x = T (\frac{a}{h}) = T (\frac{2k}{h} ) = \frac{k}{h} ∈ \frac{1}{h}ℤ.

If a is odd then a = 2k + 1 for some k ∈ ℤ and so

x = T (\frac{a}{h}) = \frac{3 (\frac{a}{h}) + 1}{2} = \frac{3 (\frac{2k+1}{h}) + \frac{h}{h}}{2} = \frac{6k + 3 + h}{2h}

= \frac{6k + 3 + 2j + 1}{2h} = \frac{6k + 2j + 4}{2h} = \frac{3k + j + 2}{h} ∈ \frac{1}{h}ℤ.

So in both cases, x ∈ \frac{1}{h}ℤ. Thus T (\frac{1}{h}ℤ) ⊆ \frac{1}{h}ℤ.

(b) Let x ∈ T (ℚ_{odd}^{+}) . Then x = T (y) for some y ∈ ℚ_{odd}^{+}. So y > 0 and x = y/2 if y is even and x = \frac{3y+1}{2}if y is odd. Thus x > 0 and x ∈ ℚ_{odd}, so x ∈ ℚ_{odd}^{+}. Hence T (ℚ_{odd}^{+}) ⊆ ℚ_{odd}^{+}.

♢

Thus for any x, if x ∈ \frac{1}{h}ℤ (respectively ℚ_{odd}^{+}) then O (x) ⊆ \frac{1}{h}ℤ (respectively ℚ_{odd}^{+}). Note that in addition to having ℚ_{odd} ⊆ ℤ_{2} we also have ℚ_{odd} ⊆ ℝ. Using the previous Lemma it is easy to see that the orbit of a rational number can only have finitely many distinct values in any bounded real interval, [a … b] := {x ∈ ℝ : a ≤ x ≤ b}, i.e. we immediately have the following lemma.

Lemma 3.2. Let x ∈ ℚ_{odd} and a, b ∈ ℝ. Then O (x) ∩ [a … b] is finite.

Thus the T -orbit of a rational number cannot have any accumulation points in ℝ. From this we immediately obtain the following corollary.

Corollary 3.3. Let x ∈ ℚ_{odd}.

(a) O (x) is bounded if and only if the T -orbit of x is eventually cyclic.

(b) If O (x) has a lower bound then it has a minimum value.

(c) If O (x) has an upper bound then it has a maximum value.

Lemma 3.1 also allows us to classify the T -orbits of rational numbers. We say the orbit of x is strictly positive (respectively strictly nonnegative, strictly negative) if every element of O (x) is positive (respectively nonnegative, negative). The following lemma shows that the orbit of every rational number x is either strictly positive, strictly negative, or eventually strictly nonnegative.

Lemma 3.4. Let x ∈ ℚ_{odd}.

(a) If x > 0 then O (x) is strictly positive.

(b) If −1 < x ≤ 0 then O (x) is eventually strictly nonnegative.

(c) If O (x) is strictly negative then x ≤ −1 and O (x) ⊆ (−∞ … − 1].

Proof: The proof of part (a) follows immediately from Lemma 3.1 (b). Part (c) follows immediately from parts (a) and (b) as it is the only remaining possibility. That leaves us with the task of proving part (b).

Let x ∈ ℚ_{odd} and −1 < x ≤ 0. If x = 0 the statement is trivially true. Assume −1 < x < 0. Notice that T (0) = 0 and T (−1) = −1 so that the binary representations of the parity vectors of 0 and −1 are \overline{0} and \overline{1} respectively. Thus the T -orbit of every number other than 0 and −1 contains both odd and even terms, because the parity vector function Φ^{−1} is a conjugacy and hence a bijection. We have three cases.

If x ∈ (−\frac{1}{4} … 0) then −\frac{1}{8} < \frac{x}{2} < 0 and \frac{1}{8} < \frac{3x+1}{2}. Thus T maps even numbers in (−\frac{1}{4} … 0) to numbers in (−\frac{1}{4} … 0) and T maps odd numbers in (−\frac{1}{4} … 0) to a positive number. Since the T -orbit of x must contain an odd number, it must also contain a positive number.

On the other hand, if x ∈ (−\frac{1}{2} … 0) then −\frac{1}{4} < \frac{x}{2} and −\frac{1}{4} < \frac{3x+1}{2}. Thus T (x) ∈ (−\frac{1}{4} … ∞) and so the T -orbit of x has a nonnegative element by the previous case.

Finally, if x ∈ (−1 … ∞) then −1 < \frac{3x+1}{2} and −\frac{1}{2} < \frac{x}{2}. Thus T maps odd numbers greater than −1 to a number greater than −1 and T maps even numbers greater than −1 to a number greater than −\frac{1}{2}. Since the T -orbit of x must contain an even number, it must also contain a nonnegative number by the previous case.

Thus for any rational x > −1 the T -orbit of x contains a nonnegative number. Since 0 is a fixed point and positive numbers map to positive numbers by Lemma 3.1, O (x) is eventually strictly nonnegative.

♢

4. Proofs of Theorems in Section 2

We now use the results of Section 3 to prove the results stated in Section 2. We first prove Theorem 2.7 and Theorem 2.6 as they are required for some of the other proofs. After that we prove Theorems 2.1, 2.2, 2.3, 2.4, and 2.5 in that order.

4.1. The Proof of Theorem 2.7. We break this proof down into a sequence of Lemmas. First we prove the intuitively clear fact that the lim inf of the sequence formed by taking the ratio of odd elements to all elements in the first n terms of the orbit of x will not change if x is replaced by any T -iterate of x.

Lemma 4.1. Let x ∈ ℚ_{odd}. For any j ∈ ℕ,

\underline{lim}\frac{κ_{n} (T^{j} (x))}{n} = \underline{lim}\frac{κ_{n} (x)}{n}.

Proof: Let x ∈ ℚ_{odd} and j ∈ ℕ. Define ω = ∑_{k=0}^{j−1} (T^{k} (x) Mod 2) and define L_{1} = \underline{lim}\frac{κ_{n}(x)}{n}

and L_{2} = \underline{lim}\frac{κ_{n}(T^{j}(x))}{n}. Note that L_{1}, L_{2} ∈ [0 … 1] as both sequences are bounded below by 0 and above by 1. Then for n > j

\frac{κ_{n} (x)}{n} = \frac{∑_{k=0}^{n−1} (T^{k} (x) Mod 2)}{n}

= \frac{∑_{k=0}^{j−1} (T^{k} (x) Mod 2) + ∑_{k=j}^{n−1} (T^{k} (x) Mod 2)}{n}

= \frac{ω}{n} + \frac{∑_{k=0}^{n−j−1} (T^{j+k} (x) Mod 2)}{n}

= \frac{ω}{n} + (\frac{n − j}{n} ) \frac{κ_{n−j} (T^{j} (x))}{n − j}.

Notice \frac{ω}{n} → 0 and \frac{n−j}{n} → 1 as n → ∞, so that applying \underline{lim} to both sides of this equation proves the result.

♢

The next Lemma proves an inequality similar to (2.3) for arbitrary positive rational 2-adic integers.

Lemma 4.2. Let x ∈ ℚ_{odd} with O (x) strictly positive and let 0 < m ≤ min O (x). Then

\frac{ln 2}{ln (3 + \frac{1}{m})} ≤ \underline{lim}\frac{κ_{n} (x)}{n}.

Proof: Let x_{0} ∈ ℚ_{odd} with O (x_{0}) strictly positive. O (x_{0}) is bounded below by 0 so min O (x_{0}) exists by Corollary 3.3 (b). Let 0 < m ≤ min (O (x_{0})). Let v = Φ^{−1}(x_{0}) be the parity vector of x_{0}. Let v = v_{0}v_{1}v_{2} … be the binary representation of v where v_{i} ∈ {0, 1}. Define maps w_{0}, w_{1} from ℝ to itself by w_{0} (x) = T_{0} (x) = \frac{x}{2}, and w_{1} (x) = (\frac{3+ \frac{1}{m}}{2} ) x. Define w ⟨0⟩ = x_{0} and w ⟨k⟩ = w_{v_{k−1}} ∘ ⋯ ∘ w_{v_{0}} (x_{0}) for all k ∈ ℕ^{+}.

For any x ∈ ℚ_{odd}, if m ≤ x then

w_{1} (x) − T_{1} (x) = (\frac{3 + \frac{1}{m}}{2} ) x − \frac{3x + 1}{2}

= \frac{1}{2} \frac{(x − m)}{m}

≥ 0.

Thus T_{1} (x) ≤ w_{1} (x). Since w_{0} (x) = T_{0} (x) we have shown

(4.1)  ∀x ∈ ℚ_{odd}, m ≤ x ⇒ T_{0} (x) = w_{0} (x) and T_{1} (x) ≤ w_{1} (x) .

We now show that w ⟨k⟩ ≥ T^{k} (x_{0}) for all k ∈ ℕ by induction on k. For the base case we note that w ⟨0⟩ = x_{0} = T^{0} (x_{0}) ≥ T^{0} (x_{0}) . Let k ∈ ℕ and assume that w ⟨k⟩ ≥ T^{k} (x_{0}). Then

w ⟨k + 1⟩ = w_{v_{k}} (w ⟨k⟩)
≥ w_{v_{k}} (T^{k} (x_{0})) because w_{v_{k}} is an increasing function
≥ T_{v_{k}} (T^{k} (x_{0})) by (4.1) since T^{k} (x_{0}) ≥ m
= T^{k+1} (x_{0}) .

So for all k ∈ ℕ, w ⟨k⟩ ≥ T^{k} (x_{0}) .

Let n ∈ ℕ^{+} and define κ = κ_{n} (x_{0}) . Then we have

m ≤ T^{n} (x_{0})

≤ w ⟨n⟩

= (\frac{3 + \frac{1}{m}}{2} )^{κ} (\frac{1}{2})^{n−κ} x_{0}

= \frac{(3 + \frac{1}{m})^{κ}}{2^{n}} x_{0}.

Taking logarithms of both sides of this inequality yields

\frac{ln 2}{ln (3 + \frac{1}{m})} − ω \frac{1}{n} ≤ \frac{κ}{n}

where ω = ln(\frac{x_{0}}{m})_{ln(3+ \frac{1}{m})}. But ω \frac{1}{n} → 0 as n → ∞ so that

∀ε > 0, ∃N > 0, ∀n > N, \frac{ln 2}{ln (3 + \frac{1}{m})} − ε ≤ \frac{κ_{n} (x_{0})}{n}

Hence _{\frac{ln 2}{ln(3+ \frac{1}{m})}} ≤ \underline{lim}\frac{κ_{n}(x_{0})}{n}.

♢

Using a similar argument, we can prove an inequality similar to Theorem 2.7 (b) for arbitrary strictly negative orbits.

Lemma 4.3. Let x ∈ ℚ_{odd} with O (x) strictly negative. Then

\frac{ln 2}{ln 3} ≤ \underline{lim}\frac{κ_{n} (x)}{n}.

Proof: Let x_{0} ∈ ℚ_{odd} with O (x_{0}) strictly negative. Let v = Φ^{−1}(x_{0}) be the parity vector of x_{0}. Let v = v_{0}v_{1}v_{2} … be the binary representation of v where v_{i} ∈ {0, 1}. Define maps u_{0}, u_{1} from ℝ to itself by u_{0} = T_{0}, and u_{1} (x) = \frac{3}{2}x. Define u ⟨0⟩ = x_{0} and u ⟨k⟩ = u_{v_{k−1}} ∘ ⋯ ∘ u_{v_{0}} (x_{0}) for all k ∈ ℕ^{+}.

For any x ∈ ℚ_{odd},

T_{1} (x) − u_{1} (x) = \frac{3x + 1}{2} − \frac{3}{2}x

= \frac{1}{2}

≥ 0.

Thus u_{1} (x) ≤ T_{1} (x). Since u_{0} (x) = T_{0} (x) we have shown

(4.2)  ∀x ∈ ℚ_{odd}, u_{0} (x) = T_{0} (x) and u_{1} (x) ≤ T_{1} (x) .

We now show that u ⟨k⟩ ≤ T^{k} (x_{0}) for all k ∈ ℕ by induction on k. For the base case we note that u ⟨0⟩ = x_{0} = T^{0} (x_{0}) ≤ T^{0} (x_{0}) . Let k ∈ ℕ and assume that u ⟨k⟩ ≤ T^{k} (x_{0}). Then

u ⟨k + 1⟩ = u_{v_{k}} (u ⟨k⟩)
≤ u_{v_{k}} (T^{k} (x_{0})) because u_{v_{k}} is an increasing function
≤ T_{v_{k}} (T^{k} (x_{0})) by (4.2)
= T^{k+1} (x_{0}) .

So for all k ∈ ℕ, u ⟨k⟩ ≤ T^{k} (x_{0}).

Let n ∈ ℕ^{+} and define κ = κ_{n} (x_{0}). Notice that −1 is an upper bound for O (x_{0}) by Lemma 3.4 (c), so we have

−1 ≥ T^{n} (x_{0})

≥ u ⟨n⟩

= (\frac{3}{2})^{κ} (\frac{1}{2})^{n−κ} x_{0}

= \frac{3^{κ}}{2^{n}} x_{0}.

Multiplying this inequality by −1 (which reverses it) and then taking logarithms yields

\frac{ln 2}{ln 3} − ω \frac{1}{n} ≤ \frac{κ}{n}

where ω = \frac{ln(−x_{0})}{ln 3}. But ω \frac{1}{n} → 0 as n → ∞ so that

∀ε > 0, ∃N > 0, ∀n > N, \frac{ln 2}{ln 3} − ε ≤ \frac{κ_{n} (x_{0})}{n}

Hence \frac{ln 2}{ln 3} ≤ \underline{lim}\frac{κ_{n}(x_{0})}{n}.

♢

Using these results we can now prove Theorem 2.7.

Proof of Theorem 2.7: Let x ∈ ℚ_{odd}.

Assume x is eventually cyclic. Then β = T^{j} (x) is cyclic for some j ∈ ℕ. Let m, M be the smallest and largest cyclic elements in O (x) respectively. Eliahou’s inequality (2.3) tells us that

\frac{ln 2}{ln (3 + \frac{1}{m})} ≤ \frac{κ_{p} (β)}{p} ≤ \frac{ln 2}{ln (3 + \frac{1}{M} )}.

where p = |O (β)|.

Let Φ^{−1} (β) = \overline{a_{0}, …, a_{p−1}} and let n ∈ ℕ^{+}. For all t ∈ ℕ, define α (t) = ∑_{i=0}^{t−1} a_{i}. Let n = qp + r where q, r are the quotient and remainder when n is divided by p (and thus 0 ≤ r ≤ p − 1). Then

\frac{κ_{n} (β)}{n} = \frac{α (n)}{n} = \frac{α (qp + r)}{n} = \frac{qα (p) + α (r)}{qp + r} = \frac{α (p) + \frac{α(r)}{q}}{p + \frac{r}{q}}.

But q → ∞ as n → ∞ so lim_{n→∞} \frac{κ_{n}(β)}{n} = \frac{α(p)}{p} = \frac{κ_{p}(β)}{p}. Thus Theorem 2.7 (a) follows immediately by

noting that lim_{n→∞} \frac{κ_{n}(x)}{n} = lim_{n→∞} \frac{κ_{n}(β)}{n} by Lemma 4.1.

For part (b) assume x has a divergent orbit.

Case 1: Assume O (x) is strictly positive. Let m ∈ ℕ^{+}. By Lemma 3.2 only finitely many elements of O (x) are between 0 and m. Thus there exists N > 0 such that ∀j ≥ N, m ≤ T^{j} (x).

By Lemma 4.2, _{\frac{ln 2}{ln(3+ \frac{1}{m})}} ≤ \underline{lim}\frac{κ_{n}(T^{N} (x))}{n}. But \underline{lim}\frac{κ_{n}(T^{N} (x))}{n} = \underline{lim}\frac{κ_{n}(x)}{n} by Lemma 4.1 and m was

arbitrary, so we have shown

∀m ∈ ℕ^{+}, \frac{ln 2}{ln (3 + \frac{1}{m})} ≤ \underline{lim}\frac{κ_{n} (x)}{n}

Thus,

(4.3)  \frac{ln 2}{ln 3} ≤ \underline{lim}\frac{κ_{n} (x)}{n}

Case 2: Assume O (x) is neither strictly positive nor strictly negative (i.e. contains both positive and negative elements). Then by Lemma 3.4, O (T^{j} (x)) is strictly positive for some j. Since

\underline{lim}\frac{κ_{n}(x)}{n} = \underline{lim}\frac{κ_{n}(T^{j}(x))}{n} by Lemma 4.1 the theorem holds by Case 1.

Case 3: Assume O (x) is strictly negative. Then the theorem holds by Lemma 4.3.

Thus in every case the theorem holds.

♢

4.2. The Proof of Theorem 2.1. We are now ready to prove Theorem 2.1. As stated in Section 2, we will also prove that the statement Ω (ℤ^{+}) ⊆ ℚ_{odd} is equivalent to the Divergent Orbits Conjecture.

Proof: ((a)⇒(b)) The proof that (a) implies (b) was given in Section 2.

((b)⇒(c)) Assume the Autoconjugacy Conjecture is true so that Ω(ℚ_{odd}) ⊆ ℚ_{odd}. Let x ∈ ℚ_{odd} and assume x has a divergent orbit. Then Ω (x) ∈ ℚ_{odd} by the assumption. Since Ω is a conjugacy and conjugacies map divergent orbits to divergent orbits, the orbit of Ω (x) is also divergent. Hence by Theorem 2.7, \underline{lim}\frac{κ_{n}(x)}{n} ≥ \frac{ln 2}{ln 3} and \underline{lim}\frac{κ_{n}(Ω(x))}{n} ≥ \frac{ln 2}{ln 3}. But by Theorem 2.6

1 = \underline{lim}\frac{κ_{n} (x)}{n} + \overline{lim}\frac{κ_{n} (Ω (x))}{n}

≥ \underline{lim}\frac{κ_{n} (x)}{n} + \underline{lim}\frac{κ_{n} (Ω (x))}{n}

≥ \frac{ln 2}{ln 3} + \frac{ln 2}{ln 3}

> 1

which is a contradiction. Therefore the Autoconjugacy Conjecture implies there are no divergent orbits of rational 2-adics. Thus (b) implies (c).

Note that the same proof shows that Ω (ℤ^{+}) ⊆ ℚ_{odd} implies the Divergent Orbits Conjecture if we take x ∈ ℤ^{+} instead of x ∈ ℚ_{odd}.

On the other hand, assume the Divergent Orbits Conjecture holds. Let y ∈ ℤ^{+}. By our assumption the orbit of y is eventually cyclic, so that Φ^{−1} (y) has eventually periodic digits in its binary representation and hence is rational. But both V and Φ map rational numbers to rational numbers so that Ω (y) = ΦV Φ^{−1} (y) is rational as well. Since y was arbitrary, Ω (ℤ^{+}) ⊆ ℚ_{odd}. Thus the Divergent Orbits Conjecture implies that Ω (ℤ^{+}) ⊆ ℚ_{odd}. So the statement Ω (ℤ^{+}) ⊆ ℚ_{odd} is equivalent to the Divergent Orbits Conjecture.

((c)⇒(a)) The fact that (c) implies (a) is essentially stated by Bernstein and Lagarias in [2]. To see this, assume no rational 2-adic integer has a divergent T -orbit. Let x ∈ ℚ_{odd}. Since O (x) is not divergent, it is finite and hence eventually periodic. Thus Φ^{−1} (x) ∈ ℚ_{odd} by the argument at the beginning of Section 2. Hence Φ^{−1} (ℚ_{odd}) ⊆ ℚ_{odd}. So (c) implies (a).

♢

4.3. Proof of Theorem 2.2. ((a)⇒(b)) Assume that the T -orbit of any positive integer contains 1. It suffices to show that

(4.4)  ∀n ∈ ℕ^{+}, T^{k} (n) = 1 ⇒ the ξ-orbit of n contains 1

holds for all k ∈ ℕ by induction on k.

Let n ∈ ℕ^{+}. Assume T^{0} (n) = 1. Then ξ^{0} (n) = n = T^{0} (n) = 1. So (4.4) holds for k = 0.

Let k ∈ ℕ. Assume (4.4) holds for k. Let n ∈ ℕ^{+}. Assume T^{k+1} (n) = 1. Then T^{k} (T (n)) = 1, so by the inductive hypothesis ξ^{s} (T (n)) = 1 for some s ∈ ℕ. Since Ω is an autoconjugacy of T we have Ω ∘ T = T ∘ Ω so that

T^{k} (T^{2}Ω (n)) = T ΩT^{k+1} (n) = T (Ω(1)) = T (2) = 1.

So once again by the inductive hypothesis ξ^{r} (T^{2}Ω (n)) = 1 for some r ∈ ℕ.

By the definition of ξ, for any m ∈ ℕ, ξ (m) = T (m) if m is even and ξ (m) = Ω (m) if m is odd. Case 1: If n is even then ξ^{s+1} (n) = ξ^{s} (ξ (n)) = ξ^{s} (T (n)) = 1. Case 2a: If n is odd and T (Ω (n)) is even then Ω (n) is even and

ξ^{r+3} (n) = ξ^{r+2} (Ω (n)) = ξ^{r+1} (T Ω (n)) = ξ^{r} (T^{2}Ω (n)) = 1

Case 2b: If n is odd and T (Ω (n)) is odd then Ω (n) is even and

ξ^{s+3} (n) = ξ^{s+2} (Ω (n)) = ξ^{s+1} (T Ω (n)) = ξ^{s} (ΩT Ω (n)) = ξ^{s} (Ω^{2}T (n)) = ξ^{s} (T (n)) = 1.

So in every case, the ξ-orbit of n contains 1. Thus (4.4) holds for all k by induction.

((b)⇒(c)) Assume the ξ-orbit of any positive integer contains 1. Let n be a positive integer. Then ξ^{k} (n) = 1 for some k ≥ 0. For 0 ≤ i < k, if ξ^{i} (n) is even then

[ξ^{i+1} (n)] = [ξ (ξ^{i} (n))] = [T (ξ^{i} (n))] = Ψ ([ξ^{i} (n)])

and if ξ^{i} (n) is odd then

[ξ^{i+1} (n)] = [ξ (ξ^{i} (n))] = [Ω (ξ^{i} (n))] = [ξ^{i} (n)] = id ([ξ^{i} (n)])

where id is the identity map on ℤ_{2}/ ∼. Since ξ always maps odd numbers to even numbers, there exists natural numbers a_{0}, a_{1}, …, a_{p} such that

[1] = [ξ^{k} (n)] = Ψ^{a_{0}} ∘ id ∘ Ψ^{a_{1}} ∘ ⋯ ∘ Ψ^{a_{p−1}} ∘ id ∘ Ψ^{a_{p}} ([n]) = Ψ^{a_{0}+···+a_{p}} ([n]) .

Thus the Ψ-orbit of [n] for any positive integer n contains [1].

((c)⇒(a)) Assume the Ψ-orbit of the class of any positive integer n contains [1]. Let n be a positive integer. Then Ψ^{k} ([n]) = [1] for some k ≥ 0. But Ψ^{k} ([n]) = [T^{k} (n)] so [T^{k} (n)] = [1] = {1, 2}. Thus T^{k} (n) ∈ {1, 2} so that either T^{k} (n) = 1 or T^{k+1} (n) = 1. Hence the T -orbit of every positive integer contains 1.

♢ 4.4. Proof of Theorem 2.3. Let C = O (x) be a self conjugate T -cycle so that Ω (C) = C. Then x ∈ C so Ω (x) ∈ C also. By the definition of orbit, Ω (x) = T^{k} (x) for some k ∈ ℕ. Let v = Φ^{−1} (x) be the parity vector of x and v = v_{0}v_{1}v_{2} … with v_{i} = {0, 1} for all i ∈ ℕ its binary representation.

Then

Φ^{−1} (Ω (x)) = Φ^{−1}ΦV Φ^{−1} (x)
= V (v_{0}v_{1}v_{2} …)
= v_{0}^{∗}v_{1}^{∗}v_{2}^{∗} …

and also σ ∘ Φ^{−1} = Φ^{−1} ∘ T so

Φ^{−1} (Ω (x)) = Φ^{−1} (T^{k} (x)) = σ^{k} (Φ^{−1} (x)) = σ^{k} (v_{0}v_{1} ⋯) = v_{k}v_{k+1}v_{k+2} …

so that

(4.5)  ∀i ∈ ℕ, v_{i}^{∗} = v_{i+k}.

However, for any i ∈ ℕ,

(4.6)  v_{i+2k} = v_{i+k}^{∗} = v_{i}^{∗∗} = v_{i}

so that combining (4.5) and (4.6) gives v = \overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}} and so

x = Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}})

as claimed.

To prove the reverse implication, let x = Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}}) for some v_{0}, v_{1}, …, v_{k−1} ∈ {0, 1}. Then

x = Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}})
= Φ (σ^{2k} (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}}))
= T^{2k} (Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}}))
= T^{2k} (x)

so x is cyclic and

Ω (x) = ΦV Φ^{−1} (x)
= ΦV Φ^{−1}Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}})
= ΦV (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}})
= Φ (\overline{v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}v_{0}v_{1} ⋯ v_{k−1}})
= Φ (σ^{k} (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}}))
= T^{k}Φ (\overline{v_{0}v_{1} ⋯ v_{k−1}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k−1}^{∗}})
= T^{k} (x)

so that Ω (x) ∈ O (x). But x ∈ O (x) so Ω (x) ∈ Ω (O (x)) and thus Ω (x) ∈ Ω (O (x)) ∩ O (x). As conjugacies map cycles to cycles Ω (O (x)) is a cycle. Since two cycles are either disjoint or equal, so Ω (O (x)) = O (x). Hence O (x) is self conjugate.

♢ 4.5. Proof of Theorem 2.4. Let C be a self conjugate T -cycle. By Theorem 2.3, C = O (x) where x = Φ (\overline{v_{0}v_{1} ⋯ v_{k}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k}^{∗}}) for some v_{0}, v_{1}, …, v_{k−1} ∈ \{0, 1\}. Since O (0) is not self conjugate, it follows by Lemma 3.4 that C is either strictly negative or strictly positive. Since \frac{κ_{2k}(x)}{2k} = \frac{k}{2k} = \frac{1}{2} it follows that

(4.7)  \underline{lim}\frac{κ_{n} (x)}{n} = lim_{n→∞} \frac{κ_{n} (x)}{n} = \frac{1}{2}.

If x is negative then \underline{lim}\frac{κ_{n}(x)}{n} ≥ \frac{ln 2}{ln 3} > 1/2 by Lemma 4.3. Hence x is positive and so C is strictly positive.

♢

4.6. Proof of Theorem 2.5. Let C be a self conjugate T -cycle. By Theorem 2.3, C = O (x) where

x = Φ (\overline{v_{0}v_{1} ⋯ v_{k}v_{0}^{∗}v_{1}^{∗} ⋯ v_{k}^{∗}}) for some v_{0}, v_{1}, …, v_{k−1} ∈ \{0, 1\}. Thus lim_{n→∞} \frac{κ_{n}(x)}{n} = \frac{1}{2} as shown in

(4.7). Combining this with Theorem 2.7 (a) we have

(4.8)  \frac{ln 2}{ln (3 + \frac{1}{m})} ≤ \frac{1}{2} ≤ \frac{ln 2}{ln (3 + \frac{1}{M} )}

where m = min (C) and M = max (C) are positive by Theorem 2.4. Solving (4.8) for m and M gives

(4.9)  min (C) ≤ 1 ≤ max (C)

as desired. Since the cycle containing 1 is {1, 2} it follows that 1 < max (C).

To prove the theorem, notice that it is easy to verify by direct computation that {1, 2} is selfconjugate. Let C be any self conjugate T -cycle C of integers. By Theorem 2.4 the orbit C is strictly positive. But by (4.9) the minimum value of C must be 1. Thus C = {1, 2}.

♢

5. Acknowledgement

We give special thanks to Jeffrey Lagarias for several helpful comments on an earlier draft of this paper, and in particular for pointing out that (c) implies (a) in Theorem 2.1.

This project was funded in part by two summer research grants from the University of Scranton.

References

[1] Bernstein, D.J., A non-iterative 2-adic statement of the 3x + 1 conjecture, Proc. Amer. Math. Soc. 121 (1994), 405-408

[2] Bernstein, D.J. and Lagarias, J. C., The 3x + 1 Conjugacy Map, Can. J. Math. 48 (1996), 1154-1169

[3] Eliahou, S, The 3x + 1 problem: new lower bounds on nontrivial cycle lengths, Discrete Math. 188 (1993), 45-56 [4] Lagarias, J. C., The 3x + 1 problem and its generalizations, Am. Math. Monthly 92 (1985), 3-23

[5] Lagarias, J. C., The set of rational cycles for the 3x+1 problem, Acta Arithmetica 56 (1990), 33-53

[6] Hedlund, G., Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320-375

[7] Wirsching, G., The Dynamical System Generated by the 3n + 1 Function, Lecture Notes in Mathematics 1681, Springer-Verlag, 1998, ISBN: 3-540-63970-5

Department of Mathematics, University of Scranton, Scranton, PA USA 18510

   E-mail address: monks@scranton.edu
   URL: http://www.scranton.edu/~monks

Department of Mathematics, University of Scranton, Scranton, PA USA 18510

   E-mail address: yazinskij2@scranton.edu