Beatty Sequences for a Quadratic Irrational: Decidability and Applications
Preprint
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.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Model-completeness and decidability of the additive structure of integers expanded with a function for a Beatty sequenceAnnals of Pure and Applied Logic, 2024
- The additive structure of integers with the lower Wythoff sequenceArchive for Mathematical Logic, 2022
- Expansions of the group of integers by Beatty sequencesAnnals of Pure and Applied Logic, 2022
- Sumsets associated with Beatty sequencesDiscrete Mathematics, 2022
- Sumsets of Wythoff sequences, Fibonacci representation, and beyondPeriodica Mathematica Hungarica, 2021
- Sumsets associated with Wythoff sequences and Fibonacci numbersPeriodica Mathematica Hungarica, 2020
- Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidabilityTheoretical Computer Science, 2017
- Elementary Methods in Number Theory2000
- Representations of numbers and finite automataTheory of Computing Systems, 1992
- Linear numeration systems of order twoInformation and Computation, 1988