Beatty Sequences for a Quadratic Irrational: Decidability and Applications

View PDF HTML (experimental)

Abstract:Let $\alpha$ and $\beta$ belong to the same quadratic field. We show that the inhomogeneous Beatty sequence $(\lfloor n \alpha + \beta \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 \alpha + \beta \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 \alpha + \beta \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.

Subjects:

Number Theory (math.NT); Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO); Logic (math.LO)

Cite as: arXiv:2402.08331 [math.NT]

(or arXiv:2402.08331v3 [math.NT] for this version)

https://doi.org/10.48550/arXiv.2402.08331

arXiv-issued DOI via DataCite

Submission history

From: Jeffrey Shallit [view email] [v1] Tue, 13 Feb 2024 09:56:33 UTC (59 KB) [v2] Sun, 24 Mar 2024 10:41:39 UTC (59 KB) [v3] Thu, 2 Apr 2026 11:33:07 UTC (64 KB)