Additive systems for ℤ \mathbb{Z} are undecidable
Andrei Zabolotskii · 2025
Read Additive systems for ℤ \mathbb{Z} are undecidable by Andrei Zabolotskii (2025) 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-2508-17285.txt.
Introduction
Zabolotskii asks which stacks of sets can tile the integers by addition, each whole number hit exactly once as a sum picking one element from each set. For the counting numbers, a classic theorem of de Bruijn settles the matter. For all integers, positive and negative, he defines natural candidate stacks, called canonical collections, and probes how hard the tiling question is.
The answer is sobering. For one explicit collection, deciding whether its sums cover every integer is exactly as hard as the famous Collatz conjecture. For a tidy family of collections, the question equals the halting problem for the Fractran language, which no algorithm can decide. Some tiling questions, he proves, are simply unanswerable.
Catalog record
| CREATOR | Andrei Zabolotskii |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-17285
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Additive systems for ℤ \mathbb{Z} are undecidable Andrei Zabolotskii Abstract What are the collections of sets A i ⊂ ℤ {A}_{i}\subset\mathbb{Z} such that any n ∈ ℤ n\in\mathbb{Z} has exactly one representation as n = a 0 + a 1 + ⋯ n=a_{0}+a_{1}+\dotsb with a i ∈ A i a_{i}\in{A}_{i} ? The answer for ℕ 0 \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. 1 Introduction Let \mathbb{M} be a commutative monoid, with additive notation. Throughout this paper, \mathbb{M} is almost always going to be either the nonnegative integers \mathbb{N}_{0} or the integers \mathbb{Z} . Let \mathcal{A}=\{A_{0},{A}_{1},\dotsc\} be a collection of subsets of \mathbb{M} , finite or countably infinite. The sets {A}_{i} themselves also can be finite or infinite. We require that each {A}_{i} contains 0 and at least one more element. Definition 1 . • The sumset of \mathcal{A} is the set of sums a_{0}+a_{1}+\dotsb where a_{i}\in A_{i} , for all i , and all but finitely many a_{i} are equal to 0. The sumset of \mathcal{A} is denoted \sum\mathcal{A} or A_{0}+A_{1}+\dotsb • The sumset of \mathcal{A} is direct when for any n\in\sum\mathcal{A} , its representation as n=a_{0}+a_{1}+\dotsb is unique. The direct sumset of \mathcal{A} is denoted \bigoplus\mathcal{A} or A_{0}\oplus A_{1}\oplus\dotsb • An additive system for \mathbb{M} is a collection \mathcal{A} such that \bigoplus\mathcal{A}=\mathbb{M} . Additive systems for \mathbb{M}=\mathbb{N}_{0} are fully described by a foundational result in this area, de Bruijn’s Theorem. We state it in Section 2 . In this work, we focus on additive systems for \mathbb{M}=\mathbb{Z} , which are notoriously hard to deal with. We define canonical collections , which simultaneously generalise in a natural way additive systems for \mathbb{N}_{0} and basic examples of additive systems for \mathbb{Z} . We then switch from the additive combinatorics point of view on canonical collections to the dynamical systems perspective. This makes it possible to construct remarkable and unexpected equivalences between questions from additive combinatorics (whether certain canonical collections are additive systems for \mathbb{Z} ) and famous difficult and even undecidable problems, namely the Collatz conjecture and the universal halting problem. For the latter problem, we make use of Conway’s esoteric programming language Fractran. We introduce canonical collections in Section 3 and prove our main results, the Collatz conjecture and halting problem equivalences, in Section 4 as Theorem 1 , Theorem 2 , and Corollary 1 . The diagram in Fig. 2 shows the relationship between the sets of collections considered in this paper. 2 Additive systems for \mathbb{N}_{0} and de Bruijn’s theorem We will denote the integer interval \{0,1,\dotsc,n-1\} for some n\in\mathbb{N} by [n] . For a set A\subset\mathbb{M} and k\in\mathbb{M} , we will denote the set \{ka\mid a\in A\} by kA . We will write k\mathcal{A} for \{kA_{0},kA_{1},\dotsc\} . It is easy to find an example of an additive system for \mathbb{N}_{0} . Example 1 (decimal numeral system) . The collection \{[10],10[10],100[10],\dotsc,10^{k}[10],\dotsc\}= \displaystyle\{ \displaystyle\{0,1,2,3,4,5,6,7,8,9\}, \displaystyle\{0,10,20,30,40,50,60,70,80,90\}, \displaystyle\{0,100,200,300,400,500,600,700,800,900\}, \displaystyle... \displaystyle\} is an additive system for \mathbb{N}_{0} . Finding the representation of a number as a sum of elements of the sets from this collection is equivalent to computing its decimal expansion; e.g., 538=\dotsb+0+0+500+30+8 . Definition 2 . Let \mathcal{A} be a collection with a direct sumset and let \mathcal{B}\subset\mathcal{A} . The contraction of \mathcal{A} with respect to \mathcal{B} is the collection \left(\mathcal{A}\setminus\mathcal{B}\right)\cup\left(\bigoplus\mathcal{B}\right) . The sumset of a contraction is direct too. In particular, when \mathcal{A} is an additive system, then so are all of its contractions. Example 1 can be generalised to a collection of subsets of \mathbb{N}_{0} corresponding to a numeral system with a varying base. De Bruijn called such collections “British number systems”, referring to the systems of weight measurement units like the one presented below as Example 2 . Definition 3 . Let (b_{i})_{i\in\mathbb{N}_{0}} be a sequence of integers, called bases , such that b_{i}>1 for all i . A British number system is the collection \{A_{i}\}_{i\in\mathbb{N}_{0}} with A_{i}=\left(\prod_{j=0}^{i-1}b_{j}\right)[b_{i}] . A numeral system is a British number system such that its sequence of bases is constant. In each of the following examples, only the first few bases are given; after them, the sequence of bases continues in an arbitrary way (e.g. becomes constant 10). Example 2 . Figure 1: Mrs. Beeton’s Book of Household Management (1907), p. 126. (b_{0},b_{1},b_{2},b_{3},b_{4},\dotsc)=(16,16,28,4,20,\dotsc) Example 3 . In a British number system \mathcal{A}=\{A_{0},A_{1},\dotsc\} , let the sequence of bases begin b_{0}=2 , b_{1}=4 , b_{2}=3 . The sets [b_{0}],~~[b_{1}],~~[b_{2}] can be visualised as: The sets A_{0}=[b_{0}],~~A_{1}=b_{0}[b_{1}],~~A_{2}=b_{0}b_{1}[b_{2}] , i.e. the elements of \mathcal{A} themselves, are: Finally, the cumulative sumsets of \mathcal{A} (viewed as an ordered sequence) are the sets A_{0}=[b_{0}],~~A_{0}+A_{1}=[b_{0}b_{1}],~~A_{0}+A_{1}+A_{2}=[b_{0}b_{1}b_{2}] . They cover an ever-increasing portion of \mathbb{N}_{0} . The colour of each point n=a_{0}+a_{1}+\dotsb , a_{i}\in A_{i} , corresponds to the smallest i such that a_{i}\neq 0 . Any British number system or a contraction of such a system is an additive system for \mathbb{N}_{0} . In fact, de Bruijn showed that the converse is also true, thus completely characterising additive systems for \mathbb{N}_{0} . Theorem (de Bruijn [ 2 ] ) . Any additive system for \mathbb{N}_{0} is a contraction of a British number system. To prove this, first a lemma is proved: any additive system \mathcal{A} must contain a set A_{0} of the form [b]\oplus A_{0}^{\prime} , where A_{0} is the set that contains 1, which must exist, and b is the smallest number not in A_{0} ; and then \left(\mathcal{A}\setminus\{A_{0}\}\right)\cup\{A_{0}^{\prime}\} is of the form b\mathcal{A}^{\prime} with \mathcal{A}^{\prime} an additive system. The theorem follows from applying the lemma repeatedly. The previous sentence hides significant technical complexity, as explained in the work [ 10 ] that gives an exposition of the theorem and its proof. 3 Additive systems for \mathbb{Z} and canonical collections In this paper, we are primarily concerned with additive systems for \mathbb{Z} . As Nathanson puts it [ 10 ] , de Bruijn’s remark at the end of his 1956 paper on \mathbb{N}_{0} still accurately describes the current state of the problem: “ \langle\ldots\rangle the analogous problem for number systems representing uniquely all integers (without restriction to nonnegative ones) \langle\ldots\rangle is much more difficult than the one dealt with above, and it is still far from a complete solution.” The existing literature on additive systems for \mathbb{Z} mostly focuses on the case of additive systems of cardinality 2, i.e. \mathbb{Z}=A\oplus B . This problem, and the more general problem known as factorisation of abelian groups, have been studied since the 1940s (by de Bruijn and Hajós) and to this day. The known results are surveyed in [ 12 ] . Many of them are of the form “if \mathbb{Z}=A\oplus B and A,B satisfy certain conditions, then there exists another set A^{\prime} such that \mathbb{Z}=A^{\prime}\oplus B ”,