2-Adic Obstructions to Presburger-Definable Characterizations of Collatz Cycles

Madhav Dhiman, Rohan Pandey · 2026

Read 2-Adic Obstructions to Presburger-Definable Characterizations of Collatz Cycles by Madhav Dhiman, Rohan Pandey (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12772.txt.

Introduction

Madhav Dhiman and Rohan Pandey probe the Collatz problem with two adic arithmetic. The Collatz problem asks whether repeated halving and tripling rules always reach one. Approaches based on Presburger arithmetic try to characterize Collatz cycles in a decidable logic. The team investigate structural limits of that strategy.

They show the Collatz cycle equation has a unique solution in the two adic integers. They term this object a ghost cycle. Ghost cycles are genuine periodic orbits of the two adic Collatz map. They satisfy all local parity constraints, yet they are not ordinary integer cycles. Their existence blocks clean Presburger characterizations of true cycles.

Catalog record

CREATORMadhav Dhiman, Rohan Pandey
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12772

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

2-Adic Obstructions to Presburger-Definable Characterizations of Collatz Cycles Madhav Dhiman, Rohan Pandey Abstract I investigate structural limitations of Presburger-arithmetic–based approaches to the Collatz problem. I show that the Collatz cycle equation admits a unique solution in the 2 2 -adic integers, which I term a ghost cycle . These ghost cycles are shown to be genuine periodic orbits of the 2 2 -adic Collatz map, satisfying all local parity constraints. I prove unconditionally that the divisibility predicate 𝒟 y = { ( x , C ) ∈ ℕ 2 : ( 2 x − 3 y ) ∣ C } \mathcal{D}_{y}=\{(x,C)\in\mathbb{N}^{2}:(2^{x}-3^{y})\mid C\} , which acts as the algebraic necessary condition for integrality, is not semilinear for any fixed number of odd steps y ≥ 1 y\geq 1 . This result is established by demonstrating that the fibers of 𝒟 y \mathcal{D}_{y} exhibit unbounded periods, an obstruction to Presburger definability. Consequently, strategies relying solely on Presburger arithmetic or finite automata to define the integrality constraint cannot capture the distinction between ghost cycles and genuine integer cycles. I conclude with a heuristic argument suggesting that because ghost cycles satisfy the algebraic cycle equation, the non-existence of integer cycles cannot be proven solely through algebraic manipulation of the cycle equation itself. 1 Introduction The Collatz map T:\mathbb{N}\to\mathbb{N} is defined by T(n)=\begin{cases}n/2,&n\equiv 0\pmod{2},\\ 3n+1,&n\equiv 1\pmod{2}.\end{cases} The Collatz conjecture asserts that every positive integer eventually reaches 1 under iteration of T . Despite its elementary definition, the conjecture remains one of the most intractable problems in mathematics. The difficulty lies in the pseudo-random mixing of modular constraints (parity) and magnitude constraints (inequalities) under iteration. [ 6 , 11 , 10 ] . 1.1 Motivation A wide class of approaches to the Collatz conjecture apply linear or automata-theoretic methods. These include: • Parity-vector encodings, • Modular constraints and residue class analysis, • Finite automata representations of binary strings, • Symbolic reasoning over linear integer arithmetic. Such methods naturally fall within the expressive power of Presburger Arithmetic , the first-order theory of (\mathbb{N},+,<) first introduced in 1929 [ 8 ] . This observation motivates the following question: To what extent can the existence or nonexistence of Collatz cycles be captured within Presburger arithmetic? Rather than addressing the Collatz Conjecture directly, I study the limitations of these methods. Specifically, I analyze whether the integrality condition —the constraint distinguishing genuine integer cycles from formal algebraic solutions—can be expressed using Presburger-definable sets. Prior work by Lagarias [ 5 ] and Bernstein [ 2 ] established the relevance of 2 -adic integers to the problem, noting that solutions exist in the 2 -adic limit. My results demonstrate that the integrality constraints required to filter these 2 -adic solutions fail to be semilinear and therefore are not definable in Presburger arithmetic. Consequently, any approach that attempts to distinguish genuine integer cycles from 2 -adic ”ghost cycles” using only linear arithmetic, finite automata, or bounded congruence reasoning is inherently insufficient. 2 Background and Preliminaries To make the logical obstructions precise, we review the relevant logical and algebraic structures. 2.1 Presburger Arithmetic and Semilinear Sets Presburger Arithmetic is the first-order theory of the structure (\mathbb{N},+,<,0,1) . It allows for quantification over integers, addition, and order, but excludes multiplication between variables. This restriction makes the theory decidable, unlike full Peano arithmetic. A fundamental result by Ginsburg and Spanier [ 4 ] characterizes the sets definable in this theory. Theorem 2.1 (Ginsburg–Spanier Characterization) . A subset of \mathbb{N}^{d} is definable by a Presburger arithmetic formula if and only if it is semilinear. Definition 2.2 (Semilinear Sets) . A set L\subseteq\mathbb{N}^{d} is linear if there exist a base vector b\in\mathbb{N}^{d} and a finite set of period vectors P=\{v_{1},\dots,v_{k}\}\subset\mathbb{N}^{d} such that L=\left\{b+\sum_{i=1}^{k}\lambda_{i}v_{i}:\lambda_{i}\in\mathbb{N}\right\}. A set is semilinear if it is a finite union of linear sets. This theorem provides a geometric method to prove undecidability or undefinability: if a set’s projection or fiber structure implies it is not semilinear, it cannot be defined in Presburger arithmetic. Below is a well-known lemma that is central to the arguments in this paper. Lemma 2.3 (Unbounded Fiber Period Obstruction) . Let S\subseteq\mathbb{N}^{2} . For x\in\mathbb{N} , let S_{x}=\{y:(x,y)\in S\} be the fiber at x . If there exists a constant M such that for every x , the fiber S_{x} is eventually periodic with minimal period p(x) dividing M , then S is semilinear. Conversely, if the set of minimal eventual periods \{p(x):x\in\mathbb{N}\} is unbounded, then S is not semilinear and not Presburger-definable. Proof. If S is semilinear, it is a finite union of linear sets. The fiber of a linear set is an arithmetic progression (or finite union thereof) whose period is determined by the lattice vectors. Since there are finitely many linear components, the least common multiple of their periods provides a uniform bound M for all fibers. If the actual minimal periods p(x) grow without bound as x\to\infty , this contradicts the existence of M . ∎ 2.2 The 2-adic Integers The ring of 2 -adic integers, \mathbb{Z}_{2} , is the completion of \mathbb{Z} with respect to the 2 -adic metric |x|_{2}=2^{-v_{2}(x)} . As detailed in Mahler [ 7 ] , elements of \mathbb{Z}_{2} can be represented as formal power series: \alpha=\sum_{i=0}^{\infty}a_{i}2^{i},\quad a_{i}\in\{0,1\}. A key property relevant to our analysis is the unit structure of \mathbb{Z}_{2} . An element x\in\mathbb{Z}_{2} is a unit (invertible) if and only if x\equiv 1\pmod{2} . In contrast to \mathbb{Z} , where the only units are \pm 1 , \mathbb{Z}_{2} contains infinitely many units, allowing for unique solutions to equations like 3x+1=2^{k}x that have no integer solutions. 3 Parity Patterns and Cycle Equations We formalize the structure of a cycle by the sequence of operations performed. Definition 3.1 (Cycle-Admissible Pattern) . A parity pattern is a tuple (x,y,\vec{\sigma}) characterizing a hypothetical cycle of length \ell=x+y , where: 1. y\geq 1 is the number of odd steps ( 3n+1 ). 2. x\geq 1 is the number of even steps ( n/2 ). 3. \vec{\sigma}=(\sigma_{0},\ldots,\sigma_{y-1}) satisfies 0=\sigma_{0}<\sigma_{1}<\cdots<\sigma_{y-1}<x , representing the cumulative number of divisions by 2 performed before each odd step. For a non-trivial cycle to exist ( n_{0}>0 ), we require the logarithmic constraint 2^{x}>3^{y} , or x>y\log_{2}3 . Note that equality is impossible by the transcendence of \log_{2}3 (see Baker [ 1 ] or Gelfond [ 3 ] ). 3.1 Derivation of the Cycle Equation A cycle corresponds to a fixed point of the composed function. By tracing the affine operations n\mapsto 3n+1 and n\mapsto n/2 , we derive the standard cycle equation [ 9 ] . Proposition 3.2 . A positive integer n_{0} generates a cycle with pattern (x,y,\vec{\sigma}) if and only if: n_{0}(2^{x}-3^{y})=\sum_{k=0}^{y-1}3^{y-1-k}2^{\sigma_{k}}=:C(y,\vec{\sigma}). (1) Proof. Let m_{k} be the value of the integer at the k -th odd step, with m_{0}=n_{0} . The transition from m_{k} to m_{k+1} involves one multiplication by 3, adding 1, and dividing by 2^{s_{k+1}} , where s_{k+1}=\sigma_{k+1}-\sigma_{k} . Thus: m_{k+1}=\frac{3m_{k}+1}{2^{s_{k+1}}}\implies m_{k+1}2^{s_{k+1}}=3m_{k}+1. Multiplying both sides by 2^{\sigma_{k}} (noting that \sigma_{k+1}=\sigma_{k}+s_{k+1} ), we get: m_{k+1}2^{\sigma_{k+1}}=3(m_{k}2^{\sigma_{k}})+2^{\sigma_{k}}. Let A_{k}=m_{k}2^{\sigma_{k}} . The recurrence becomes A_{k+1}=3A_{k}+2^{\sigma_{k}} . We solve this linear recurrence by induction. • Base Case ( k=0 ): A_{0}=m_{0}2^{0}=n_{0} . • Step 1: A_{1}=3n_{0}+2^{\sigma_{0}} . • Step 2: A_{2}=3(3n_{0}+2^{\sigma_{0}})+2^{\sigma_{1}}=3^{2}n_{0}+3^{1}2^{\sigma_{0}}+2^{\sigma_{1}} . By induction, after y steps: A_{y}=3^{y}n_{0}+\sum_{k=0}^{y-1}3^{y-1-k}2^{\sigma_{k}}. However, since this is a

Read the complete text