Exact Residue-Class Lifts of Hofstadter Recursions: Interleaving, Composition, and Rigidity

We construct exact transfers between nested recurrences without an additive forcing term, R(n)=R(n-R(n-a))+R(n-R(n-b)). Multiplying both delays and all values by an integer D gives reversible interleavings: solutions with divisible initial values split into D independent smaller-delay solutions. To go beyond repeated blocks, we introduce phase-dependent maps on the residue labels. An exact parent-index identity reduces the lifted recurrence to a finite homogeneous balance criterion, with positivity and strictly backward evaluation built into the construction. The criterion yields nonzero corrected lifts of Golomb's quasilinear solution and of the published V and H companion solutions, whose branches have constant, square-root, and linear growth. Within the canonical three-phase Golomb lift ansatz, nonidentity middle-phase maps exist precisely for D>=4. For the companions, a three-map normal form is complete within the canonical five-phase ansatz; two subclasses admit explicit classifications, and cyclic maps occur at every scale D>=3. We determine minimal initial blocks, value-support densities, and linear summatory corrections. Products of residue tables are associative, while changing their order can alter the arithmetic of the resulting sequence. In particular, two constructions with the same delays (6,12) have summatory functions differing by N/3+O(1). Finite certificates enumerate the small-scale cases completely. A clock-rigidity theorem and a congruence obstruction identify limits of the transfer mechanisms. Archive contentsComplete reproducibility archive with manuscript PDF and LaTeX, four vector figures and integer figure data, full initial blocks, all Golomb tables through D=4, all companion tables through D=4, independent recursion audits, printed finite certificates, the original author-supplied checker, provenance, and SHA-256 integrity hashes.