REVIEW 4 major objections 4 minor 6 references
Non-Definability of Reachability in B\"uchi Arithmetic for a Family of Generalized Collatz Maps
T0 review · 4 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The paper claims that reachability for a family of generalized Collatz maps is not first-order definable in Büchi arithmetic.
desk verdict The manuscript's advertised Büchi-arithmetic non-definability theorem is absent from the body; the submission is internally mismatched and should not go to peer review in this form. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Büchi arithmetic ⟨N,+,V_q⟩ is first-order arithmetic over natural numbers with addition and the function V_q(x) = largest power of q dividing x; its definable relations are exactly the q-automatic relations, i.e., those whose digit encodings are recognized by finite automata. The paper's announced machinery is a definability collapse: from a definition of the reachability relation R it would derive a definition of the set of powers of 2, contradicting the known fact that powers of 2 are not q-automatic for q not a power of 2 (or more generally, via the classical automata-theoretic transfer theorem). The map T_{q,d} itself is the piecewise-affine map that the paper studies.
What would settle it
Build a finite automaton that recognizes the base-q encoding of pairs (x,z) with z an iterate of T_{q,d}(x) for some admissible (q,d); existence of any such automaton disproves the theorem. Short of that, check whether the announced powers-of-2 construction actually works from an assumed first-order definition of R: a concrete failure of that derivation would expose the gap.
Extended reading notes
Core claim
The announced result is a non-definability theorem: for every odd q≥3 and d≥1 with q+d a power of 2, the reachability relation R(x,z) of the generalized Collatz map T_{q,d} — the relation 'z is some iterate of x' — has no first-order definition in the structure ⟨N,+,V_q⟩, where V_q(x) is the largest power of q dividing x. Because first-order definability in this structure coincides with recognition by finite automata reading base-q digits, this is equivalently the statement that no finite automaton can decide reachability. The proof strategy is to show that a definition of R would yield a definition of the set of powers of 2, which is impossible by a classical theorem on automata-recognizabl
Load-bearing premise
The load-bearing step is the reduction, announced in the abstract, from definability of reachability to definability of powers of 2; the supplied manuscript does not carry out or prove this reduction.
Editorial extensions
If this is right
- For every odd q≥3, d≥1 with q+d a power of 2, reachability in T_{q,d} is not q-automatic; the classical 3x+1 map's base-3 reachability is included.
- The non-definability is independent of the Collatz conjecture's truth; it concerns expressibility, not dynamics.
- The infinite family shows this logical obstruction is not an isolated accident of the classical map.
- Any finite-state device reading base-q digits is provably unable to solve reachability for these maps, so algorithms must use arithmetic beyond automatic sets.
Reading between the lines
- If the announced powers-of-2 reduction can be supplied, it would give a reusable criterion: any relation whose definability in Büchi arithmetic entails definability of powers of 2 is non-definable, potentially applying beyond the q+d-power-of-2 family.
- A likely next test is to see whether non-definability persists for maps where q+d is not a power of 2; the paper's argument suggests the special condition is what makes the reduction to powers of 2 feasible.
- The result would imply that reachability of these Collatz maps is not merely undecidable in full arithmetic but already beyond the weak arithmetic that captures regular languages — indicating a sharp syntactic boundary.
- One could attempt to identify a simpler definable consequence of reachability (e.g., a set of starting points reaching a fixed target) and test its automaticity computationally for small q,d.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The submission's advertised title and abstract claim a non-definability theorem: for odd integers q≥3 and d≥1 with q+d a power of 2, the unparameterized reachability relation R of the generalized Collatz map T_{q,d} is not first-order definable in Büchi arithmetic <N,+,V_q>, and hence is not recognized by any finite automaton. The abstract's two-sentence proof sketch says that definability of R would allow construction of a formula defining the powers of 2, and that Cobham's theorem then gives a contradiction. The full text provided, however, is a different manuscript, 'Semantic Limits of Positive Existential Reasoning in Arithmetic Dynamics,' whose main theorem concerns preservation of positive existential formulas under ring homomorphisms and whose Collatz application is about ghost realization via 2-adic cycles. A careful search of §§1–8 finds no statement or proof of the advertised theorem, no occurrence of Büchi arithmetic, V_q, the relation R, or Cobham's theorem, and no construction of a formula defining the powers of 2. The central claim is therefore unsupported in the submitted text.
Significance. If the advertised theorem were proved, it would be a significant contribution to the logical and automata-theoretic study of Collatz-type maps, giving an infinite family of such maps whose reachability relations are not regular in the natural base-q encoding. The claimed independence from universal computation and from the Collatz conjecture would make the result particularly interesting. As submitted, however, the manuscript does not deliver this result. The body's actual contribution—the Homomorphic Preservation Barrier and its Collatz illustration—is much weaker: it is a direct corollary of the standard preservation of positive existential formulas under ring homomorphisms, it applies only to a narrow fragment of first-order ring logic, and its main example is conditional on the Collatz conjecture in order to assert that the relevant property fails over Z. The body's limitations section explicitly disclaims undecidability, unprovability, and independence. The advertised non-definability theorem is entirely absent, so the paper's significance relative to its central claim is effectively nil, despite the clarity of the body's exposition and the correctness of its routine preservat
major comments (4)
- [Title/Abstract vs §§1–8] The central theorem announced in the title and abstract is not stated or proved anywhere in the body. The full text is a different manuscript, and §§1–8 contain no definition of the reachability relation R, no treatment of Büchi arithmetic <N,+,V_q>, no formula defining the powers of 2, and no invocation of Cobham's theorem. The abstract's claim that 'Assuming definability of R, we construct a first-order formula that defines the set of powers of 2' is the load-bearing reduction, but no such construction appears. This is not a presentation gap; the submitted text simply does not contain the advertised result.
- [Abstract, second paragraph] The only proof sketch is the two-sentence abstract paragraph. It omits all technical content: how T_{q,d} and R are formalized, how a definition of R in Büchi arithmetic would yield a definition of the powers of 2, why Cobham's theorem applies, and where the condition that q+d is a power of 2 is used. The condition never appears in the body. An abstract cannot serve as a derivation, especially for a non-definability result whose main work is the reduction to a known non-definable set.
- [Theorem 5.1 and Definitions 2.2–2.3] Even within the body's own framework, Theorem 5.1 is immediate from the preservation of positive existential formulas under ring homomorphisms; it is not a substantive 'barrier.' Definition 2.3's algebraic refutability is extremely narrow—it requires T_ring plus finitely many positive existential consequences to entail the negation of a positive existential property—so the theorem's scope is correspondingly limited. The paper's own Remark 5.2 acknowledges the result is a direct consequence of standard preservation, and §8.2 disclaims any conclusion about provability or independence. Thus the body cannot support the advertised non-definability claim.
- [§7.2] The Collatz illustration is conditional. To conclude Z ⊭ φ_k, the text invokes the standard Collatz conjecture; without that assumption, the 'ghost realizability' example does not establish an unconditional fact about the integers. Moreover, the periodic-orbit formula in Example 3.4 permits repeated elements, so the notion of period is nonstandard, and the 2-adic cycles do not necessarily give distinct periodic points. This weakens the illustrative force of the body's own application, independent of the advertised theorem.
minor comments (4)
- [§6, Remark 6.2] Remark 6.2 refers to 'Corollary 6.2' but the corollary is numbered 6.1.
- [Throughout] The text shifts inconsistently between first-person singular ('I' in §1 and §8) and first-person plural ('we' in §§2–6).
- [Title/Abstract vs body] The symbols R, T_{q,d}, Büchi arithmetic, and V_q used in the title and abstract are never defined in the body; if the body were intended to be the submitted paper, these definitions would be needed.
- [References] Cobham's theorem is mentioned in the abstract but is not cited in the reference list. Reference [2] is by the same authors and is cited for a restricted observation; the degree of overlap with the present body should be clarified.
Circularity Check
No circularity found; the mismatch between abstract and body is a completeness/correctness issue, not circularity.
full rationale
I walked the derivation chain in the provided text. The body's central theorem (Theorem 5.1, Homomorphic Preservation Barrier) is explicitly a direct consequence of the standard preservation of positive existential formulas under ring homomorphisms, as the paper itself states in Remark 5.2: 'Theorem 5.1 is a direct consequence of preservation of Σ+1 formulas under ring homomorphisms.' This is a standard external model-theoretic fact, not an input smuggled in as a conclusion. The 2-adic periodic cycles used in Section 7 are attributed to Lagarias [1], an external source, and the self-citation [2] is merely descriptive ('A restricted version of this observation... was developed in earlier work [2]'), not load-bearing: no uniqueness theorem, ansatz, or fitted parameter is imported from it. The abstract's advertised Büchi-arithmetic theorem and its claimed reduction to definability of powers of 2 do not appear anywhere in §§1-8; there is no construction, no invocation of Cobham's theorem, and no treatment of V_q or the relation R. That is a substantial gap in the manuscript's completeness, and the central claim is unsupported by the text provided. But an unsupported or missing derivation is not the same as a circular derivation: the paper does not define its conclusion into its premises, fit the target result into a parameter, or rely on a self-citation to force the claimed outcome. Therefore no specific circular step can be exhibited, and the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Cobham's theorem: a set recognized by finite automata in two multiplicatively independent bases is ultimately periodic; in particular the powers of 2 are not first-order definable in Büchi arithmetic <N,+,V_q> for the relevant q.
- standard math Relations definable in Büchi arithmetic <N,+,V_q> are exactly those recognized by finite automata reading base-q encodings.
- standard math Positive existential formulas are preserved under ring homomorphisms.
- domain assumption The 2-adic Collatz map has periodic points in Z_2 corresponding to closed residue-class cycles not present in the positive integers (Lagarias).
Cite this review
Pith. "Pith review of Non-Definability of Reachability in B\"uchi Arithmetic for a Family of Generalized Collatz Maps." pith.science (2026). https://pith.science/paper/7R2SMBV5
@misc{pith2026260206066,
author = {Pith},
title = {Pith review of: Non-Definability of Reachability in B\"uchi Arithmetic for a Family of Generalized Collatz Maps},
year = {2026},
howpublished = {\url{https://pith.science/paper/7R2SMBV5}},
note = {Machine review of arXiv:2602.06066}
}
abstract
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\"uchi 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 the set of powers of $2$. Cobham's theorem then rules out this set. The family includes the classical map $T_{3,1}$. The family is infinite but restricted, isolated by the condition that $q+d$ is a power of $2$ . Unlike the undecidability results of Conway, Kurtz, and Simon, the construction does not embed universal computation and does not depend on the Collatz conjecture.
Reference graph
Works this paper leans on
-
[1]
J. C. Lagarias.The3x+ 1problem and its generalizations. American Mathematical Monthly, 92(1):3–23, 1985
1985
- [2]
-
[3]
Hodges.Model Theory
W. Hodges.Model Theory. Cambridge University Press, 1993
1993
-
[4]
Robinson.Complete Theories
A. Robinson.Complete Theories. North-Holland, Amsterdam, 1956
1956
-
[5]
B. Rossman. Homomorphism preservation theorems.Journal of the ACM, 55(3):1–53, 2008
2008
-
[6]
van den Dries.Lectures on the Model Theory of Valued Fields
L. van den Dries.Lectures on the Model Theory of Valued Fields. In: Model Theory, Algebra, and Geometry, MSRI Publications, vol. 39, Cambridge University Press, 2000. 9
2000
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.