🔢 mathematics

Additive systems for $\mathbb{Z}$ are undecidable

This paper demonstrates that determining whether the sumset of a canonical collection of subsets of $\mathbb{Z}$ covers the entire integers is undecidable, as the problem is shown to be equivalent to the universal halting problem for Fractran and is linked to the Collatz conjecture.

Original authors: Andrei Zabolotskii

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrei Zabolotskii

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Building Numbers Like LEGO

Imagine you have a giant, infinite box of LEGO bricks. But these aren't just random bricks; they are organized into specific types or layers.

Layer 0 has small bricks (like 0, 1, 2).
Layer 1 has medium bricks (like 0, 10, 20).
Layer 2 has large bricks (like 0, 100, 200).

The Goal: Can you build any integer (positive, negative, or zero) using exactly one brick from each layer?

If you can build the number 538, you might pick a "500" brick from Layer 2, a "30" brick from Layer 1, and an "8" brick from Layer 0.
The rule is strict: You must use exactly one brick from every layer, and the sum must be unique. You can't build the number 538 in two different ways.

In math, this is called an Additive System.

Part 1: The Easy Case (Positive Numbers)

For a long time, mathematicians knew how to solve this for positive numbers only (0, 1, 2, 3...).

The Analogy: Think of a standard decimal system (base 10).
- Layer 0: Digits 0–9.
- Layer 1: Multiples of 10 (0, 10, 20...).
- Layer 2: Multiples of 100.
This works perfectly. Every positive number has exactly one "recipe" of bricks. A famous mathematician named de Bruijn figured out exactly what these "perfect recipes" look like.

Part 2: The Hard Case (All Integers)

The paper asks: What happens if we want to build negative numbers too? (..., -3, -2, -1, 0, 1, 2, 3...).

The Problem: It's much harder. You can't just use standard positive bricks. You need "negative bricks" or a weird mix of positive and negative ones.
The "Canonical Collection": The author invents a new, structured way to organize these layers. He calls them Canonical Collections. Think of them as a specific set of instructions for how to arrange your LEGO layers so they might cover every integer.

The Twist: It's a Game of "Will It Stop?"

The author realizes that checking if a Canonical Collection works (i.e., can it build every integer?) is actually the same as playing a game of "Will this process eventually stop?"

He translates the math problem into a Dynamical System (a machine that keeps running).

The Machine: You start with a number. You apply a rule to it. You get a new number. You apply the rule again.
The Question: Does this machine eventually reach Zero and stop?
- If the machine reaches zero for every starting number, then your LEGO collection is perfect (it's an additive system).
- If the machine gets stuck in a loop or runs forever for even one number, your collection is broken.

The Shocking Connections

Here is where the paper gets wild. The author proves that deciding if these LEGO collections work is equivalent to solving some of the most famous, unsolvable puzzles in mathematics and computer science.

1. The Collatz Conjecture (The 3n+1 Problem)

You've probably heard of this. It's a simple rule:

If a number is even, divide by 2.
If a number is odd, multiply by 3 and add 1.
Repeat.
The Mystery: Does this always eventually reach 1? No one knows. It's been tested for trillions of numbers, but no one has a proof.

The Paper's Discovery: The author built a specific LEGO collection where the question "Does this collection work?" is exactly the same as asking "Is the Collatz Conjecture true?"

If you could solve the LEGO problem, you would solve Collatz.
If you could solve Collatz, you would know if that LEGO collection works.

2. The Halting Problem (The "Stop or Go" Problem)

This is a concept from computer science. Imagine you have a computer program. Can you write a master program that looks at any other program and tells you: "Will this program eventually stop, or will it run forever?"

The Answer: No. It is mathematically impossible (undecidable). There is no algorithm that can solve this for every program.

The Paper's Discovery: The author created a special family of LEGO collections based on a weird programming language called Fractran.

He proved: "Does this Fractran-based LEGO collection work?" is exactly the same as asking "Does this Fractran program stop for every input?"
Since we know the "Stop or Go" question is impossible to answer for all programs, it means it is impossible to decide if these LEGO collections work.

The Conclusion: Why This Matters

The paper concludes that for these specific types of number systems, there is no general rule or algorithm that can tell you if they cover all integers.

The Metaphor: Imagine you have a box of LEGOs. Sometimes you can look at the box and say, "Yes, this builds everything." But for this specific, complex type of box, the question "Does it build everything?" is as hard as solving the Collatz mystery or predicting if a computer program will crash.
The Takeaway: Math isn't just about finding answers; sometimes, the question itself is unanswerable. The author showed that the structure of numbers is so deep and complex that it hides the same level of difficulty as the hardest problems in computing and number theory.

In short: The paper connects the simple act of adding numbers to the deepest, most unsolvable mysteries of the universe, proving that for some number systems, we can never know if they are perfect.

1. Problem Statement

The paper addresses the fundamental problem of characterizing additive systems for the set of integers ( $\mathbb{Z}$ ).

Definition: An additive system for a monoid $M$ is a collection of subsets $\mathcal{A} = \{A_0, A_1, \dots\}$ such that every element $n \in M$ can be uniquely represented as a finite sum $n = a_0 + a_1 + \dots$ , where $a_i \in A_i$ .
Context: For non-negative integers ( $\mathbb{N}_0$ ), these systems are fully characterized by de Bruijn's Theorem, which states that any additive system for $\mathbb{N}_0$ is a contraction of a "British number system" (a system with varying bases).
The Gap: The analogous problem for $\mathbb{Z}$ (representing all integers, positive and negative, uniquely) is significantly harder. While specific examples exist (e.g., negabinary or balanced ternary systems), there is no general structural characterization. The central question is: Given a specific collection of sets, is it an additive system for $\mathbb{Z}$ ? (i.e., does its direct sumset cover the entire set of integers?)

2. Methodology

The author employs a multi-step methodology combining additive combinatorics, dynamical systems, and computability theory:

A. Introduction of Canonical Collections

To generalize known examples (like negabinary and balanced ternary systems), the author defines Canonical Collections.

Structure: A collection defined by a sequence of bases $(b_i)_{i \in \mathbb{N}_0}$ (where $b_i > 1$ ) and a sequence of sets $(T_i)_{i \in \mathbb{N}_0}$ , where each $T_i$ is a complete residue system modulo $b_i$ containing 0.
Construction: The sets in the collection are $A_i = (b_0 b_1 \dots b_{i-1}) T_i$ .
Property: The sumset of any canonical collection is always direct (unique representation exists if the sum exists), but it is not guaranteed to be complete (covering all of $\mathbb{Z}$ ).

B. Translation to Dynamical Systems

The core methodological shift is translating the additive problem into a non-autonomous dynamical system.

The Map: For a given integer $n$ , the author defines a sequence of maps $f_i: \mathbb{Z} \to \mathbb{Z}$ :
$f_i(n) = \frac{n - t_i(n)}{b_i}$
where $t_i(n)$ is the unique element in $T_i$ congruent to $n \pmod{b_i}$ .
Trajectory: The "expansion" of $n$ corresponds to the trajectory $n, f_0(n), f_1(f_0(n)), \dots$ .
Equivalence: A canonical collection is complete (an additive system for $\mathbb{Z}$ ) if and only if the trajectory of every integer $n \in \mathbb{Z}$ eventually reaches 0 and stays there.

C. Reduction to Undecidable Problems

The author constructs specific instances of canonical collections where the "trajectory reaching 0" condition is mathematically equivalent to famous unsolved or undecidable problems:

The Collatz Conjecture: Constructing a collection where the trajectory mimics the $3n+1$ map.
Fractran Halting Problem: Constructing a collection where the trajectory mimics the execution of a Fractran program (a Turing-complete esoteric programming language).

3. Key Contributions and Results

Theorem 1: Equivalence to the Collatz Conjecture

The author constructs a specific canonical collection $\mathcal{A}_C$ such that:

$\mathcal{A}_C$ is an additive system for $\mathbb{Z}$ if and only if the Collatz conjecture is true.
Mechanism: The bases $b_i$ and residue sets $T_i$ are chosen such that the dynamical system $f_i$ replicates the Collatz function ( $3n+1$ for odd, $n/2$ for even) for positive integers. The proof demonstrates that any integer eventually enters the "Collatz regime" of the trajectory.

Theorem 2: Equivalence to the Universal Halting Problem

The author defines Fractran-type canonical collections based on a Fractran program $F$ .

Result: A Fractran program $F$ halts for all inputs if and only if the corresponding canonical collection $\mathcal{A}_F$ is complete.
Significance: Since the universal halting problem for Fractran is undecidable (no algorithm can determine if an arbitrary program halts on all inputs), the problem of determining completeness for this family of canonical collections is also undecidable.

Corollary 2: Undecidability

The problem of deciding whether a given Fractran-type canonical collection is an additive system for $\mathbb{Z}$ is undecidable.

This implies that there is no general algorithm to determine if a "well-behaved" (finite data description) additive system covers $\mathbb{Z}$ .

4. Significance and Implications

Resolution of a Longstanding Open Problem: The paper provides a definitive answer to the structural complexity of additive systems for $\mathbb{Z}$ . Unlike $\mathbb{N}_0$ , which has a clean characterization (de Bruijn's theorem), the integer case is shown to be computationally intractable.
Bridging Fields: It establishes a profound link between additive combinatorics (tiling and sumsets), dynamical systems (trajectory convergence), and computability theory (undecidability).
Hardness of Verification: The results suggest that verifying whether a specific set of rules generates a unique representation for all integers is as hard as solving the Collatz conjecture or the halting problem. This explains why no general characterization theorem exists for $\mathbb{Z}$ analogous to de Bruijn's.
New Perspective on Number Systems: By framing numeral systems as dynamical trajectories, the paper offers a new tool for analyzing the convergence and coverage properties of non-standard number systems.

Conclusion

Zabolotskii demonstrates that the question "Is this collection an additive system for $\mathbb{Z}$ ?" is not merely difficult but undecidable for a natural, well-behaved family of collections. By encoding the logic of the Collatz conjecture and Fractran programs into the structure of these additive systems, the paper proves that the completeness of such systems is inextricably linked to some of the most difficult problems in mathematics and computer science.