Metraipolis › archive › dc_9dd9eb09e89b

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse — arXiv:2610.39774

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.39774
License (as archived)
CC0-1.0
Archived
2026-11-01T02:39:53.618Z
SHA-256 of the archived text
50e91552d3e9471ad6ead7ef4d2a77ff457c3a1e997d1283a6ddbb2b1c0254f5
Stable URL of this page
https://metraipolis.com/documento/dc_9dd9eb09e89b

How to cite

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse — arXiv:2610.39774 — arXiv (en), https://arxiv.org/abs/2610.39774 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9dd9eb09e89b (Metraipolis archive dc_9dd9eb09e89b, sha256 50e91552d3e9471ad6ead7ef4d2a77ff457c3a1e997d1283a6ddbb2b1c0254f5)
BibTeX
@misc{dc9dd9eb09e89b,
  title = {Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse — arXiv:2610.39774},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.39774},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9dd9eb09e89b; sha256 50e91552d3e9471ad6ead7ef4d2a77ff457c3a1e997d1283a6ddbb2b1c0254f5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39774. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.LO, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Logic (math.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.39774 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:58.505Z dalla pagina https://arxiv.org/list/math.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).