On existential Büchi arithmetic in two coprime bases

Abstract

For multiplicatively independent natural numbers $\alpha$ and $\beta$, Villemaire showed in 1992 that the first-order theory of Presburger arithmetic expanded with both Büchi predicates $V_{\alpha }$ and $V_{\beta }$ is undecidable, as it encodes multiplication. In recent years, Hieronymi and Schulz showed that Presburger arithmetic expanded with the weaker power predicates ${\alpha }^{\mathbb{N}}=\{{\alpha }^n:n\in \mathbb{N}\}$ and ${\beta }^{\mathbb{N}}$ is also undecidable, while Karimov et al. showed that the existential fragment of this theory is decidable. These results left open the natural problem of determining the decidability of the existential fragment of Villemaire's original expansion. We settle this question for coprime $\alpha$ and $\beta$. Specifically, we give a quantifier-elimination argument that proves the decidability of the existential fragment of $\mathsf{FO}(\mathbb{Z};<,+,V_{\alpha },V_{\beta })$.