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

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+\cdots$ 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.

11 pages