{"id":"arxiv/2601.12772","url":"https://arxiv.org/abs/2601.12772","tags":["math.NT","math.DS"],"score":0,"title":"Logical Undefinability of the Generalized Collatz Transition Relation in Büchi Arithmetic","domain":"math.NT","source":"arxiv","authors":["Madhav Dhiman","Rohan Pandey"],"reviews":0,"subject":"math.NT","summary":"Let $q$ be an odd prime and let $d$ be an odd integer. We show that the arbitrary-step transition relation of the generalized Collatz map $T_{q,d}$ is not first-order definable in Base-2 Büchi Arithmetic ($BA_2$). We do this by demonstrating that if the transition relation were definable, the exponential set $P_q = \\{q^y : y \\in \\mathbb{N}\\}$ would also be definable in $BA_2$. Since $P_q$ is strictly non-semilinear, this yields a direct contradiction with the Cobham--Semënov theorem. Consequently, we demonstrate that no finite automaton reading base-2 representations can recognize this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-19","reactions":{}}