pith. sign in

arxiv: 2508.17285 · v2 · submitted 2025-08-24 · 🧮 math.CO · cs.LO

Additive systems for mathbb{Z} are undecidable

Andrei Zabolotskii This is my paper

Pith reviewed 2026-05-18 21:46 UTC · model grok-4.3

classification 🧮 math.CO cs.LO
keywords additive systemsunique sum representationsundecidabilityFractranCollatz conjecturedynamical systemscanonical collectionsinteger coverings
0
0 comments X

The pith

Deciding whether canonical collections of integer sets give unique sums covering all of Z is undecidable for a natural family of them.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks which collections of subsets of the integers allow every integer to be written uniquely as a sum with one term from each set. De Bruijn's theorem settles the analogous question over the non-negative integers, but the authors introduce canonical collections as the natural candidates over all of Z. They translate the covering question into dynamical systems and prove that, for one such collection, coverage is equivalent to the Collatz conjecture while, for a well-behaved family, it is equivalent to the universal halting problem for Fractran programs and therefore undecidable.

Core claim

There is a well-behaved family of canonical collections for which the question of whether their sumset equals all of Z is equivalent to the universal halting problem for Fractran and is therefore undecidable, via a translation of the covering question into dynamical systems that preserves the undecidability.

What carries the argument

Canonical collections of subsets of Z, together with the translation of their unique-sum covering condition into the language of dynamical systems.

If this is right

  • For at least one canonical collection the covering question is equivalent to the Collatz conjecture.
  • No algorithm exists that can decide full coverage for every member of the well-behaved family.
  • Additive unique-representation problems over Z inherit undecidability from computability theory through this reduction.
  • De Bruijn-type classification theorems cannot be expected to be decidable when extended from N_0 to Z.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar dynamical encodings may render other additive-basis or tiling questions over Z undecidable as well.
  • One could look for explicit canonical collections whose failure to cover Z is provable by direct construction rather than by reduction to halting.
  • The result suggests a direct bridge between additive combinatorics and classical undecidability results that could be explored in other abelian groups.

Load-bearing premise

The dynamical-system translation of the additive covering question for canonical collections is faithful and does not change whether the problem is decidable.

What would settle it

A concrete canonical collection and a corresponding Fractran program such that the collection's sumset covers Z exactly when the program halts (or fails to match in either direction).

Figures

Figures reproduced from arXiv: 2508.17285 by Andrei Zabolotskii.

Figure 1
Figure 1. Figure 1: Mrs. Beeton’s Book of Household Management (1907), p. 126. (b0, b1, b2, b3, b4, . . .) = (16, 16, 28, 4, 20, . . .) 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The sets of collections considered in this paper. A numeral system is specified by [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

What are the collections of sets ${A}_i\subset\mathbb{Z}$ such that any $n\in\mathbb{Z}$ has exactly one representation as $n=a_0+a_1+\dotsb$ with $a_i\in{A}_i$? The answer for $\mathbb{N}_0$ instead of $\mathbb{Z}$ is given by a theorem of de Bruijn. We describe a family of natural candidate collections for $\mathbb{Z}$, which we call canonical collections. Translating the problem into the language of dynamical systems, we show that the question of whether the sumset of a canonical collection covers the entire $\mathbb{Z}$ is difficult: specifically, there is a collection for which this question is equivalent to the Collatz conjecture, and there is a well-behaved family of collections for which this question is equivalent to the universal halting problem for Fractran and is therefore undecidable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines canonical collections of subsets of Z such that every integer has a unique sum representation from the collection. It translates the covering question (whether the sumset equals all of Z) into a dynamical system on Z, shows equivalence to the Collatz conjecture for one explicit collection, and establishes that for a well-behaved family of such collections the covering question is equivalent to the universal halting problem for Fractran programs, implying undecidability.

Significance. If the claimed equivalences hold, the result is significant: it furnishes an explicit reduction from a natural additive-combinatorial decision problem on Z to a known undecidable problem, extending de Bruijn's theorem from N0 to Z. The dynamical-systems translation supplies a concrete mechanism for transferring undecidability and may be reusable for other covering questions. The manuscript provides a clear reduction strategy and names the target family explicitly.

major comments (2)
  1. [§4] §4 (dynamical-systems translation): the claim that the orbit behavior of the induced map on Z is in bijective correspondence with unique sum representations for canonical collections is load-bearing for the undecidability transfer. The text asserts faithfulness but does not supply an explicit verification that every non-covering instance maps to a non-halting Fractran computation (and conversely) without introducing extraneous orbits or fixed points that lack counterparts in the original sumset.
  2. [§3] Definition of canonical collections (early in §3): the condition that every n has exactly one representation must be preserved under the dynamical encoding; if the map from collections to dynamical systems allows multiple orbits to correspond to the same additive representation, the equivalence to Fractran halting fails to be exact and the undecidability conclusion does not follow.
minor comments (2)
  1. Notation for the sumset and the dynamical map should be unified across sections to avoid switching between A_0 + A_1 + … and the orbit notation.
  2. The paper would benefit from an explicit small example of a canonical collection and its corresponding Fractran program to illustrate the reduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and insightful comments on our manuscript. We address each major comment below and have revised the paper accordingly to clarify the bijective correspondence and preservation of uniqueness.

read point-by-point responses

  1. Referee: [§4] §4 (dynamical-systems translation): the claim that the orbit behavior of the induced map on Z is in bijective correspondence with unique sum representations for canonical collections is load-bearing for the undecidability transfer. The text asserts faithfulness but does not supply an explicit verification that every non-covering instance maps to a non-halting Fractran computation (and conversely) without introducing extraneous orbits or fixed points that lack counterparts in the original sumset.

    Authors: We agree that an explicit verification strengthens the argument. In the revised manuscript, we have added a new proposition in §4 that constructs the explicit bijection between the set of unique sum representations and the orbits of the induced dynamical system. This proposition verifies that non-covering sumsets correspond precisely to non-halting Fractran programs, with no extraneous orbits or fixed points introduced by the encoding. The construction ensures that every orbit corresponds to a unique representation by design of the canonical collection. revision: yes

  2. Referee: [§3] Definition of canonical collections (early in §3): the condition that every n has exactly one representation must be preserved under the dynamical encoding; if the map from collections to dynamical systems allows multiple orbits to correspond to the same additive representation, the equivalence to Fractran halting fails to be exact and the undecidability conclusion does not follow.

    Authors: The dynamical encoding is defined in such a way that it directly encodes the unique representation into the orbit trajectory. Specifically, the map on Z is induced by the generating functions or the shift corresponding to the summands in the canonical collection. By the uniqueness condition in the definition of canonical collections, each representation maps to a distinct orbit, and conversely. We have expanded the discussion in §3 to include a lemma proving that the encoding preserves the one-to-one correspondence, thereby ensuring the equivalence is exact and the undecidability result holds. revision: yes

Circularity Check

0 steps flagged

Explicit reduction to Fractran halting; derivation self-contained with no circular steps

full rationale

The paper defines canonical collections and translates the additive covering question into dynamical systems on Z. It then exhibits an explicit family of such collections for which the covering property is equivalent to the halting behavior of arbitrary Fractran programs. Because the equivalence is constructed directly from the definitions (rather than fitted to data or derived from a self-citation chain) and the undecidability is imported from the independently established undecidability of universal Fractran halting, the central claim does not reduce to its own inputs by construction. No self-definitional, fitted-prediction, or load-bearing self-citation patterns appear in the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The argument rests on standard arithmetic and set-theoretic properties of the integers together with the definition of canonical collections and a dynamical-systems encoding; no numerical parameters are fitted and no new physical or mathematical entities beyond the canonical collections are postulated.

axioms (1)
  • standard math Standard axioms of integer arithmetic and set theory suffice to define sums and uniqueness of representations.
    Invoked when translating additive covering into dynamical systems.
invented entities (1)
  • canonical collections no independent evidence
    purpose: A family of natural candidate collections of sets for which the covering question on Z is studied.
    Introduced in the paper as the objects whose covering behavior is shown to be undecidable in some cases.

pith-pipeline@v0.9.0 · 5674 in / 1329 out tokens · 44580 ms · 2026-05-18T21:46:02.876723+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 1 internal anchor

  1. [1]

    Deciding stability and mortality of piecewise affine dynamical systems

    Vincent D. Blondel et al. “Deciding stability and mortality of piecewise affine dynamical systems”. In: Theoretical Computer Science 255 (2001), pp. 687–696. doi: 10 . 1016 / S0304-3975(00)00399-6

    work page 2001

  2. [2]

    On number systems

    N. G. de Bruijn. “On number systems”. In: Nieuw Arch. Wisk. (3) 4 (1956), pp. 15–17

    work page 1956

  3. [3]

    A 3 x + 1 survey: Number theory and dynamical systems

    Marc Chamberland. “A 3 x + 1 survey: Number theory and dynamical systems”. In: The ultimate challenge: the 3x + 1 problem. AMS, 2010

    work page 2010

  4. [4]

    FRACTRAN: A Simple Universal Programming Language for Arith- metic

    J. H. Conway. “FRACTRAN: A Simple Universal Programming Language for Arith- metic”. In: Open Problems in Communication and Computation . Springer, 1987

    work page 1987

  5. [5]

    Chapter 7. Integer Tilings

    Stanley Eigen et al. “Chapter 7. Integer Tilings”. In: Weakly wandering sequences in ergodic theory. Springer, 2014

    work page 2014

  6. [6]

    Undecidability of translational monotilings

    Rachel Greenfeld and Terence Tao. “Undecidability of translational monotilings”. In: J. Eur. Math. Soc. (2025). doi: 10.4171/JEMS/1673. arXiv: 2309.09504 [math.CO]

    work page doi:10.4171/jems/1673 2025

  7. [7]

    Tiling the integers with aperiodic tiles

    Franck Jedrzejewski. “Tiling the integers with aperiodic tiles”. In: Journal of Mathematics and Music 3 (2009), pp. 99–115. doi: 10.1080/17459730903040915

    work page doi:10.1080/17459730903040915 2009

  8. [8]

    Translational tilings of the integers with long periods

    Mihail N. Kolountzakis. “Translational tilings of the integers with long periods”. In: El. J. Comb. 10 (2003), #R22. doi: 10.37236/1715

    work page doi:10.37236/1715 2003

  9. [9]

    Multifactorisations and Divisor Functions

    Ambrose D. Law, Matthew C. Lettington, and Karl Michael Schmidt. “Multifactorisations and Divisor Functions”. arXiv: 2303.12042 [math.NT]

    work page arXiv

  10. [10]

    Additive systems and a theorem of de Bruijn

    Melvyn B. Nathanson. “Additive systems and a theorem of de Bruijn”. In: The American Mathematical Monthly 121 (2014), pp. 5–17. doi: 10.4169/amer.math.monthly.121. 01.005. arXiv: 1301.6208 [math.NT]

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4169/amer.math.monthly.121 2014

  11. [11]

    Puzzle #4 — The n-Category Caf´ e (comment)

    Mike Stay. Puzzle #4 — The n-Category Caf´ e (comment). https://golem.ph.utexas. edu/category/2006/10/puzzle_4.html#c005735. 2006

    work page 2006

  12. [12]

    7.3 Tiling the integers

    S´ andor Szab´ o and Arthur D. Sands. “7.3 Tiling the integers”. In: Factoring groups into subsets. CRC Press, 2009. School of Mathematics and Statistics, The Open University, Milton Keynes, MK7 6AA, United Kingdom andrei.zabolotskii@open.ac.uk 10

    work page 2009