On the Decidability of Presburger Arithmetic Expanded with Powers

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↦ αˣ, x ↦ βˣ for any multiplicatively independent α,β > 1 would lead to mathematical breakthroughs regarding base-α and base-β expansions of certain transcendental numbers.