Existential Büchi arithmetic in two coprime bases

The problem asks whether the existential fragment of arithmetic with addition, order, and power predicates for two coprime bases is decidable. The reported result claims a positive answer when the bases are multiplicatively independent.

Known results

• For integers $\alpha,\beta>1$, the existential fragment of $\langle\mathbb{Z};0,1,<,+,\alpha^{\mathbb{N}},\beta^{\mathbb{N}}\rangle$ is stated to be decidable; the proof uses Diophantine approximation and Baker’s theorem on linear forms in logarithms.
• For multiplicatively independent bases, the full first-order theory is undecidable, with undecidability already appearing at bounded quantifier complexity; the negative result is attributed to Hieronymi and Schulz.

August 2026 preprint

The preprint On existential Büchi arithmetic in two coprime bases claims that the existential-fragment question is settled positively for coprime, multiplicatively independent bases. This would establish a decidable fragment inside an expansion whose full first-order theory is undecidable; the claim has not been independently verified in the retrieved material.

Current status (as of August 2026): The existential fragment is claimed decidable for coprime multiplicatively independent bases, but the claim is unverified; the full first-order theory remains undecidable.