3.5 Correspondence to the Original Map
For any \(n \in \mathbb {N}\), one step of the compact Collatz map \(T\) can be simulated by one or two steps of the original Collatz map \(C\). Specifically, there exists \(j \in \{ 1, 2\} \) such that \(C^j(n) = T(n)\).
We split into cases based on the parity of \(n\). If \(n\) is even, \(T(n) = n/2 = C(n)\), so \(j=1\). If \(n\) is odd, \(T(n) = (3n+1)/2 = C(3n+1)/2 = C(C(n))\), so \(j=2\) (since \(3n+1\) is even).
For any \(k, n \in \mathbb {N}\), there exists \(j\ge k \in \mathbb {N}\) such that \(C^j(n) = T^k(n)\).
By induction on \(k\), using Lemma 114.
If \(n \ge 1\) and \(C^j(n) = 1\) for some \(j \in \mathbb {N}\), then there exists \(k \in \mathbb {N}\) such that \(T^k(n) = 1\).
By induction on \(j\). In the base case \(j=0\), \(n=1=T^0(n)\). For the inductive step \(j+1\), if \(n\) is even, then \(C(n) = n/2 = T(n)\), so we apply the induction hypothesis to \(T(n)\). If \(n\) is odd, then \(C(n) = 3n+1\), and \(C(3n+1) = (3n+1)/2 = T(n)\). Since \(C^j(3n+1) = 1\), we apply the induction hypothesis to \(3n+1\), which reaches 1 under \(T\). Since \(T(n)\) is a step in that sequence, \(n\) also reaches 1 under \(T\).
For any odd \(n \in \mathbb {N}\), \(n\) belongs to a cycle under the original Collatz map \(C\) if and only if it belongs to a cycle under the compact map \(T\).
\((\Rightarrow )\) If \(n\) is on a cycle of length \(k {\gt} 0\) under \(C\), we can count the number of even steps in the cycle to determine the corresponding number of steps under \(T\). The "halving" steps in the original sequence correspond exactly to the steps in the compact sequence. Since the sequence is periodic, it must eventually return to \(n\) under \(T\). \((\Leftarrow )\) If \(T^k(n) = n\) for some \(k {\gt} 0\), since every step of \(T\) can be simulated by one or two steps of \(C\) (Lemma 114), it follows that \(C^j(n) = n\) for some \(j \ge k {\gt} 0\).
For any \(n \in \mathbb {N}\), the orbit of \(n\) under \(C\) is bounded if and only if the orbit of \(n\) under \(T\) is bounded.
\((\Rightarrow )\) Since every value in the \(T\)-orbit is also present in the \(C\)-orbit (Lemma 115), if the \(C\)-orbit is bounded by \(B\), then the \(T\)-orbit is also bounded by \(B\). \((\Leftarrow )\) If the \(T\)-orbit is bounded by \(B\), then any value \(C^d(n)\) in the \(C\)-orbit is either a value \(T^k(n) \le B\), or it is an "intermediate" odd step \(m = C^d(n)\) such that \(C(m) = 3m+1\) is even and \(C(3m+1) = (3m+1)/2 = T^k(n) \le B\). In the latter case, \(3m+1 \le 2B\), so \(m \le (2B-1)/3 {\lt} B\). Thus the entire \(C\)-orbit is bounded by \(2B+1\).