# Constructive survivor lists for an injective Collatz restriction ## 1. Result and contribution Consider the partial map $$ H(n)= \begin{cases} 3n/4,&n\ge8,\quad n\equiv0\pmod4,\\ (9n+1)/8,&n\ge8,\quad n\equiv7\pmod8, \end{cases} \tag{1} $$ which is undefined on the other positive integers. Its termination is Conjecture 4.14 of Yolcu, Aaronson and Heule [1]. It is a restriction relevant to Collatz: for the shortcut Collatz map $C$ and $\psi(n)=8n+1$, $$ C^2(\psi(n))=\psi(3n/4),\qquad C^3(\psi(n))=\psi((9n+1)/8) \tag{2} $$ on the respective legal branches. Their shortcut parity words are $10$ and $101$. Termination of $H$ would settle this restricted problem, not the full Collatz conjecture. Let $S_h$ be the set of positive integers admitting $h$ successive applications of $H$, with $S_0=\mathbb Z_{>0}$. Write $$ \alpha=\log_3 2,\qquad H_2(p)=-p\log_2p-(1-p)\log_2(1-p),\qquad \theta_*=(1-\alpha) H_2\!\left(\frac{2\alpha-1}{1-\alpha}\right) =0.320851848794\ldots. \tag{3} $$ **Theorem 1 (exact listing).** For every $\theta>\theta_*$ there is a computable integer-valued function $h_\theta(k)=O_\theta(k+1)$ and an algorithm that, given any interval $I$ of $M\ge1$ consecutive positive integers, lists exactly $$ I\cap S_{h_\theta(\lceil\log_2 M\rceil)}. \tag{4} $$ The algorithm uses $O_\theta(M^\theta)$ integer arithmetic operations. Every integer used has $O_\theta(\log(2+\max I)+\log(2+M))$ bits. Thus its bit complexity is $$ M^\theta\operatorname{poly}_\theta \bigl(\log(2+\max I)+\log(2+M)\bigr). \tag{5} $$ The interval location is unrestricted. The output retains the original sources. The proof supplies the algorithm and its complexity bound; finite timings are not used to infer either. The counting mechanism is inherited from Garcia–Tal's translated-interval compression [2] and Leen's recursive parity-cylinder argument [3]. The extra constructive fact is that $H$ is globally injective on its domain. We recursively list surviving *images* in shorter intervals and pull them back through the unique partial inverse. This avoids generating the numerous source words that share those image intervals. **Corollary 2 (finite survival and orbit sets).** For every $\theta>\theta_*$ there are constants $L_\theta,C_\theta,C'_\theta$ such that every interval $I$ of $M$ consecutive positive integers satisfies $$ \#\bigl(I\cap S_{\lceil L_\theta(1+\log_2M)\rceil}\bigr) \le C_\theta M^\theta, \tag{6} $$ and every finite or infinite actual $H$ orbit set $\mathcal O$ satisfies $$ \#(\mathcal O\cap I)\le C'_\theta M^\theta. \tag{7} $$ In particular, for distinct states of one orbit lying above $N\ge1$, and $\theta_*<\theta<1$, $$ \sum_{\substack{x\in\mathcal O\\x\ge N}}\frac1x \le K_\theta N^{\theta-1}. \tag{8} $$ These are sparsity and finite-listing statements. They do not say the list in (4) is empty. No positive cycle or divergent orbit is excluded. ## 2. Relation to existing compression and verification methods Garcia and Tal [2, Lemma 3 and Theorem 1] group source cylinders into shorter image intervals to bound synchronous transversals and orbit sets. Their generalized Hasse map, also denoted $H$ in that paper, is a different total map. Leen [3, appendix “Uniform sparsity of orbit sets”] uses recursive grouping to obtain every Collatz orbit-set exponent above $H_2(\log_3 2)$. Our earlier paper [4] retains common clocks and odd-step labels for Collatz image compression and obtains stronger counting estimates. None of those results makes the ordinary Collatz map globally injective. A small image count alone does not furnish an efficient list of all original sources in a fibre. For the restricted map (1), the cylinder identity was established in [5, Lemma 2.1]. Its two letter types have different binary and ternary costs. Their constrained word entropy gives (3), and disjoint image residues provide the unique pullback needed for the listing algorithm. We prove the cylinder identity again below so that Theorem 1 is self-contained. No new general interval-compression principle is claimed. Computational Collatz verification already uses source-cylinder sieves. Barina [6, Sections 3.2–3.4] combines ternary preimage sieves, binary cylinder tables and simultaneous treatment of congruence classes. Angeltveit [7, Sections 2–5] recursively adds source bits, applies descent and smaller-source path-merging tests, and uses lookahead bitvectors. Those algorithms verify convergence on bounded ranges by resolving the remaining sources. Theorem 1 instead gives a proved operation bound for listing finite-horizon survivors of the injective partial map (1), with arbitrary interval translation. Its low groups recurse on image intervals. We do not claim a practical speed advantage over those implementations, an ordinary-Collatz verification algorithm with exponent (3), or priority for recursive source sieving. The theorem is also different from the matrix-interpretation obstruction in [5]. That paper limits a class of termination certificates; the present paper supplies an exact finite enumeration procedure. ## 3. Cylinders, inverse images and the entropy threshold Call the branches in (1) $a$ and $b$. For a chronological word $W$ with $a_W$ letters $a$ and $b_W$ letters $b$, put $$ A_W=a_W+2b_W,\qquad B_W=2a_W+3b_W,\qquad t_W=a_W+b_W=B_W-A_W. \tag{9} $$ **Lemma 3 (cylinder identity).** For every $W$ there are integers $0\le r_W<2^{B_W}$ and $0\le c_W<3^{A_W}$ such that, before imposing the cutoff $n\ge8$ at intermediate inputs, its nonnegative source cylinder and endpoint are $$ n=r_W+2^{B_W}q,\qquad f_W(n)=c_W+3^{A_W}q,\qquad q\ge0. \tag{10} $$ All prefix values are nonnegative integers affine in $q$, with positive integer slope. In particular, all input cutoffs hold when $q\ge8$. *Proof.* The empty word has $r=c=A=B=0$. Appending $a$ requires $c+3^Aq\equiv0\pmod4$, so $q=z+4q'$ for a unique $0\le z<4$. Then $$ r'=r+2^Bz,\qquad c'=\frac{3(c+3^Az)}4<3^{A+1}. $$ Appending $b$ similarly fixes $q=z+8q'$, $0\le z<8$, and gives $$ r'=r+2^Bz,\qquad c'=\frac{9(c+3^Az)+1}{8}\le3^{A+2}-1. $$ The bounds on $r'$ and prefix slopes follow inductively. The cutoff claim uses a prefix slope at least one and a nonnegative intercept. $\square$ **Lemma 4 (unique pullback).** The map $H$ is injective, and its partial inverse is $$ R(y)= \begin{cases} 4y/3,&y\equiv0\pmod3,\\ (8y-1)/9,&y\equiv8\pmod9, \end{cases} \tag{11} $$ provided the displayed predecessor is at least $8$; otherwise that inverse step is undefined. *Proof.* An $a$ input is $4z$ and has image $3z$. A $b$ input is $8z+7$ and has image $9z+8$. The image classes are disjoint, and both affine maps are injective. Formula (11) gives the only possible predecessors and their required source congruences. $\square$ Fix a binary precision $k\ge1$ and stop a word when its cumulative binary cost first reaches $k$. Since letters cost two or three bits, $$ B\in\{k,k+1,k+2\},\qquad t\le\lceil k/2\rceil. \tag{12} $$ Every source surviving $\lceil k/2\rceil$ steps has such a stopping word. An interval of width at most $2^k$ meets at most two source blocks $[q2^B,(q+1)2^B)$. For fixed $A,B,q$, all stopped images lie in the single interval $$ J_{A,q}=[q3^A,(q+1)3^A)\cap\mathbb Z. \tag{13} $$ Their stopping time is the same number $B-A$. Consequently their images are distinct by Lemma 4 even when their words differ. We will enumerate these images without first enumerating the words. For a count pair $A,B$, the letter counts and total number of words are $$ a_W=2B-3A,\qquad b_W=2A-B,\qquad \binom{B-A}{2A-B}. \tag{14} $$ The binomial coefficient is understood to be zero unless both letter counts are nonnegative. Define $$ g(z)=(1-z)H_2\!\left(\frac{2z-1}{1-z}\right), \qquad \frac12\le z\le\frac23. \tag{15} $$ The entropy bound for (14) is $2^{Bg(A/B)}$. Moreover $$ g'(z)\log2 =\log\frac{(2-3z)^3}{(1-z)(2z-1)^2}. \tag{16} $$ The ratio is less than one at $z=5/8$, and decreases thereafter: its numerator decreases, while the derivative of its denominator is $(2z-1)(5-6z)>0$ on this interval. Thus $g$ is strictly decreasing on $[5/8,2/3]$, with $g(\alpha)=\theta_*$. Choose a rational $$ \frac58\le\beta<\alpha,\qquad g(\beta)<\theta, \qquad c=\beta\log_2 3<1. \tag{17} $$ Such a choice exists for every $\theta>\theta_*$. All algorithmic cutoffs below are then exact rational or integer comparisons. **Lemma 5 (high-word count).** Let $N_\beta(k)$ count all words with $B\in\{k,k+1,k+2\}$ and $A>\beta k$, including those that cross $k$ before their last letter. Then $$ N_\beta(k)\le C_\beta(k+1)2^{kg(\beta)}. \tag{18} $$ *Proof.* Sum (14) over the three possible $B$ values. There are $O(k+1)$ admissible count pairs. For a high pair, $A/B>\beta k/(k+2)=\beta-O(1/k)$. Monotonicity of $g$ beyond $\beta$, and its bounded derivative in a neighbourhood of $\beta$, give $Bg(A/B)\le kg(\beta)+O_\beta(1)$. The finitely many small $k$ are absorbed into $C_\beta$. $\square$ ## 4. A computable finite horizon For $k\ge0$ set $$ \ell_A=\lceil\log_2(3^A)\rceil,\qquad D(k)=\{A\in\mathbb Z_{\ge0}:A\le\beta k,\ \ell_A\le k-2\}. $$ Compute $\ell_A$ as the bit length of $3^A-1$, including $\ell_0=0$; floating-point logarithms are unnecessary. Fix a base precision $k_0\ge2$, and define $$ h(k)= \begin{cases} \lceil k/2\rceil,&0\le k\le k_0,\\ \displaystyle\lceil k/2\rceil+ \max\bigl(\{h(\ell_A):A\in D(k)\}\cup\{0\}\bigr),&k>k_0. \end{cases} \tag{19} $$ Every recursive argument is at most $k-2$, so the definition terminates. For sufficiently large $k$, $\ell_A\le ck+1\le c'k$ for any fixed $c1/[2(1-\beta\log_2 3)]$ after finitely many small scales are handled. The requirement $g(\beta)<\theta$ forces $\beta\uparrow\alpha$ as $\theta\downarrow\theta_*$. This sufficient coefficient diverges, and the recursive clock (19) has the same loss of scale separation. This is a limitation of the construction, not a lower bound on every possible listing algorithm or horizon. We make no endpoint estimate. ## 5. The listing algorithm and its correctness For recursion, permit intervals $[L,L+M)$ with $L\ge0$, while always excluding source $0$ from the output. This includes (13) when $q=0$. Set $k=\lceil\log_2M\rceil$. If $k\le k_0$, scan the at most $2^{k_0}$ sources and test their first $h(k)$ steps directly. Otherwise consider every $B\in\{k,k+1,k+2\}$ and every nonnegative pair in (14). Put $t=B-A$, and discard the pair if $t>\lceil k/2\rceil$. If $A\in D(k)$, consider the at most two block indices $q$ whose source blocks meet the current interval. Recursively list the positive members of $J_{A,q}\cap S_{h(\ell_A)}$. For each listed image, apply the unique inverse (11) exactly $t$ times, checking the cutoff at each step. Retain the source only if it lies in the current interval, the recovered word has counts $A,B$ and first crosses precision $k$ on its last letter, and a forward replay verifies survival through $h(k)$ steps. This low group never generates its source words. If $A\notin D(k)$, generate only the words with exactly $a_W=2B-3A$ letters $a$ and $b_W=2A-B$ letters $b$, by generating the $\binom{B-A}{2A-B}$ choices of the $b$ positions. Reject words whose binary cost crosses $k$ early. Compute $r_W$ from (10). Since $2^B\ge2^k\ge M$, the source cylinder has at most one representative in the interval. Find it by integer division and accept it exactly when its forward replay admits all $h(k)$ steps. For sufficiently large $k$, groups outside $D(k)$ are the high groups of Lemma 5. The extra groups caused by $\ell_A\le k-2$ occur at only finitely many precisions and affect only constants. Deduplicate sources, for example in a balanced search tree, and output them in increasing order. **Proposition 6 (exactness).** The algorithm returns precisely the positive sources in the supplied interval that survive $h(k)$ steps. *Proof.* Induct on $k$. The direct base case is exact. A surviving source has a unique first-crossing word by (12). If its group is low, its stopped image lies in (13) and admits at least $$ h(k)-t\ge h(\ell_A) $$ additional steps by (19). The induction hypothesis lists that actual image. Its unique inverse recovers the original source and word, which pass all the filters. If the group is high, the word is generated and its unique interval representative is tested. Conversely every output is positive and its full replay passed. $\square$ The final replay is necessary: a child list includes images whose inverse word belongs to another group, and the child horizon need not match the remaining parent horizon exactly. The reconstruction filters remove both forms of overcount. ## 6. Complexity and sparsity Let $T(k)$ be the worst-case number of integer arithmetic operations at precision $k$, uniformly in the nonnegative interval location. Cylinder computation, inverse reconstruction, word generation delay and forward replay cost a polynomial in $k$. A child output is explicitly listed, so its cardinality is at most its work. Set comparisons cost a polynomial factor in $k$ per source, since there are at most $2^k$ distinct sources. For one fixed polynomial $P$ and all large $k$, $$ T(k)\le P(k)\sum_{A\in D(k)}T(\ell_A) +P(k)\bigl(1+N_\beta(k)\bigr). \tag{20} $$ Memoization may reduce this count but is not needed for the bound. Assume inductively $T(j)\le C2^{\theta j}$ for $j