Additive systems for ℤ are undecidable

2025/08/24 by Zabolotskii, Andrei
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2508.17285

Abstract

What are the collections of sets A_i⊂ℤ such that any n∈ℤ has exactly one representation as n=a₀+a₁+\dotsb with a_i∈A_i? The answer for ℕ₀ instead of ℤ is given by a theorem of de Bruijn. We describe a family of natural candidate collections for ℤ, 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 ℤ 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.

Citations

• Undecidability of translational monotilings
• Multifactorisations and Divisor Functions
• Translational tilings of the integers with long periods

Related

• Automata and tame expansions of (ℤ,+)
• Multiplicative richness of additively large sets in ℤ^d
• Finite enumerable but undecidable collections
• On the Collatz general problem qn+1
• A p-adic Approach To Piecewise Polynomial Dynamical Systems