Almost Golomb Sequences

1. Problem Statement and Motivation

The paper investigates a family of self-referential integer sequences called Almost Golomb Sequences, which are finite-memory truncations of the famous Golomb's sequence.

• Golomb's Sequence ($G(n)$): Defined as the unique non-decreasing sequence where $n$ appears exactly $G(n)$ times. It satisfies the global rule:
  $$G\left(\sum_{k=1}^n G(k)\right) = n$$
  This sequence exhibits smooth, sublinear growth ($G(n) \sim C n^{\phi-1}$, where $\phi$ is the golden ratio) and is not $k$-regular for any $k \ge 2$.
• The Truncation: The author introduces sequences $(a_r(n))$ of order $r \ge 2$ by replacing the infinite cumulative sum with a sliding window of the $r$ most recent terms:
  $$a_r\left(\sum_{j=0}^{r-1} a_r(n-j)\right) = n$$
  The sequence is constructed greedily (minimal non-decreasing extension).
• Core Question: How does restricting the "memory" of the self-referential rule from infinite to finite ($r$) alter the asymptotic behavior, regularity, and combinatorial structure of the sequence?

2. Methodology

The paper employs a hybrid of constructive combinatorics, automata theory, and computer-assisted proof verification.

• Run-Length Analysis: The authors analyze the "runs" (consecutive occurrences) of values in the sequence. They establish that for order $r$, the run lengths are bounded, and the starting positions of runs follow a specific recurrence.
• Denesting (Divide-and-Conquer): A central technique is "denesting," where the implicit definition is transformed into explicit recurrence relations based on the base-$r$ representation of $n$ (e.g., formulas for $a(rn+i)$ in terms of $a(n)$).
• Correction Sequences: For $r \ge 3$, the denesting formulas are not purely linear; they require binary correction sequences (denoted $\epsilon, \eta$, etc.) that are $r$-automatic. These sequences account for the discrete oscillations in the growth.
• Automata Theory: The paper utilizes the Allouche–Shallit criterion to prove $r$-regularity. It constructs Deterministic Finite Automata with Output (DFAO) to generate the correction sequences.
• Computer Verification: For $r=4$ and $r=5$, the authors use the Walnut theorem prover to certify the derived recurrences and the automaticity of the correction sequences, bridging the gap between heuristic pattern recognition and rigorous proof.

3. Key Contributions and Results

A. Universal $r$-Regularity

Theorem 2.9: For every $r \ge 2$, the almost Golomb sequence $a_r(n)$ is $r$-regular.

• Unlike Golomb's sequence (which is not $k$-regular), the finite-memory constraint forces the sequence into the realm of automatic/regular sequences.
• The difference sequence $d(n) = a(n+1) - a(n)$ is shown to be $r$-automatic.

B. Explicit Denesting Formulas

The paper provides explicit $r$-adic recurrence formulas for small $r$:

• $r=2$ (Dyadic):
  $$a(2n) = a(n) + a(n+1) - 1$$
  $$a(2n+1) = a(n) + a(n+1)$$
  This leads to a Mallows-type nested recurrence: $a(n+1) = 1 + a(n+1 - a(a(n)+1) + a(a(n)-1))$.
• $r=3$ (Triadic): Formulas involve a correction sequence $\epsilon(n)$ (1 if $n$ is in specific intervals, 0 otherwise).
  $$a(3n) = a(n-2) + a(n-1) + a(n) + 1 + \epsilon(n-1)$$
  $$a(3n+1) = a(n-1) + a(n) + a(n+1)$$
  $$a(3n+2) = a(n) + a(n+1) + a(n+2) - 1 - \epsilon(n)$$
• $r=4, 5$: Similar structures exist but involve multiple correction sequences ($\epsilon_0, \dots, \epsilon_3$ for $r=4$ and a pair $(\epsilon, \eta)$ for $r=5$). These were identified mathematically and certified by Walnut.

C. Non-Convergence of $a(n)/n$

Theorem 7.1, 7.5, 7.6, 7.8: For all $r \ge 2$, the ratio $a(n)/n$ does not converge.

• Instead of a single limit, the ratio oscillates between two distinct rational limit points.
• Examples:
  • $r=2$: Limits are $3/4$ and $2/3$.
  • $r=3$: Limits are $8/15$ and $5/8$.
  • $r=4$: Limits are $25/48$ and $10/21$.
• This contrasts sharply with Golomb's sequence, where $a(n)/n^{\phi-1}$ converges to a constant. The oscillation is driven by the discrete nature of the sliding window.

D. Combinatorial Interpretations

• $r=2$: The multiplicity of a value $m$ is determined by the second most significant bit of $m-1$. The difference sequence $d(n)$ follows a Boolean cellular automaton rule: $d(2n)=1$ and $d(2n+1) = d(n) \land d(n+1)$.
• $r=3$: The difference sequence exhibits a palindromic substitution rule within triadic blocks, where the block structure is determined by the run length $L_n$.

E. The "Golomb Meta-Structure" Conjecture

The paper presents a striking numerical observation (Section 9):

• Let $M(r)$ be the maximum multiplicity (maximum number of times any integer appears) in the sequence of order $r$.
• Let $j_k$ be the smallest order $r$ such that $M(r) \ge k$.
• Conjecture: The differences between these thresholds follow Golomb's sequence itself:
  $$j_{k+1} - j_k = G(k)$$
  $$j_k = S(k-1) + 2$$
  where $S(k)$ is the partial sum of Golomb's sequence.
• This suggests that the sequence generated by truncating Golomb's rule "reappears" as the law governing the complexity of the family of truncated sequences. The paper reduces this to two boundary conjectures: the Prefix Conjecture ($a_r(r) = G(r-1)$) and the Domination Lemma.

4. Significance

1. Transition from Analytic to Automatic: The paper demonstrates a phase transition in self-referential sequences. Moving from infinite memory (Golomb) to finite memory (Almost Golomb) shifts the sequence from analytic power-law growth to linear growth with automatic oscillations.
2. New Class of Regular Sequences: It establishes a rich family of $r$-regular sequences with explicit divide-and-conquer structures, expanding the known landscape of sequences defined by sliding-window recurrences.
3. Combinatorial Depth: The discovery of cellular automaton rules and palindromic substitutions for these sequences provides new tools for analyzing self-referential structures.
4. Meta-Structure Phenomenon: The conjecture that Golomb's sequence governs the hierarchy of its own finite-memory variants is a profound and unexpected connection, suggesting a deep underlying algebraic structure in self-referential systems.

5. Open Questions

The paper concludes with several open problems, including:

• The behavior of the Cesàro means for $r \ge 3$.
• Whether the full multiplicity sequence $N_r(n)$ is always $r$-automatic.
• The nature of the phase transition as $r \to \infty$ (does the oscillation vanish to recover Golomb's smooth growth?).
• Generalizations to "gap-$s$" sequences where the window is not contiguous.

In summary, Cloitre's work rigorously characterizes the "Almost Golomb" family, proving their regularity, detailing their oscillatory growth, and uncovering a surprising meta-structural link back to the original Golomb sequence.