Cobham's theorem for the Gaussian integers
Abstract
Assuming the four exponentials conjecture, Hansel and Safer showed that if a subset $S$ of the Gaussian integers is both $α=-m+i $- and $β=-n+i$-recognizable, then it is syndetic, and they conjectured that $S$ must be eventually periodic. Without assuming the four exponentials conjecture, we show that if $α$ and $β$ are multiplicatively independent Gaussian integers, and at least one of $α$, $β$ is not an $n$-th root of an integer, then any $α$- and $β$-automatic configuration is eventually periodic; in particular we prove Hansel and Safer's conjecture. Otherwise, there exist non-eventually periodic configurations which are $α$-automatic for any root of an integer $α$. Our work generalises the Cobham-Semenov theorem to Gaussian numerations.
Fields of Study & Subjects
Machine Learning and Algorithms
Computability
Logic
AI Algorithms
Advanced Statistical Process Monitoring
Publication details
- Journal / source
- Advances in Mathematics
- Volume
- 503
- Pages
- 111219–111219
- Publication date
- 31 August 2026
- Language
- EN