# Effective periodic-dictionary complexity for Collatz trajectories ## Contribution and prior work An exceptional Collatz orbit would have to avoid convergence while respecting the arithmetic of every one of its finite prefixes. We prove an effective restriction on how such a prefix can be described by a fixed finite collection of periodic exponent patterns. Arbitrarily long pieces of a chosen periodic pattern each count once; strings of exponent one are free. The minimum number of counted pieces grows at least as $c_W\log t\log\log t$ on every orbit avoiding the explicitly known cycles represented by the dictionary. The primary result is a uniform finite inequality with explicit constants, including its dependence on the initial integer. It yields an effective bound on the number of non-one steps for every orbit and, using an effective cycle-minimum bound, the same lower order for dictionary complexity of long positive cycles. The fixed-budget excursion exponent is sharply $\log_2 3$, with an ineffective constant. Its arithmetic input is Evertse's nondegenerate S-unit inequality [1]. The effective count uses Evertse and Ferretti's height-interval refinement of the Quantitative Subspace Theorem [2]. That theorem bounds the number and relative widths of exceptional height intervals, but not their locations. Disjoint intervals of growth of actual orbit records can be charged to their total widths. The new arithmetic interface accommodates arbitrary periodic templates and phase changes. Above an explicit state threshold, one root term dominates every possible cancelling subsum. Deleting zero subsums among the remaining terms preserves that root and the actual trajectory numerator. The primitive gcd is bounded using the root and the total sum; this gives the height lower bound needed at fast records. Ordered underlying powers of two and three survive deletion, even when actual valuations do not. These features avoid a separate boundary-merger grammar for every dictionary. Small-state segments have a computable height ceiling derived from periodic divisibility. Run compression itself is standard in the cycle literature. Brox [3] compresses the cycle numerator at descending elements and proves effective finiteness of cycles having fewer than twice the logarithm of their period many descending elements. His use of periodic closure and linear forms in logarithms differs from our open-trajectory argument. Luca [4] groups constant exponent runs and proves a logarithmic lower bound for the number of one-runs in positive cycles. His effective cycle-minimum estimate is an input to our cycle corollary. Our dictionary count is different from his ascent count, and we do not claim to improve his theorem about that quantity. Quantitative Subspace methods for symbolic complexity are also classical. Bugeaud and Evertse [5, Theorem 3.1 and Section 8] give effective bounds for digit changes in ordinary base expansions of algebraic irrational real numbers. Those hypotheses do not apply to the rational integer labels and mixed powers of two and three here. Our contribution is the trajectory numerator, its root-preserving deletion, the ordered mesh, and the charging of actual record progress. Lagarias's bibliographies [6,7] provide the broader cycle and predecessor context. Our comparison is scoped to the cited results; we do not assert an exhaustive priority claim. Cassian Mahler's public exponent-two telescoping suggestion [8] motivated the initial special case of the dictionary formulation. The results require no mixing or density theorem. They constrain each individual trajectory but still permit highly irregular divergent orbits. They give neither positive piece frequency nor a strict exponential growth-rate gap, and do not resolve Collatz. All times below count odd steps. An even initial integer can first be replaced by its odd part. All logarithms without a displayed base are natural. ## Statement and conventions Write $U_e(x)=(3x+1)/2^e$. An actual word means that every intermediate value is positive odd and $e=v_2(3x+1)$ at that step. Fix a finite nonempty dictionary $W$ of nonempty positive exponent words, each containing a letter at least two. A counted piece is any nonempty finite factor of $w^\infty$ for a word $w\in W$, with any phase and any terminal cut, or an individual exponent at least two. Arbitrary strings of ones are free gaps. Let $k_W(t)$ be the minimum number of counted pieces covering the first $t$ actual exponents. This is prefix-monotone: truncation leaves an admissible decomposition of no greater cost. Any consecutive subword of a decomposition with at most $m$ pieces also has at most $m$ pieces. For each cyclic phase of $w$, compute its affine fixed point $\alpha=p/q$ in lowest terms, with $q>0$. If $n=|w|$, $D=\sum w_i$, and $U_w(x)=(3^nx+c)/2^D$, then $\alpha=c/(2^D-3^n)$. Both its reduced denominator and numerator are odd; its denominator is prime to three. There is no zero denominator. Its other phases are the corresponding rotated-word fixed points. Positive integral phases give positive odd integral cycles: the fixed-point equation implies the successive divisibilities by two, and the rotated numerators are odd. Equivalently, this finite claim can be checked directly for every template. Stop before any step starting in the union $\mathcal C_W$ of these cycles and $\{1\}$. A terminal state in this set is allowed. No absence of other positive cycles is assumed. **Theorem 1 (effective dictionary complexity).** There are explicit constants $G\ge2$ and $C_W>0$ such that, for every positive odd start $b$, every allowed finite prefix of length $t$, every integer $m\ge1$, and $k=k_W(t)$, $$ \log\frac{t+1}{\log(b+G)} \le \log(k+1)+\left(\frac{k}{m}+1\right)\log2 +e^{C_Wm}+\log\frac8{\log2}. \tag{1} $$ Consequently any orbit avoiding $\mathcal C_W$ satisfies, for an effective $c_W>0$ and an effective threshold depending on $b$ and $W$, $$ k_W(t)\ge c_W\log t\log\log t. \tag{2} $$ **Theorem 2 (sharp fixed-budget excursions).** For every fixed integer $r\ge0$ and every $\sigma>\log_2 3$, there is a possibly ineffective $K_{r,W,\sigma}$ such that every allowed segment of cost at most $r$ starting at $b$ has all its states at most $K_{r,W,\sigma}b^\sigma$. The leading exponent $\log_2 3$ cannot be decreased, already for free gaps. ## Explicit elementary constants Take an integer $G$ at least $2^{\max_{w\in W}|w|}$ and at least $q+|p|+2$ for every phase $p/q$. Increase it to at least four if necessary. For a piece starting at $x$, let $L$ be its number of complete periods. If $x\ne\alpha$, periodic integrality implies $$ 2^{DL}\mid qx-p,\qquad L\le D^{-1}\log_2|qx-p|. $$ Since $D\ge n$, $|qx-p|\le(x+G)^2$, and the terminal incomplete period has length less than $n\le\log_2G$, the piece length is at most $3\log_2(x+G)$. The excluded case $x=\alpha>0$ is a stopped template cycle. A singleton high letter has length one and satisfies the same bound. Also every actual step satisfies $U_e(x)+G\le(3/2)(x+G)$. Thus a piece's shifted maximum is at most $(x+G)^3$. A free one-gap has length at most $\log_2(x+1)$ and shifted maximum at most $(x+G)^2$. A free gap followed by one piece therefore has length at most $7\log_2(x+G)$ and shifted maximum at most $(x+G)^6$; weaken six to eight. Iterating and allowing a final free gap gives, for at most $m$ counted pieces, $$ \ell\le8\,8^m\log_2(b+G),\qquad \max_j(x_j+G)\le(b+G)^{2\,8^m}. \tag{3} $$ We also need a uniform reciprocal bound per piece. For a phase of a word of length $n$, let $s=3^n/2^D$, and let $s_*>0$ be the minimum of its prefix multipliers, including the empty prefix. Every state in a period whose entrance is $y$ is at least $s_*y$. If $s>1$, successive period entrances grow by at least the factor $s$, so the reciprocal sum of all complete periods is at most $n/[s_*(1-1/s)]$. If $s<1$ and $x>\alpha$, then $\alpha>0$ and the entrance distances from $\alpha$ decrease geometrically, but their last nonzero distance is at least $1/q$. Reversing their order bounds the sum of reciprocal entrance values by $q/(1-s)$, and the full reciprocal sum by $nq/[s_*(1-s)]$. If $x<\alpha$, the entrance values strictly increase through positive integers below $\alpha$, so there are at most $\lceil\alpha\rceil$ complete periods, contributing at most $n\lceil\alpha\rceil$. Add $n$ for the partial period in all cases. Let $r_W\ge1$ be the maximum of these explicit bounds over phases. A free gap has reciprocal sum at most three, and a singleton has sum at most one. Take, for example, $R=4+r_W$. Then $$ \prod_{j<\ell}\left(1+\frac1{3x_j}\right) \le e^{R(m+1)},\qquad a+1\le 2e^{R(m+1)}\frac{3^\ell}{2^D}(b+1). \tag{4} $$ All constants here are computable from the finite dictionary. No finite simulation of all small starting values is an input. ## The numerator and removal of zero subsums Let $C$ be the least common multiple of the denominators of all phase shifts $q_\alpha=\alpha+1$. It is prime to six. A periodic piece, from entrance phase $\alpha$ to exit phase $\beta$, satisfies $$ 3^\ell(b+1)=2^D(a+1)-2^Dq_\beta+3^\ell q_\alpha. \tag{5} $$ Unroll the full segment backwards after multiplying by $C$. Its root is $A_0=C2^D(a+1)$, and its full sum is $C3^\ell(b+1)$. Each periodic piece contributes two nonzero coordinates with coefficients $-Cq_\beta,Cq_\alpha$; each singleton contributes coefficients $-C,2C$. Free gaps contribute none. There are at most $2m$ nonroot coordinates. In their reverse order their underlying binary positions $A_i$ decrease weakly and ternary positions $B_i$ increase weakly. Let $L$ be the lcm of the absolute nonzero coefficients in this finite catalog. Let $S_f$ be the primes dividing $6L$, and $s=|S_f|$. Put $Q_* =\max(2,\max_\alpha|q_\alpha|)$ and $M_m=\lceil4mQ_*\rceil+1$. For each coordinate $z_i=c_i2^{A_i}3^{B_i}$ there is an actual boundary state $x_i$ such that $$ |z_i|\le\frac{Q_*A_0}{x_i+1}. \tag{6} $$ Indeed the shifted inverse recurrence subtracts a nonnegative constant, so every inverse prefix satisfies $3^j(x+1)\le2^d(a+1)$. For the outgoing term of a singleton, use the next boundary and the additional factor $1/3$; $Q_*\ge2$ suffices. If all states exceed $M_m$, the sum of the absolute nonroot coordinates is less than $A_0/2$. No zero subsum can contain the root. Repeatedly remove zero subsums among the other coordinates. This terminates and preserves the root, total sum, and ordered underlying position arrays. The retained vector has every nonempty subsum nonzero and real height exactly $A_0$. If the actual word has a nonone, its net nonroot sum is strictly negative, by the shifted inverse recurrence; thus at least one nonroot survives and the dimension satisfies $2\le d\le2m+1$. All-one words will be handled directly. This argument permits arbitrary phase changes and cancellations. It does not presume ordered actual valuations and does not require a boundary merger rule for the dictionary. ## Local product, gcd, and fast records Use coordinate linear forms at infinity and all primes in $S_f$ other than three. At three replace the ROOT coordinate form by the total-sum form. They are independent coordinate/sum forms. We use $|z|_p=p^{-v_p(z)}$ and the ordinary absolute value at infinity. The product of all these local forms, before projective normalization, is exactly $$ Q=\operatorname{rough}_{S_f}(a+1) 3^{-\ell-v_3(b+1)+v_3(a+1)}. \tag{7} $$ Let $g$ be the gcd of the retained coordinates and $H'=A_0/g$ their primitive height. The gcd is an $S_f$-unit since a nonroot survives. Its factors away from two and three divide $L$. The complete sum implies $2^{v_2(g)}\le b+1$, since $C$ is odd. The root implies $3^{v_3(g)}\le a+1$, since $C$ is prime to three. Therefore $$ H'\ge\frac{C2^D}{L(b+1)}. \tag{8} $$ Suppose $b\le B$ and the endpoint is a fast record, $a+G>(B+G)^2$. Then $a+1>(B+1)^2$. The shifted step bound with shift one and $D\ge\ell$ imply $$ 2^D\ge\left(\frac{a+1}{b+1}\right)^\gamma, \qquad \gamma=\frac{\log2}{\log(3/2)}>\frac53. $$ Combining with (8), $H'\ge(C/L)(a+1)^{(\gamma-1)/2}\ge(C/L)(a+1)^{1/3}$. If $a+1\ge L^{12}$ and $a\ge G$, this gives $H'\ge(a+1)^{1/4}\ge(a+G)^{1/8}$. The last inequality follows from $(a+1)^2\ge a+G$ under the stated hypothesis. The upper bound (4) and (3) give, with $D_m=100(1+\log(2C)+R)8^m$, $$ \log\log(a+G)-\log8 \le\log\log H' \le\log\log(b+G)+\log D_m. \tag{9} $$ Only the lower bound requires a fast record. For the upper bound, use $A_0\le2C3^\ell(b+1)e^{R(m+1)}$; the generous $D_m$ covers the length bound, $m+1\le2\,8^m$, and $\log(b+G)>1$. ## An effective number of meshes after pruning Write $g=2^u3^v\gamma_0$ with $(\gamma_0,6)=1$. For a retained nonroot put $A_i^+=\max(A_i-u,0)$ and $B_i^+=\max(B_i-v,0)$. The arrays remain oppositely ordered. Integer divisibility shows $$ z_i/g=\widetilde c_i2^{A_i^+}3^{B_i^+},\qquad |\widetilde c_i|\mid L. \tag{10} $$ In fact $\gamma_0\mid c_i$, and every negative residual power of two or three must divide $c_i/\gamma_0$. Cancel these factors. This proves (10), including its integrality. The clamped normalized positions $p_i=A_i^+\log2/\log H'$ and $b_i=B_i^+\log3/\log H'$ lie in $[0,1]$. Actual binary and ternary valuations exceed them by at most $\log L/\log H'$, and the normalized real coordinate is $p_i+b_i$ plus an error in the same interval. The total contribution of all other prime valuations of a nonroot is also at most $\log L/\log H'$. Set $\varepsilon=1/100$, $\varepsilon'=1/200$, $N=4000(s+1)d$, and $$ T_d=\max\{d^{200d},\exp(N(1+\log L))\}. $$ Call a word bad if $Q0$, an explicit allowance is $$ \mathcal A_m=F_m+1+ \sum_{d=2}^{2m+1}P_dL_d (\log\omega_d+\log D_m+\log8). \tag{14} $$ Summing disjoint progress intervals gives $$ \log\log(B_k+G)\le\log\log(b+G) + (k/m+1)\log2+\mathcal A_m. \tag{15} $$ For completeness the allowance is effectively exponential in $m$. Here $Q_*\le G$, $M_m+G\le(4m+3)G$, and $s\le2+\log L/\log2$. Using $d\le2m+1\le3m$, $\log d\le d$, and $\binom nk\le(en/k)^k$ in (11) gives the deliberately loose bounds $$ \begin{aligned} \log P_d&\le100(s+1)Ad\le300(s+1)Am,\\ \log L_d&\le100m,\\ \log\omega_d+\log D_m+\log8&\le100A(m+1),\\ F_m+1&\le30A(m+1). \end{aligned} $$ These hold for $m\ge1$ (in particular $A>1$); the preceding definitions give them directly also at $d=2$. There are $2m$ terms in (14). Thus $$ \mathcal A_m\le\exp(C_Wm),\qquad C_W=10^6(s+1)A. \tag{16} $$ Each counted piece has length at most $3\log_2(B_k+G)$; each of the $k+1$ free gaps has length at most $\log_2(B_k+G)$, including the last one because its entrance is at most $B_k$. Hence $t+1\le8(k+1)\log_2(B_k+G)$; for $k=0$ this follows directly from the free-gap bound. Combining with (15)--(16) proves (1). Take $m=\lfloor\log k/(4C_W)\rfloor$ once $k$ is large. The exponential allowance is at most $k^{1/4}$, so (1) implies $\log((t+1)/\log(b+G))\ll_W k/\log k$. The $m=1$ case forces $k$ past this effective range when $t$ is sufficiently large. Elementary inversion gives (2), with effective constants and onset. ## Fixed-budget exponent and scope The specialization of Evertse [1, Theorem 2] used here states that, for fixed dimension, fixed finite $S=S_f\cup\{\infty\}$, and every $\varepsilon>0$, nonzero integer coordinates with no vanishing nonempty subsum satisfy $$ \left(\prod_i\prod_{v\in S}|z_i|_v\right) \left|\sum_i z_i\right|_3 \ge c_{d,S,\varepsilon}\max_i|z_i|_3 \left(\max_i|z_i|\right)^{-\varepsilon}. $$ The constant is ineffective. For a segment of fixed cost $r$ with all states above $M_r$, apply Evertse [1], Theorem 2, to the retained nondegenerate vector with $S=S_f\cup\{\infty\}$ and $T=\{3\}$. No primitivity is required. The local product of the coordinate forms is $\operatorname{rough}_{S_f}(a+1)$ and $\max_i|z_i|_3\ge|A_0|_3=3^{-v_3(a+1)}$. Therefore (7) satisfies $Q\ge c_{r,W,\varepsilon}A_0^{-\varepsilon}$. Repeating the calculation of (13), now with arbitrary sufficiently small $\varepsilon>0$, yields $\Omega\ll_{r,W,\eta}(a+1)^{q+\eta}$, where $q=\log_3(3/2)$. Equation (4) then bounds $a$ by a constant times $b^\sigma$ for every $\sigma>1/(1-q)=\log_2 3$. If the segment visits a state at most $M_r$, the remaining suffix has shifted height at most $Z_r$ by (3). Apply this argument to each prefix to bound every state. All-one prefixes are handled directly. Finally, $b_N=2^N-1$ has $N-1$ initial ones and endpoint $2\,3^{N-1}-1$. Its logarithmic height ratio tends to $\log_2 3$, proving sharpness. The fixed-budget constants remain ineffective; the separate effective interval argument is what proves (1). The finite dictionary may contain rational shadows of any sign. The result says that an avoiding orbit cannot remain cheaply describable by that fixed dictionary. It does not say that every exceptional orbit has low dictionary cost, nor that complicated events have positive frequency. It supplies no exponential growth-rate gap or upper return remainder. ## Individual descents, examples, and positive cycles **Corollary 3 (effective non-one counts on every orbit).** There are an effective absolute constant $c>0$ such that the number $N_b(t)$ of exponents at least two in the first $t$ odd steps satisfies $N_b(t)\ge c\log t\log\log t$ for all sufficiently large $t$, with an effective threshold depending on $b$. The conclusion includes orbits after arrival at one. Indeed choose the dictionary consisting of the one-letter word $2$. Its only positive template cycle is $1$, and its piece count is at most $N_b(t)$. Thus (1) holds with $k$ replaced by $N_b(t)$ before or at first arrival at one. To handle a later time, let $h$ be that first arrival. If $h+1\ge(t+1)/2$, apply (1) at $h$, use $N_b(h)\le N_b(t)$, and add $\log2$ on its right. Otherwise $N_b(t)\ge t-h>(t+1)/2$, which directly implies the same enlarged inequality. Hence a uniform finite inequality for $N_b(t)$ holds for all $t$, with final constant $\log(16/\log2)$ in place of $\log(8/\log2)$. The inversion proving (2) is effective independently of $h$ and gives the corollary. For this dictionary the exact minimum cost counts each maximal run of twos once and each exponent at least three individually. More generally, $W=\{(2),\ldots,(H)\}$ counts each maximal constant run in a fixed finite range once, and larger exponents individually. The dictionary $W=\{(1,2),(2)\}$ also absorbs long positive shadows of the negative cycle through $-5$: the two-step affine map is $(9x+5)/8$. Its pieces can start at either phase and can end midway through a repetition. Theorem 1 applies to the optimal decomposition, with no prescribed parsing. It therefore also lower-bounds the cost of every particular admissible parsing. **Corollary 4 (effective cycle complexity).** For every fixed dictionary $W$, effective $c_W>0$ and $n_W$ exist such that a positive cycle of odd period $n\ge n_W$, outside $\mathcal C_W$, has cyclic dictionary cost at least $c_W\log n\log\log n$. Cyclic cost is the minimum over all cuts of one period and all admissible decompositions. Let $b$ be the least odd value of the cycle, and $D$ its exponent sum. Luca [4, Lemma 3.1(i)] gives $b