On the decidability of Presburger arithmetic expanded with powers - Karimov, T; Luca, F; Nieuwveld, J; Ouaknine, J; Worrell, J (Society for Industrial and Applied Mathematics, 2025)
We prove that for any integers α, β > 1, the existential fragment of the first-order theory of the structure ⟨Z; 0, 1, <, +, αN, βN⟩ is decidable (where α N is the set of positive integer powers of α, and likewise for β N). On the other hand, we show by way of hardness that decidability of the existential fragment of the theory of ⟨N; 0, 1, <, +, x 7→ α x , x 7→ β x ⟩ for any multiplicatively independent α, β > 1 would lead to mathematical breakthroughs regarding base-α and base-β expansions of certain transcendental numbers.