On a sequence of Kimberling and its relationship to the Tribonacci word

This paper proves Clark Kimberling's conjectures regarding his 2017 binary sequence by utilizing the Walnut theorem-prover to establish its connection to the infinite Tribonacci word and to determine its subword complexity and critical exponent.

The Gist

Imagine you are a detective trying to solve a mystery about a very specific, endless pattern of lights: 0s and 1s. This pattern, which we'll call Sequence B, was discovered by a mathematician named Clark Kimberling in 2017. He had a hunch about how this pattern behaved, but he couldn't prove it.

This paper is the story of how three other mathematicians (Lubomíra, Edita, and Jeffrey) solved the mystery. They didn't just guess; they used a combination of old-school logic and a super-powered computer robot to prove Kimberling was right.

Here is the breakdown of their adventure, explained without the heavy math jargon.

1. The Magic Recipe (How the Pattern Grows)

Kimberling didn't just write down a random list of numbers. He created a recipe, like a set of instructions for a baker, but instead of flour and eggs, he used "0s" and "1s."

• The Starting Dough: You start with 00.
• The Rules:
  • If you see a single 0, it stays 0.
  • If you see a single 1, it turns into 10.
  • If you see a double 00, it explodes into 0101.
• The Process: You take your current string, break it into the biggest possible chunks of 00, 0, or 1, and apply the rules to every chunk at once. Then you repeat.

If you keep doing this forever, the pattern settles into a stable, infinite stream of lights: 0100101100...

2. The First Mystery: How Fast Does It Grow?

Kimberling guessed that the length of these strings followed a very specific, predictable rhythm. He wrote down a formula (a sequence of numbers) and said, "The length of the string after step 100 will be exactly this number."

The Solution:
The authors proved this was true. They treated the string like a Lego tower. They realized that no matter how complex the tower gets, it's always built from just three types of Lego blocks: 1, 10, and 100. By counting how many of each block appeared in the previous step, they could predict exactly how many would appear in the next step. It turned out the growth followed a "Tribonacci" rhythm (like the famous Fibonacci sequence, but adding the last three numbers instead of just the last two).

3. The Second Mystery: The Secret Connection

Here is the most magical part. The authors discovered that Sequence B isn't actually its own unique creature. It's a disguise.

• The Real Star: There is a famous, well-studied pattern called the Tribonacci Word. It's like the "King" of these types of patterns.
• The Disguise: The authors found that if you take the King (the Tribonacci Word) and apply a simple translation code (swapping 0s for 10s, 1s for 0s, and 2s for 1s), you get Sequence B.
• The Analogy: Imagine the Tribonacci Word is a person speaking French. Sequence B is that same person speaking French, but wearing a hat and a coat that makes them look like a different person. Once you take off the coat (apply the math), you realize they are the same person all along.

4. The Super-Tool: "Walnut"

How did they prove all this? They used a tool called Walnut.

Think of Walnut as a robot lawyer.

• You don't tell the robot how to solve the problem step-by-step.
• Instead, you tell the robot the rules of the game (the logic of the sequence) and ask it a specific question: "Is it true that this pattern never has three 1s in a row?"
• The robot then checks every single possibility, from the beginning of time to the end of time, and gives you a definitive "TRUE" or "FALSE."

The authors wrote a computer program in a special language that Walnut understands, and the robot confirmed all of Kimberling's guesses were correct.

5. The Final Clues: Complexity and Repetition

The paper ends by answering two final questions about Sequence B:

1. How "busy" is the pattern? (Factor Complexity)

   • If you look at a short slice of the pattern, how many different combinations can you find?
   • The authors proved that Sequence B is "busy" in a very specific, balanced way. It's not too chaotic, and not too boring. It has exactly twice as many unique patterns as its length (a property shared by a special class of patterns called "Rote words").

2. How much does it repeat? (Critical Exponent)

   • Does the pattern ever get stuck in a loop? Like 10101010?
   • The authors calculated the "maximum repetition" allowed in the pattern. They found that the pattern can repeat itself, but it hits a hard ceiling. It can never repeat more than about 3.19 times. It's like a song that can have a chorus repeated a few times, but if it repeats too much, it breaks the song's structure.

The Big Picture

This paper is a celebration of collaboration between human intuition and machine power.

• Kimberling was the explorer who found a strange new island and drew a map with some question marks.
• The Authors were the cartographers who used a high-tech satellite (Walnut) and old-school math to fill in the map, proving the island's geography was exactly as the explorer suspected.

They showed that even in the world of abstract numbers, there are hidden connections (like the link to the Tribonacci Word) and beautiful, predictable rhythms waiting to be discovered.

Technical Summary

Here is a detailed technical summary of the paper "On a sequence of Kimberling and its relationship to the Tribonacci word" by Dvořáková, Pelantová, and Shallit.

1. Problem Statement

The paper addresses a sequence $B$ (OEIS A288462) defined by Clark Kimberling in 2017. The sequence is generated by a specific set of "inflation rules" applied iteratively to a starting block $B_0 = 00$. The rules involve factoring the current string into maximal blocks of $00$,$0$, and$1$, and then applying substitutions:

• $00 \to 0101$
• $0 \to 0$
• $1 \to 10$

Kimberling made several conjectures regarding this sequence, including:

1. Length Conjecture: The length of the $i$-th iterate, $|B_i|$, follows a specific recurrence relation ($c_i = 2c_{i-1} - c_{i-4}$).
2. Index Conjectures: The positions of the $n$-th $0$and$n$-th$1$in the sequence follow linear approximations involving the Tribonacci constant$\psi$.
3. Structural Properties: The paper aims to determine the factor complexity (number of distinct substrings of length $n$) and the critical exponent (the supremum of powers $w^k$ appearing in the word) of the infinite limit word $B$.

The challenge lies in the fact that the generation rules are not a simple morphism (substitution on individual letters) but depend on the context of maximal blocks, making standard combinatorial analysis difficult.

2. Methodology

The authors employ a hybrid approach combining combinatorial word theory and automata-theoretic theorem proving:

• Automata and Walnut: A significant portion of the work utilizes Walnut, a theorem-prover for automatic sequences. The authors construct a Deterministic Finite Automaton with Output (DFAO) that computes the $n$-th letter of $B$ given $n$ in Tribonacci representation. This allows for the rigorous verification of properties (such as balance and index bounds) via first-order logic.
• Derivation from Tribonacci Word: The authors establish a structural link between $B$ and the infinite Tribonacci word ($TR$), which is the fixed point of the morphism $0 \to 01, 1 \to 02, 2 \to 0$. They prove that$B$is the image of$TR$ under a specific morphism composed with a letter-to-word mapping.
• Bispecial Factor Analysis: To determine factor complexity and critical exponent, the authors analyze bispecial factors (factors that can be extended both to the left and right in multiple ways). They utilize known results about bispecial factors in the Tribonacci word and map them to $B$ using the derived morphism.
• Return Words: The critical exponent is calculated using the ratio of the lengths of bispecial factors to their shortest return words, applying a theorem by Dolce et al.

3. Key Contributions and Results

A. Proof of Kimberling's Conjectures

• Lengths: The authors prove that $|B_i| = c_i$ for all $i \ge 0$, where $c_i$ satisfies the recurrence $c_i = 2c_{i-1} - c_{i-4}$. They achieve this by decomposing $B_i$ into blocks ($1, 10, 100$) and showing the counts of these blocks satisfy the Tribonacci recurrence.
• Index Bounds: They prove precise bounds for the indices of the $n$-th $0$($I_0(n)$) and$n$-th$1$($I_1(n)$):
  • $|\lfloor \psi n \rfloor - I_0(n)| \le 2$
  • $|\lfloor \gamma n \rfloor - I_1(n)| \le 3$
  • Here, $\psi \approx 1.839$ is the Tribonacci constant, and $\gamma = (\psi^2+1)/2 \approx 2.191$. This confirms Kimberling's conjectures with tighter error bounds.

B. Relationship to the Tribonacci Word

The paper establishes that $B$ is not an arbitrary sequence but is structurally derived from the Tribonacci word. Specifically:
$$B = 0 \cdot f(TR)$$
where $f$ is a morphism defined by $0 \to 10, 1 \to 0, 2 \to 1$. This connection allows the authors to transfer properties from the well-studied Tribonacci word to$B$.

C. Factor Complexity

The authors prove that $B$ is a Rote word.

• Result: The factor complexity of $B$ is $P_B(n) = 2n$ for all $n \ge 1$.
• Significance: This places $B$ in a specific class of binary sequences with low complexity, similar to Sturmian words but with a slightly higher complexity factor.

D. Critical Exponent

The authors determine the critical exponent of $B$, denoted $ce(B)$, which represents the maximum power of a repeated factor in the sequence.

• Result: $ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$.
• Method: They identified the bispecial factors of $B$ and their shortest return words. By analyzing the limit of the ratio of the length of the bispecial factor to its return word, they derived the exact critical exponent. This value is identical to the critical exponent of the Tribonacci word.

E. Balance Property

Using Walnut, the authors proved that $B$ is 3-balanced but not 2-balanced. This means that for any two factors of the same length, the difference in the number of $1$s is at most 3.

4. Significance

• Validation of Conjectures: The paper provides rigorous proofs for all of Kimberling's conjectures regarding sequence A288462, moving them from empirical observations to mathematical facts.
• Methodological Primer: The paper serves as a guide on how to analyze sequences generated by complex, non-morphic inflation rules. It demonstrates the power of combining structural analysis (morphisms, return words) with computational verification (Walnut).
• Connection to Tribonacci Dynamics: By linking $B$ to the Tribonacci word, the authors show that despite the complex generation rules, the sequence inherits the deep arithmetic and combinatorial properties of the Tribonacci system.
• Automata Construction: The construction of the DFAO for $B$ in Tribonacci representation is a significant technical contribution, enabling future automated proofs regarding the sequence's properties.

In summary, the paper successfully deciphers the structure of Kimberling's sequence, proving it is a morphic image of the Tribonacci word with specific complexity and repetition properties, and validates all associated conjectures using a blend of theoretical derivation and automated theorem proving.