Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse
Abstract
For a strictly increasing G:ℕ→ℕ with G(0)≥ 1, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit G[t](0) has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive G. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and G has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.
Related
- Step Recursion: Rational Strides and Exact Inclusion Orders over the Reals
- A Dirichlet Mixed-Membership Model for Exact Multivariate Distributional Credibility
- Spectra: Exact Component Transport for Test-Time Prior Adaptation in Simulation-Based Inference
- Parity families and signed spectra: kernel averaging, near-Ramanujan bounds, and exact circulant models
- Exact analytical spectra of an effective field-modified radial Schrödinger equation by the Nikiforov--Uvarov method
BibTeX
@misc{osipov2026step,
title = {{Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse}},
author = {Kirill Osipov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39774},
eprint = {2610.39774},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39774},
}
RIS
TY - UNPB
TI - Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse
AU - Kirill Osipov
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39774
UR - https://arxiv.org/abs/2610.39774
AB - For a strictly increasing G:ℕ→ℕ with G(0)≥ 1, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit G^[t](0) has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive G. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and G has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.
ER -