{"id":"arxiv/2602.06066","url":"https://arxiv.org/abs/2602.06066","tags":["math.GM"],"score":0,"title":"Non-Definability of Reachability in Büchi Arithmetic for a Family of Generalized Collatz Maps","domain":"math.GM","source":"arxiv","authors":["Madhav Dhiman","Rohan Pandey"],"reviews":0,"subject":"math.GM","summary":"Let $q \\ge 3$ and $d \\ge 1$ be odd integers with $q+d$ a power of $2$. We study the generalized Collatz map $T_{q,d}$, a one-dimensional piecewise-affine map on the positive integers, and its unparameterized reachability relation $R(x,z)$, which holds when $z$ is an iterate of $x$ under $T_{q,d}$. We prove that for every such pair $(q,d)$ the relation $R$ is not first-order definable in Büchi arithmetic $\\langle \\mathbb{N}, +, V_q \\rangle$. Equivalently, no finite automaton recognizes the base-$q$ encoding of $R$. Assuming definability of $R$, we construct a first-order formula that defines…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-01","reactions":{}}