🔢 mathematics

Meta-automatic Sequences

This paper introduces the concept of meta-automatic sequences as a synthesis of meta-Fibonacci and automatic sequences, focusing on non-denestable examples $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ for which the authors establish explicit DFAO evaluations, 4-uniform morphisms, and factor complexities.

Original authors: John M. Campbell, Benoit Cloitre

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: John M. Campbell, Benoit Cloitre

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

The Big Picture: Mixing Two Types of Recipes

Imagine you are a chef trying to create a new kind of infinite recipe book. In the world of mathematics, there are two famous ways to write these recipes (sequences of numbers):

The "Self-Referential" Chef (Meta-Fibonacci):
Imagine a recipe that says, "To make the next dish, look at the taste of the dish you made three steps ago, and use that number to decide how many ingredients to add."
- The Problem: This is chaotic. The recipe refers to itself in a loop. It's like trying to pull yourself up by your own bootstraps. Mathematicians love these because they are mysterious, but they are very hard to predict. The most famous example is the Hofstadter Q-sequence, which is so tricky we don't even know if it can be written down for every single number.
The "Digital" Chef (Automatic Sequences):
Imagine a recipe that says, "To make the next dish, look at the last digit of your position number. If it's even, do X; if it's odd, do Y."
- The Benefit: This is very orderly. It's like a computer program that follows a strict set of rules based on the "digits" of the number. These are called Automatic Sequences. They are predictable and can be generated by a simple machine (a Finite Automaton).

The Paper's Goal:
The authors, John Campbell and Benoît Cloitre, asked: "What happens if we mix these two chefs together?"
They created a new type of sequence called a Meta-automatic sequence. This is a recipe where the instructions depend on the value of a previous dish (like the Self-Referential Chef), but the structure is still organized enough to be generated by a machine (like the Digital Chef).

The Magic Trick: The "Balance" Constraint

The secret sauce in this paper is a specific rule they call Balance.

Imagine you are flipping a coin for every number in your sequence.

If the number is even ( $2n$ ), you flip a coin.
If the number is odd ( $2n+1$ ), you flip the opposite side of that coin.
So, if the even number is 0, the odd one must be 1. If the even is 1, the odd is 0.

Why is this important?
Usually, mixing self-referential loops with digital rules creates a mess. But the authors discovered that if you force this "Balance" rule, the messy loops straighten out.

Think of it like a tangled ball of yarn (the meta-recursion). If you pull on the ends with a specific tension (the balance rule), the yarn suddenly snaps into a straight, neat line. Mathematically, this "snapping" turns a complex, self-referential problem into a simple, linear one that a computer can easily solve.

The Two New Sequences: M1 and M2

The authors built two specific examples of these new sequences, which they named M1 and M2.

M1 (The "Mixed" Sequence):
This sequence uses a mix of standard rules and self-referential rules.
- Analogy: Imagine a robot that usually follows a map, but occasionally stops to ask itself, "How many steps did I take last time?" and adjusts its path based on that answer.
- Result: Even though it asks itself questions, the "Balance" rule ensures the robot never gets lost. It follows a pattern that can be drawn as a simple 4-state machine.
M2 (The "Pure" Sequence):
This sequence is even more self-referential. Both of its main rules depend on its own previous values.
- Analogy: This is like a robot that only navigates by asking itself questions about its past. "Where am I? How far did I go? Now, turn based on that."
- Result: Surprisingly, this chaotic-looking robot also follows a neat pattern. In fact, the authors found a clever way to describe M2: it is just the famous Thue-Morse sequence (a well-known mathematical pattern) with a specific "mask" applied to it. It's like taking a familiar song and playing it through a specific filter; the melody changes, but the underlying rhythm is still there.

The "Denestable" Concept

The paper introduces a fancy word: Denestable.

Nested: A recipe where the instructions are buried inside other instructions (like Russian nesting dolls).
Denestable: A recipe where you can peel away the layers and find a simple, flat instruction underneath.

The authors proved that M1 and M2 are NOT denestable.

Analogy: Imagine a puzzle box. Some boxes have a secret button that opens them instantly (denestable). M1 and M2 are like boxes where the only way to open them is to solve the puzzle as it is. You can't simplify the instructions into a flat list; you must keep the self-referential loop to understand how they work. Yet, despite being "nested," they are still orderly enough to be generated by a simple machine.

Why Does This Matter?

It Breaks the Rules: Previously, mathematicians thought that if a sequence was "nested" (self-referential), it couldn't be "automatic" (machine-generated) unless it could be simplified. This paper proves that's not true. You can have a sequence that is deeply nested and perfectly orderly at the same time.
New Tools: They built specific "machines" (called DFAOs) that can generate these sequences. They also figured out exactly how complex these sequences are (how many different patterns appear as you read them).
The "Meta-Thue-Morse": They showed that these new sequences are like "cousins" of the famous Thue-Morse sequence, expanding our understanding of how order can emerge from chaos.

Summary in One Sentence

The authors discovered that if you force a chaotic, self-referential number sequence to be perfectly balanced (like a seesaw), the chaos magically organizes itself into a predictable pattern that a simple computer can generate, creating a new family of mathematical objects that are both complex and orderly.

1. Problem Statement and Motivation

The paper addresses the intersection of two distinct classes of integer sequences:

Meta-Fibonacci (Nested) Sequences: Defined by recurrences where the argument of the recursive call depends on the value of the sequence itself (e.g., Hofstadter's $Q$ -sequence: $Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))$ ). These are notoriously difficult to analyze, often lacking closed forms or even guaranteed existence for all $n$ .
Automatic Sequences: Defined by digit-based recurrences (divide-and-conquer) where $a(kn+r)$ depends on values at strictly smaller indices (e.g., $a(2n) = a(n)$ ). These are well-understood, characterized by finite automata (DFAO), and possess regular structural properties.

The Core Question: Can one construct a sequence that combines the "nested" nature of meta-Fibonacci recurrences with the structural regularity of automatic sequences? Specifically, the authors investigate whether recurrences of the form $a(kn+r) = a(\text{expression involving } a(n))$ can yield $k$ -automatic sequences, and if so, under what conditions they remain "non-denestable" (i.e., cannot be reduced to a standard digit-based recurrence without increasing the kernel size).

2. Methodology and Definitions

The authors introduce a formal framework to study these hybrid sequences:

Meta-Automatic Sequences: A sequence $U$ is $q$ -meta-automatic if its terms $U(q^{t+1}n + j)$ can be expressed as a function of previous terms where the arguments of the recursive calls may themselves depend on the values of the sequence (selectors).
Denestability: A meta-automatic recurrence is denestable if it can be rewritten as a standard digit-based recurrence (satisfying the Allouche–Shallit criterion) without increasing the dimension of the sequence's $k$ -kernel. The paper focuses on sequences that are non-denestable.
Balancedness Constraint: The study focuses on binary sequences satisfying the "balanced" property: $a(2n) + a(2n+1) = 1$ $a (2 n) + a (2 n + 1) = 1$ . This constraint is crucial because it allows the authors to linearize non-linear selectors using the field $\mathbb{F}_2$ $F_{2}$ .
- Key Lemma: For a balanced sequence, the selector $a(2n + 1 - a(n))$ is equivalent to the XOR operation: $a(2n+1) \oplus a(n)$ . This transforms a meta-recursive definition into an affine recurrence over $\mathbb{F}_2$ .

3. Key Contributions and Constructions

The paper introduces and analyzes two specific non-denestable meta-automatic sequences, $M_1$ and $M_2$ , defined via base-4 recurrences.

Sequence $M_1$ (Meta(1))

Definition: A mixed template where one branch rule is meta-automatic:
- $M_1(4n) = M_1(n)$
- $M_1(4n+2) = M_1(2n + 1 - M_1(n))$ (with complementary odd terms).
Analysis:
- The authors prove $M_1$ is 4-automatic.
- They construct a 4-state Deterministic Finite Automaton with Output (DFAO).
- Non-Denestability: They prove $M_1$ is not denestable. While the recurrence can be linearized to $M_1(4n+2) = M_1(2n+1) \oplus M_1(n)$ , the closure of the 4-kernel requires a "lifted state" of dimension 2 (tracking both $M_1(n)$ and an auxiliary term). It cannot be reduced to a recurrence depending solely on $M_1$ at fixed linear shifts of $n$ .
- Morphism: A 4-uniform morphism is derived that generates $M_1$ .

Sequence $M_2$ (Meta(2))

Definition: A "pure" two-selector template where both branch rules are meta-automatic:
- $M_2(4n) = M_2(2n + M_2(n))$
- $M_2(4n+2) = M_2(2n + 1 - M_2(n))$
Analysis:
- $M_2$ is also 4-automatic with a 4-state DFAO.
- Structural Factorization: A major result is the explicit factorization $M_2(n) = t(q(n))$ , where $t$ is the Thue–Morse sequence and $q$ is a specific bit-masking operator that zeros out bits at positions $m \equiv 2, 5 \pmod 6$ .
- Affine Structure: The state transitions of $M_2$ are governed by an affine map over $\mathbb{F}_2^2$ involving the matrix $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$ , which has order 3.
- Non-Denestability: Like $M_1$ , $M_2$ is proven to be non-denestable, requiring the lifted state space to close the kernel.

Thue–Morse Quarto Sequence ( $Q$ )

The paper also analyzes a baseline sequence $Q$ (OEIS A298952) which is 4-automatic but not meta-automatic in the same sense, serving as a comparison point for factor complexity.

4. Main Results

Existence of Non-Denestable Meta-Automatic Sequences: The paper provides the first construction of sequences that satisfy meta-recursions but are provably 4-automatic. This demonstrates that the "nested" nature of the recurrence does not preclude automaticity if balancedness constraints are applied.
Linearization Mechanism: The authors formalize how the balancedness constraint ( $a(2n)+a(2n+1)=1$ ) converts non-linear meta-selectors into $\mathbb{F}_2$ -affine maps. This allows the construction of DFAOs for sequences that would otherwise appear chaotic.
Factor Complexity:
- The paper computes the factor complexity functions $p(n)$ (number of distinct factors of length $n$ ) for $Q$ , $M_1$ , and $M_2$ .
- All three sequences have linear complexity: $p(n) = \Theta(n)$ .
- Distinctive Behavior: Despite sharing the same automaton size (4 states), $M_1$ $M_{1}$ and $M_2$ $M_{2}$ exhibit different complexity profiles.
  - $M_2$ has a piecewise linear complexity that depends on $k \pmod 3$ (where $n \approx 2^k$ ), with slopes alternating between 2 and 4.
  - $M_1$ has a different piecewise structure.
- The authors provide explicit formulas for $p(n)$ in terms of dyadic intervals.

5. Significance and Implications

Bridging Fields: The work successfully bridges the gap between the unpredictable world of meta-Fibonacci sequences and the rigid structure of automatic sequences. It shows that "meta" behavior can be tamed into "automatic" behavior through specific algebraic constraints (balance).
Refining Automaticity Criteria: The paper highlights the limitations of the Allouche–Shallit automaticity criterion. While that criterion requires arguments to be fixed linear functions of $n$ , this paper shows that sequences with value-dependent arguments can still be automatic if the dependency is linearizable over a finite field.
New Class of Sequences: The introduction of "meta-automatic" sequences opens a new avenue for research. The authors suggest that similar constructions could exist in base 3 (ternary balance) and other modular arithmetic settings.
Computational Tools: The paper utilizes the Walnut theorem prover to verify properties and generate complexity formulas, demonstrating the utility of automated reasoning in combinatorics on words.

In summary, Campbell and Cloitre demonstrate that by imposing a balancedness constraint, one can construct sequences that are defined by complex, value-dependent recurrences yet possess the elegant, finite-state structure of automatic sequences, while remaining fundamentally distinct from standard digit-based sequences due to their non-denestable nature.