On the Decidability of Presburger Arithmetic Expanded with Powers

2024/07/06 by Toghrul Karimov, Karimov, Toghrul, Florian Luca +7 · 1 citation
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · pdf · doi:10.48550/arxiv.2407.05191

openalex publication_date 2024/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for any integers α, β> 1, the existential fragment of the first-order theory of the structure ⟨ ℤ; 0,1,<, +, α^ℕ, β^ℕ⟩ is decidable (where α^ℕ is the set of positive integer powers of α, and likewise for β^ℕ). On the other hand, we show by way of hardness that decidability of the existential fragment of the theory of ⟨ ℕ; 0,1, <, +, x↦ α^x, x ↦ β^x⟩ for any multiplicatively independent α,β> 1 would lead to mathematical breakthroughs regarding base-α and base-β expansions of certain transcendental numbers.

Cited by

• The Skolem Problem in rings of positive characteristic

Related

• The complexity of Presburger arithmetic with power or powers
• Undefinability of multiplication in Presburger arithmetic with sets of powers
• There is no maximal decidable expansion of the ⟨ ℕ ,\ < \ ⟩ structure
• On the Decidability of Monadic Theories of Arithmetic Predicates
• The Universal Fragment of Presburger Arithmetic with Unary Uninterpreted Predicates is Undecidable