On the Decidability of Presburger Arithmetic Expanded with Powers
<|reference_start|>On the Decidability of Presburger Arithmetic Expanded with Powers: We prove that for any integers $\alpha, \beta > 1$, the existential fragment of the first-order theory of the structure $\langle \mathbb{Z}; 0,1,<, +, \alpha^{\mathbb{N}}, \beta^{\mathbb{N}}\rangle$ is decidable (where $\alpha^{\mathbb{N}}$ is the set of positive integer powers of $\alpha$, and likewise for $\beta^{\mathbb{N}}$). On the other hand, we show by way of hardness that decidability of the existential fragment of the theory of $\langle \mathbb{N}; 0,1, <, +, x\mapsto \alpha^x, x \mapsto \beta^x\rangle$ for any multiplicatively independent $\alpha,\beta > 1$ would lead to mathematical breakthroughs regarding base-$\alpha$ and base-$\beta$ expansions of certain transcendental numbers.<|reference_end|>
@article{karimov2024on,
    title={On the Decidability of Presburger Arithmetic Expanded with Powers},
    author={Toghrul Karimov, Florian Luca, Joris Nieuwveld, Jo"el Ouaknine, James
  Worrell},
    journal={arXiv preprint arXiv:2407.05191},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05191},
    primaryClass={cs.LO}
}