Additive systems for \(\mathbb{Z}\) are undecidable

Andrei Zabolotskii1
1School of Mathematics and Statistics, The Open University, Milton Keynes, MK7 6AA, United Kingdom

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.

Keywords: additive systems, Collatz conjecture, undecidability