A Fibonacci theorem for Collatz trajectories via modular graph structure

Abstract

Let $T(n)=n/2$ if $n$ is even and $T(n)=(3n+1)/2$ if $n$ is odd. We prove that for each $m\ge 1$, exactly $F(m+1)$ odd integers $n$ in $\{1,\dots ,2^m\}$ have the property that none of the iterates $T(n),T^2(n),\dots ,T^{m-1}(n)$ lies in the residue class $4(\mathrm{mod}6)$, where $F(m+1)$ is the $(m+1)$-th Fibonacci number; the proportion decays at rate $(\phi /2{)}^m$, $\phi =(1+\sqrt{5})/2$. Equivalently, these are the odd $n\le 2^m$ for which no two consecutive terms of $n,T(n),\dots ,T^{m-1}(n)$ are even. The proof uses the directed graph $G$ of Collatz transitions modulo $6$ and its unique absorbing strongly connected component $G^{\prime }=G[\{1,2,4,5\}]$. Removing vertex $4$ from $G^{\prime }$ yields a subgraph of spectral radius $\phi$, against $\rho (G^{\prime })=2$; the Fibonacci count follows from this spectral gap. We construct an explicit bijection ${\Psi }_m:\{1,\dots ,6\cdot 2^m\}\to {\mathcal{P}}_m(G)$ onto the directed paths of length $m$ in $G$. We further show that no vertex of $G^{\prime }$ is dispensable: removing any single vertex reduces the spectral radius strictly below $2$, with hierarchy $1<\sqrt{2}<\phi <2$. In particular, every positive cycle of $T$ must visit residue class $2(\mathrm{mod}6)$, and a flow conservation identity forces this class to account for more than $18\%$ of the steps in any such cycle.

arXiv comment26 pages, 1 figures, 0 tables