Additive systems for \(\mathbb{Z}\) are undecidable
Journal of Combinatorial Mathematics and Combinatorial Computing · 11.04.2026 · 130 · 241-253
DOI: 10.61091/jcmcc130-16 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 11.04.2026. Verfasst von Andrei Zabolotskii.
Abstract (Originalsprache)
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.
Zitieren
APA
Zabolotskii, A. (2026). Additive systems for \(\mathbb{Z}\) are undecidable. Journal of Combinatorial Mathematics and Combinatorial Computing, 130, 241-253. https://doi.org/10.61091/jcmcc130-16
Vancouver
Zabolotskii A. Additive systems for \(\mathbb{Z}\) are undecidable. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;130:241-253. doi:10.61091/jcmcc130-16
BibTeX
@article{Zabolotskii2026,
author = {Zabolotskii, Andrei},
title = {Additive systems for \(\mathbbZ\) are undecidable},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2026},
volume = {130},
pages = {241--253},
doi = {10.61091/jcmcc130-16}
}
EUVIMED