Beatty Sequences for a Quadratic Irrational: Decidability and Applications
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917378810445824 |
|---|---|
| author | Schaeffer, Luke Shallit, Jeffrey Zorcic, Stefan |
| author_facet | Schaeffer, Luke Shallit, Jeffrey Zorcic, Stefan |
| contents | Let $α$ and $β$ belong to the same quadratic field. We show that the inhomogeneous Beatty sequence $(\lfloor n α+ β\rfloor)_{n \geq 1}$ is synchronized, in the sense that there is a finite automaton that takes as input the Ostrowski representations of $n$ and $y$ in parallel, and accepts if and only if $y = \lfloor n α+ β\rfloor$. Since it is already known that the addition relation is computable for Ostrowski representations based on a quadratic number, a consequence is a new and rather simple proof that the first-order logical theory of these sequences with addition is decidable. The decision procedure is easily implemented in the free software Walnut.
As an application, we show that for each $r \geq 1$ it is decidable whether the set $\{ \lfloor n α+ β\rfloor \, : \, n \geq 1 \}$ forms an additive basis (or asymptotic additive basis) of order $r$. Using our techniques, we also solve some open problems of Reble and Kimberling, and give an explicit characterization of a sequence of Hildebrand et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08331 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beatty Sequences for a Quadratic Irrational: Decidability and Applications Schaeffer, Luke Shallit, Jeffrey Zorcic, Stefan Number Theory Discrete Mathematics Formal Languages and Automata Theory Combinatorics Logic Let $α$ and $β$ belong to the same quadratic field. We show that the inhomogeneous Beatty sequence $(\lfloor n α+ β\rfloor)_{n \geq 1}$ is synchronized, in the sense that there is a finite automaton that takes as input the Ostrowski representations of $n$ and $y$ in parallel, and accepts if and only if $y = \lfloor n α+ β\rfloor$. Since it is already known that the addition relation is computable for Ostrowski representations based on a quadratic number, a consequence is a new and rather simple proof that the first-order logical theory of these sequences with addition is decidable. The decision procedure is easily implemented in the free software Walnut. As an application, we show that for each $r \geq 1$ it is decidable whether the set $\{ \lfloor n α+ β\rfloor \, : \, n \geq 1 \}$ forms an additive basis (or asymptotic additive basis) of order $r$. Using our techniques, we also solve some open problems of Reble and Kimberling, and give an explicit characterization of a sequence of Hildebrand et al. |
| title | Beatty Sequences for a Quadratic Irrational: Decidability and Applications |
| topic | Number Theory Discrete Mathematics Formal Languages and Automata Theory Combinatorics Logic |
| url | https://arxiv.org/abs/2402.08331 |