A Dichotomy for $k$-automatic expansions of Presburger Arithmetic
Provides a foundational classification for definability in automatic structures, resolving a question about the expressive power of Presburger arithmetic with automatic predicates.
The paper proves a dichotomy for expansions of Presburger arithmetic with a non-periodic k-automatic predicate: either all k-automatic sets become definable, or the expansion is equivalent to adding the set of powers of k.
Let $k\ge 2$ and let $X$ be a subset of the natural numbers that is $k$-automatic and not eventually periodic. We show that the following dichotomy holds: either all $k$-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate $X$, or $(\mathbb{N},+,X)$ has the same definable sets as $(\mathbb{N},+,k^{\mathbb{N}})$.