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

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.

Publication Details

Journal
ArXiv.org
Published
2025-08-24
Primary Topic
Geochemistry and Geologic Mapping
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

ArXiv.org
Geochemistry and Geologic Mapping
article

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

article en

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.

ArXiv.org
Openalex Percentile: Top 64%
Geochemistry and Geologic Mapping
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Additive systems for $\mathbb{Z}$ are undecidable · ArXiv.org (2025) | TGRS Research Map | TGRS