Beatty solutions of almost Golomb equations

This paper establishes the existence and uniqueness of an inhomogeneous Beatty sequence with slope $1/\sqrt{2}$ as a second monotone solution to the order-2 almost Golomb equation, characterizing its validity across a continuous family of parameters and verifying the identity for various window sizes while noting its failure for even perfect squares.

The Gist

Imagine you are trying to build a tower of blocks, but there's a strange rule you must follow: The height of the block you place at a specific spot depends on the sum of the heights of the two blocks right before it.

This is the core puzzle of the "Almost Golomb Equation." It sounds simple, but it's a self-referential loop: to know where to put the next block, you need to know the heights of previous blocks, but those heights determine where you are looking. It's like trying to write a story where the plot of Chapter 10 depends on a sentence you haven't written yet in Chapter 5.

For decades, mathematicians knew of one way to solve this: the "Greedy" method. This is like a child building a tower who always chooses the smallest possible block that fits the rules. It works, but the tower grows in a jagged, repetitive, and somewhat chaotic way.

Benoît Cloitre's new paper (dated April 2026) reveals a shocking secret: There is a second, completely different way to build this tower.

Here is the breakdown of this discovery using everyday analogies:

1. The Two Builders

Think of the sequence of numbers as a line of people waiting in a queue.

• The Greedy Builder: This builder is practical and local. They look only at the immediate past and pick the smallest number that doesn't break the rules. Their line grows in a pattern that repeats every few steps (like a rhythm of "short, tall, tall, short"). It's predictable but "jittery."
• The Beatty Builder (The New Discovery): This builder is a visionary. They don't just look at the immediate past; they follow a smooth, irrational slope (specifically $1/\sqrt{2}$, which is about 0.707). Their line grows with a gentle, flowing rhythm that never repeats exactly. It's like a perfectly smooth wave compared to the Greedy builder's jagged sawtooth.

The Surprise: Up until the 11th person in line, both builders agree on who stands where. But at person #12, they diverge. The Greedy builder repeats a number (making a "run" of two identical blocks), while the Beatty builder moves to a new number. Both are mathematically correct, but they are following completely different philosophies.

2. The "Sliding Window" Mystery

The rule involves a "sliding window." Imagine you are looking through a window that shows the last two people. The rule says: "The person standing at the position equal to the sum of the heights of the last two people must be the current person's number."

Because the "position" you are checking depends on the heights you just chose, the system is flexible.

• The Greedy solution is rigid and local.
• The Beatty solution is global and smooth. It turns out that if you shift the starting point of the Beatty builder just slightly, they can still solve a weaker version of the puzzle (a "triple-nested" equation). This creates a continuous family of solutions, like a dimmer switch that allows for a whole range of valid towers, rather than just one or two.

3. The "Magic Interval"

The paper calculates a very specific "Goldilocks Zone" (an interval of numbers) for the starting shift of the Beatty builder.

• If you start too low or too high, the tower eventually collapses (the math breaks).
• If you start just right (inside this specific interval), the tower stands forever.
• The paper proves that every starting point inside this tiny interval works for the weaker equation, but only one specific point works for the original, strict equation.

4. The "Square" Problem

The author also looked at what happens if you change the window size (looking at 3, 4, 5, or more previous blocks).

• Odd Squares (9, 25, 49...): The smooth Beatty builder works perfectly. The math lines up beautifully.
• Even Squares (4, 16, 36...): The smooth builder fails. The math breaks down. It's as if the universe has a preference for odd numbers in this specific puzzle.

5. Why Does This Matter?

You might ask, "Who cares about a weird number sequence?"
This is about understanding order in chaos.

• The Greedy solution represents systems driven by local rules (like computer algorithms or cellular automata).
• The Beatty solution represents systems driven by global, irrational harmony (like the spirals in a sunflower or the orbits of planets).

The paper shows that a single set of rules can support both types of order simultaneously. It's like finding out that a single set of traffic laws can result in both a chaotic traffic jam (Greedy) and a perfectly flowing highway (Beatty), depending on how the drivers choose to start.

Summary

Benoît Cloitre found a hidden "smooth" solution to a puzzle that everyone thought only had a "jagged" solution. He proved that this smooth solution is unique in its specific form but part of a larger family of solutions that work for a slightly relaxed version of the rules. It's a beautiful discovery showing that mathematics often has more than one "right" answer, and sometimes the most elegant answer is the one that looks the least like the obvious one.

Technical Summary

1. Problem Statement

The paper investigates the almost Golomb equation of order $r$, which seeks a non-decreasing sequence of positive integers $a(n)$ satisfying:
$$a\left(\sum_{j=0}^{r-1} a(n-j)\right) = n$$
for $n \ge 1$, with $a(k)=0$ for $k<1$.

• Context: The classic Golomb sequence (where the sum is cumulative) is unique and grows as a power law. The "almost" variant replaces the cumulative sum with a sliding window of size $r$.
• Known Solution: The "greedy" solution (the smallest non-decreasing sequence satisfying the equation) is known to be $r$-regular (automatic) with an oscillating growth ratio.
• The Gap: It was unknown whether other monotone solutions exist that are not greedy. Specifically, the paper addresses the case $r=2$ and generalizes to arbitrary $r$.

2. Methodology

The author employs a combination of analytic number theory, combinatorics on words, and computational verification:

• Asymptotic Heuristics: Assuming $a(n) \sim cn$, the equation implies $c(2cn) \approx n$, leading to $c = 1/\sqrt{2}$ for $r=2$. This suggests an inhomogeneous Beatty sequence structure.
• Beatty Sequence Analysis: The paper rigorously tests sequences of the form $a(n) = \lfloor cn + d \rfloor$ where $c = 1/\sqrt{2}$.
• Sturmian Words: The differences $\Delta(n) = a(n+1) - a(n)$ are analyzed as Sturmian words generated by irrational rotations.
• Ostrowski Numeration: The proofs utilize the Ostrowski representation of integers based on the continued fraction of $1/\sqrt{2}$ (related to Pell numbers) to handle fractional parts and carry propagation.
• Automated Theorem Proving: The author uses the Walnut theorem prover to verify the identity for specific cases up to $r=30$ by reducing the problem to first-order logic in Ostrowski numeration.
• Discrepancy Theory: The generalization to higher $r$ relies on bounding the discrepancy of fractional parts of arithmetic progressions.

3. Key Contributions and Results

A. Existence of a Second Solution for $r=2$

The paper proves the existence of a second, fundamentally different monotone solution for the order-2 equation, distinct from the greedy solution.

• Theorem 1: The sequence defined by $a(n) = \lfloor \frac{n+1}{\sqrt{2}} \rfloor$ (an inhomogeneous Beatty sequence with slope $1/\sqrt{2}$ and shift $d=\sqrt{2}/2$) satisfies the equation $a(a(n) + a(n-1)) = n$.
• Divergence: This solution agrees with the greedy solution for $n \le 11$ but diverges at $n=12$. While the greedy solution repeats values (runs of length 2), the Beatty solution has runs of length 1, maintaining a different self-consistent addressing structure.
• Uniqueness: Among Beatty sequences, this specific shift $d = \sqrt{2}/2$ is the unique solution to the strong identity.

B. The Triple-Nested Family and the Interval $I$

The paper explores a weaker equation: $a(a(a(n) + a(n-1))) = a(n)$.

• Theorem 2 & 3: There exists a continuous interval of shifts $I = [\frac{\sqrt{2}}{2}, 2(\sqrt{2}-1)]$ (length $\approx 0.121$).
  • If $d \in I$, the sequence $a(n) = \lfloor n/\sqrt{2} + d \rfloor$ satisfies the triple-nested equation.
  • If $d \notin I$, the equation fails infinitely often.
• Mechanism: For $d \neq \sqrt{2}/2$, the identity $a(f(n)) = n$ fails by a "defect" $D(n) \in \{0, 1\}$. However, the outer function $a$ absorbs this defect because $a(n+1) = a(n)$ whenever the defect is non-zero. This absorption relies on the specific alignment of the defect word with the "repeat-set" of the Sturmian sequence.

C. Structural Properties

• Sturmian Structure: The first differences of the Beatty solution form a Sturmian word of slope $1/\sqrt{2}$.
• Ostrowski Representation: The solution can be described via a digit-swap in the Ostrowski numeration system (swapping Pell denominators $q_k$ with Pell numerators $p_k$).
• Defect Morphism: At the right endpoint of the interval $I$, the defect word $D(n)$ is not Sturmian but is a morphic word generated by a specific substitution rule involving the silver ratio ($1+\sqrt{2}$).

D. Generalization to Order $r$

The results are extended to arbitrary window sizes $r$:

• General Form: The candidate solution is $a_r(n) = \lfloor \frac{n}{\sqrt{r}} + \frac{\sqrt{r}}{2} \rfloor$.
• Perfect Squares:
  • If $r = s^2$ and $s$ is odd, the identity holds exactly.
  • If $r = s^2$ and $s$ is even, the identity fails (yielding $n+1$).
• Non-Squares:
  • The identity is proven for $r=3$ and $r=5$ via case analysis of fractional parts.
  • Theorem 21: The identity holds for all non-square $r$ up to 30, verified computationally using Walnut.
  • Conjecture 22: The identity holds for all non-square $r \ge 2$. The proof reduces to a discrepancy bound $|\Phi_r(n) - r/2| < \sqrt{r}/2$.

4. Significance

1. Multiplicity of Solutions: The paper fundamentally changes the understanding of implicit functional equations in sequences. It demonstrates that "almost Golomb" equations admit multiple distinct monotone solutions (one greedy/regular, one Beatty/irrational), challenging the assumption of uniqueness often found in such recursive definitions.
2. Connection to Irrational Rotations: It establishes a deep link between self-referential integer sequences and the theory of Sturmian words, Beatty sequences, and bounded remainder sets for irrational rotations.
3. Methodological Bridge: The work bridges the gap between $k$-regular sequences (finite automata) and sequences defined by irrational slopes, showing how "defects" in one can be absorbed by the structure of the other in higher-order compositions.
4. Computational Number Theory: It provides a concrete application of the Walnut theorem prover to verify complex identities involving fractional parts and Ostrowski numeration, setting a precedent for future proofs in this domain.

5. Open Problems

The paper concludes with several open challenges:

• Proving the general conjecture for all non-square $r$ (specifically establishing the discrepancy bound for all $r$).
• Determining if the greedy and Beatty solutions are the only infinite monotone solutions for any $r$.
• Proving the Ostrowski digit-swap identity rigorously.
• Characterizing the substitution rules for the defect at the boundaries of the Beatty interval for $r \ge 3$.