🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

This paper establishes that inhomogeneous Beatty sequences generated by quadratic irrationals are synchronized via finite automata, enabling a simple decision procedure for their first-order logical theory and resolving open problems regarding their additive basis properties.

Original authors: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical machine that takes a number, does some math to it, and spits out a new number. Specifically, this machine calculates a famous type of number sequence called a Beatty sequence. If you feed it the number $n$ , it gives you the result of $\lfloor n\alpha + \beta \rfloor$ (which means: multiply $n$ by a special number $\alpha$ , add a little bit $\beta$ , and round down to the nearest whole number).

For a long time, mathematicians wondered: Can we build a simple, rule-following robot (a "finite automaton") that can check if a specific output $y$ actually came from a specific input $n$ using this formula?

The answer, according to this paper by Luke Schaeffer, Jeffrey Shallit, and Stefan Zorcic, is YES, but only if the special numbers $\alpha$ and $\beta$ belong to a specific family of numbers called quadratic irrationals (numbers involving square roots, like the Golden Ratio or $\sqrt{2}$ ).

Here is the breakdown of their discovery using simple analogies:

1. The Magic Language: Ostrowski Representations

To make the robot work, we can't just use normal counting (1, 2, 3...). We have to speak a secret language called Ostrowski representation.

The Analogy: Think of normal counting as writing numbers in base-10 (using digits 0–9). The Ostrowski system is like a custom language where the "place values" aren't powers of 10, but are instead based on a specific irrational number (like the Fibonacci numbers).
Why it matters: In this secret language, the relationship between the input $n$ and the output $y$ becomes a pattern that a simple robot can recognize. It's like switching from a chaotic jumble of letters to a sentence with perfect grammar that a spell-checker can instantly verify.

2. The "Synchronized" Robot

The authors prove that for these specific numbers, the sequence is "synchronized."

The Analogy: Imagine a dance floor. You have two dancers: one representing the input number ( $n$ ) and one representing the output number ( $y$ ). They are dancing in perfect lockstep.
The Robot's Job: The robot watches them dance side-by-side. It doesn't need to do complex math to know if they are partners. It just looks at their steps (their digits in the secret language). If the steps match the specific rhythm of the Beatty sequence, the robot says "Yes, they are a pair!" If not, it says "No."
The Breakthrough: The paper shows that for quadratic irrationals, this dance is so regular that a robot with a finite number of memory states (a simple machine) can do it perfectly.

3. The "Walnut" Calculator

The authors didn't just prove this theoretically; they built a tool called Walnut to do the work for them.

The Analogy: Think of Walnut as a super-powered calculator that speaks "Logic." Instead of you doing the math, you just ask it questions in plain English (translated into logic), like: "Is every number bigger than 12 the sum of two numbers from this sequence?"
The Result: Walnut builds the robot (the automaton) automatically and checks the answer. If the answer is "True," it gives you a mathematical proof. If "False," it gives you a counter-example.

4. What Can We Do With This? (The Applications)

Once you have this robot, you can solve puzzles that were previously impossible or very hard to solve. The paper uses this tool to answer several "open problems" (math questions that had been sitting unanswered for years):

The "Additive Basis" Puzzle: Can you make every large number by adding together $r$ numbers from this sequence? (e.g., Can you make every number by adding two numbers from the sequence?) The robot can decide this instantly.
Solving Riddles: They solved specific riddles posed by mathematicians Don Reble and Graham about patterns in these sequences.
The "Swappage" Mystery: They proved a conjecture about a sequence where numbers are swapped based on whether they are even or odd, showing exactly what the resulting pattern looks like.
Fractional Parts: They even figured out how to compare the "leftover" parts of numbers (fractional parts) using this robot, solving a problem about how numbers are arranged on a circle.

5. The Big Picture: Decidability

The most profound takeaway is Decidability.

The Analogy: Before this, asking complex questions about these sequences was like asking a genie for a wish without knowing if the genie could grant it. Sometimes the answer was "Maybe," or "We don't know."
The New Reality: The authors proved that for this whole family of sequences, there is always a definite Yes or No answer, and we have a mechanical recipe (the robot) to find it. There are no "unsolvable" mysteries left in this specific mathematical neighborhood.

Summary

In short, the authors discovered that for a specific class of numbers involving square roots, the relationship between an input and its Beatty sequence output is so orderly that a simple computer program can verify it. They built a tool (Walnut) to automate this, allowing them to solve decades-old math puzzles and prove new theorems in a matter of seconds.

It turns out that even in the wild world of irrational numbers, there is a hidden rhythm that a simple machine can understand.

1. Problem Statement

The paper addresses the decidability and structural properties of inhomogeneous Beatty sequences of the form $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ , where $\alpha$ and $\beta$ are real numbers belonging to the same quadratic field (i.e., $\mathbb{Q}(\sqrt{d})$ for some square-free integer $d$ ).

Specifically, the authors investigate:

Whether these sequences are synchronized (meaning a finite automaton can verify the relationship $y = \lfloor n\alpha + \beta \rfloor$ given the representations of $n$ and $y$ ).
Whether the first-order logical theory of these sequences (with addition) is decidable.
Applications of this decidability to open problems in additive number theory, combinatorics on words, and specific conjectures regarding sequences in the On-Line Encyclopedia of Integer Sequences (OEIS).

2. Methodology

The core methodology relies on the intersection of automata theory, number theory, and logic, implemented via the software tool Walnut.

Ostrowski Numeration Systems: The authors utilize the Ostrowski representation of integers based on a quadratic irrational $\gamma$ . Unlike standard base- $k$ representations, Ostrowski representations use the denominators of the convergents of the continued fraction of $\gamma$ . For quadratic irrationals, these representations allow the addition relation ( $x+y=z$ ) to be recognized by a finite automaton.
Synchronized Sequences: A sequence is "synchronized" if a finite automaton can accept pairs of representations $(n, y)$ if and only if $y = s_n$ . The authors prove that inhomogeneous Beatty sequences for quadratic irrationals are synchronized.
Theorem 9 (Main Structural Result): The authors prove that if $0 < \gamma < 1$ $0 < γ < 1$ is a quadratic irrational with a purely periodic continued fraction, and $\alpha, \beta \in \mathbb{Q}(\gamma)$ $α, β \in Q (γ)$ , then the sequence $(\lfloor n\alpha + \beta \rfloor)$ $(⌊ n α + β ⌋)$ is $\gamma$ $γ$ -Ostrowski synchronized.
- Key Lemma: They utilize a matrix approach to continued fractions to show that $\lfloor n\gamma \rfloor$ can be expressed linearly in terms of Ostrowski digits, allowing the construction of a synchronized automaton.
- Closure Properties: They leverage the fact that synchronized sequences are closed under linear combinations, composition, and floor functions with integer coefficients.
Decidability via Walnut: Since the sequences are synchronized and addition is computable in the Ostrowski system, the first-order theory of these sequences is decidable. The authors use Walnut, a theorem-prover for automatic sequences, to construct the necessary automata and evaluate logical formulas.
Converse Proof (Theorem 28): They prove that if a Beatty sequence is synchronized, then $\alpha$ and $\beta$ must belong to the quadratic field generated by the underlying continued fraction, establishing a necessary and sufficient condition.

3. Key Contributions and Results

A. Theoretical Foundations

Synchronization of Quadratic Beatty Sequences: The paper establishes that for any $\alpha, \beta$ in the same quadratic field, the inhomogeneous Beatty sequence is synchronized. This provides a new, simpler proof for the decidability of the first-order theory of these sequences with addition.
Converse Theorem: The authors prove that synchronization implies the parameters $\alpha$ and $\beta$ must lie in the quadratic field associated with the automaton's numeration system.
Additive Basis Decidability: It is shown to be decidable whether a set $\{\lfloor n\alpha + \beta \rfloor\}$ forms an additive basis (or asymptotic additive basis) of order $r$ . The smallest such order $r$ is effectively computable.

B. Applications and Solving Open Problems

The authors apply their decision procedure to solve several specific problems:

Reble's Conjectures: They prove three conjectures by Don Reble regarding the existence of monochromatic arithmetic progressions of length 3 in the Fibonacci word. They characterize the sets of integers $r$ for which these progressions occur using the sequences A189377, A189378, and A189379.
Graham's Question: They solve a special case of a question by Ronald Graham regarding "eventual covering families" (ECF). They prove that for pairs $(\alpha_i, \beta_i)$ in the same quadratic field, it is decidable whether every sufficiently large integer belongs to exactly one set $S(\alpha_i, \beta_i)$ .
Hildebrand et al. Sequence: They provide an explicit characterization of a sequence $\tilde{c}(n)$ studied by Hildebrand, Li, Li, and Xie, proving that $0 \le c(n) - \tilde{c}(n) \le 2$ and constructing the automaton for the difference.
Kimberling's Swappage Problem: They provide an alternate proof of Kimberling's conjecture regarding the "lower even swappage sequence" (OEIS A141104), showing it relates to the Beatty sequence of $\phi^3$ . They also characterize four related sequences (A141105–A141107).
Sums-Complement Sets: They prove that the set of integers that cannot be written as the difference of two elements of a quadratic Beatty sequence is itself an automatic sequence. They compute the specific automaton for the case $\alpha = \sqrt{7}$ .
$\sqrt{2}$ Sequences: They resolve conjectures and provide automata for seven OEIS sequences related to $\sqrt{2}$ (including A097508, A001951, A003151, etc.), proving identities and relationships between them.
Fractional Parts: They extend the method to handle comparisons of fractional parts $\{\alpha x\} < \{\alpha y\}$ by converting them into floor function inequalities, allowing the ordering of fractional parts on the unit circle to be decided.

4. Significance

Algorithmic Number Theory: The paper demonstrates that deep questions in additive number theory and combinatorics on words, which were previously intractable or required ad-hoc proofs, can be solved mechanically using finite automata and first-order logic.
Unification: It unifies the study of Beatty sequences, Sturmian words, and quadratic irrationals under the framework of synchronized sequences and Ostrowski numeration.
Practical Implementation: The work highlights the power of Walnut as a research tool. The authors show that complex theorems can be verified in seconds, turning abstract decidability results into practical computational proofs.
Resolution of Open Problems: The paper settles multiple long-standing conjectures (Reble, Kimberling, Irwin, Dekking) that had remained open for years, providing definitive answers and explicit automata for the sequences involved.

In summary, this paper establishes a robust framework for analyzing quadratic Beatty sequences, proving their logical decidability, and leveraging this to solve a wide array of specific, previously open problems in mathematics.