🔢 mathematics

State Complexity of Shifts of the Fibonacci Word

This paper demonstrates that the state complexity of automata generating shifted Fibonacci words, whether processing Zeckendorf representations in most-significant-digit-first or least-significant-digit-first order, grows logarithmically with the shift amount $c$ , approaching the information-theoretic minimum for aperiodic sequences.

Original authors: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

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, infinite tape of beads, colored either Black or White. This isn't just any random pattern; it's the Fibonacci Word, a sequence so famous in mathematics that it's like the "Golden Ratio" of strings. It goes: Black, White, Black, Black, White, Black, White, Black... and continues forever without ever repeating the same chunk twice.

Mathematicians love this tape because it's generated by a very simple machine (an automaton) with just 5 tiny gears (states). If you tell the machine "What is the 100th bead?", it crunches the number and spits out the answer instantly.

The Problem: The "Shift"

Now, imagine you want to look at the tape, but you slide it over by a few spots. Maybe you want to see the bead that was originally at position 100, but now you want to know what's at position 105. You've "shifted" the sequence by 5.

The big question the authors asked is: How complicated does the machine need to become to handle this shift?

If you shift the tape by a tiny amount (like 5 spots), the machine stays small. But what if you shift it by a huge amount, like 1,000,000 spots?

In most cases, shifting a pattern by a huge number makes the machine explode in size. It might need millions of gears to remember where it is.
However, for this specific Fibonacci tape, the authors discovered something magical: The machine stays surprisingly small. Even if you shift it by a million spots, the machine only needs a number of gears roughly equal to the number of digits in that million.

The Analogy: The Library of Infinite Books

Think of the Fibonacci Word as a library with infinite books.

The Standard Machine: A librarian who can find any page in the book if you give them the page number. They have a simple map (5 states) that works for the original book.
The Shifted Machine: Now, the librarian has to find the page, but the book has been moved. The "Page 1" is now actually "Page 1000."
The Bad News: Usually, to handle a shift of 1000, you'd need a librarian with a massive, confusing map with thousands of rooms.
The Good News (This Paper): The authors found that for the Fibonacci library, you don't need a massive map. You just need a smart index. The size of the index only grows as fast as the length of the number you are shifting by.
- Shift by 10? Small index.
- Shift by 1,000,000? Still a tiny index.
- Shift by a googol? The index is still manageable.

This is incredibly efficient. It's close to the theoretical minimum possible size for any non-repeating pattern.

How Did They Do It? (The Secret Sauce)

The authors used a mix of three tools to solve this puzzle:

The "Fibonacci Ruler" (Zeckendorf Representation):
Instead of counting in normal base-10 (1, 2, 3...), they used a special way of counting based on Fibonacci numbers (1, 2, 3, 5, 8, 13...). It's like measuring a table not with inches, but with a ruler that only has marks at 1, 2, 3, 5, and 8 inches. This ruler has a special property: you can never use two marks in a row. This "no consecutive marks" rule is the key to keeping the machine simple.
The "Golden Circle" (Diophantine Approximation):
They visualized the problem as a circle. Imagine the Fibonacci numbers spinning around a circle. The position where they land determines if the bead is Black or White. When you shift the sequence, you are essentially rotating this circle. The authors proved that no matter how far you rotate it, the "landing spots" stay organized in neat, predictable slices.
The "Robot Lawyer" (Automated Proving):
They didn't just guess; they used a computer program called Walnut. Think of Walnut as a super-strict robot lawyer. The authors wrote down the rules of the Fibonacci tape in a formal language, and the robot checked every single possible scenario to prove, beyond a shadow of a doubt, that the machine size really does stay small.

The Two Ways to Read the Tape

The paper looked at two ways to feed the number to the machine:

LSD-First (Least Significant Digit): Like reading a number from right to left (e.g., reading 123 as "3, then 2, then 1").
MSD-First (Most Significant Digit): Like reading a number normally, from left to right (e.g., "1, then 2, then 3").

Usually, reading from left to right is much harder for these machines and requires way more gears. But for the Fibonacci Word, the authors proved that both methods result in a tiny, efficient machine.

Why Does This Matter?

In the world of computer science, "State Complexity" is about how much memory a computer needs to do a job.

If you are designing a chip or a compression algorithm, you want to know: "How much space do I need to store this pattern?"
This paper tells us that the Fibonacci Word is a champion of efficiency. Even when you shift it by massive amounts, it doesn't require a supercomputer to track it. It can be handled by a tiny, elegant device.

In summary: The authors took a famous, infinite pattern, shifted it by a huge amount, and proved that the "machine" needed to generate it doesn't get bloated. Instead, it grows very slowly, like a tree that only adds a few new branches for every new digit in the number you shift by. It's a beautiful example of how deep mathematical structure leads to simple, efficient solutions.

1. Problem Statement

The paper investigates the state complexity of generating shifted versions of the Fibonacci word $f = (f_i)_{i \ge 0}$ .

Context: The Fibonacci word is a canonical example of an automatic sequence (specifically, Fibonacci-automatic). It is generated by a deterministic finite automaton with output (DFAO).
The Operation: The authors consider the shifted sequence $(f_{i+c})_{i \ge 0}$ for a fixed integer shift $c \ge 0$ .
The Question: Given that the original sequence $f$ is generated by a small DFAO (5 states for least-significant-digit-first, or lsd-first, and 2 states for most-significant-digit-first, or msd-first, in Zeckendorf representation), what is the state complexity of the minimal DFAO required to generate the shifted sequence $(f_{i+c})_{i \ge 0}$ ?
Motivation: In standard base- $k$ systems, shifting a sequence by $c$ typically requires $O(m \log c)$ states for lsd-first inputs. However, for Zeckendorf representation (Fibonacci base), standard addition transducers do not exist because addition cannot be performed in a single pass. Furthermore, for other sequences like the Thue-Morse sequence, msd-first shifts can require $O(c)$ states. The authors aim to determine if the Fibonacci word exhibits a more efficient complexity for shifts.

2. Methodology

The authors employ a hybrid approach combining automata theory, Diophantine approximation, and formal logic.

A. Mathematical Characterization of the Fibonacci Word

The core of the proof relies on a geometric characterization of the Fibonacci word using fractional parts of multiples of the golden ratio $\phi = \frac{1+\sqrt{5}}{2}$ .

Lemma 1: $f(i) = 1$ if and only if $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$ .
Lemma 2 (Shifted): $f(i+c) = 1$ if and only if $\{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$ .
This transforms the problem of generating the sequence into a problem of determining which interval modulo 1 the value $\{i\phi\}$ falls into.

B. Partitioning the Unit Interval

The authors construct specific partitions of the interval $[0, 1)$ based on the input representation (Zeckendorf representation).

For lsd-first: They define a partition $I_d(m)$ induced by the first $d$ digits of the Zeckendorf representation. They prove that the low-order bits of an integer $n$ determine the interval in which $\{n\phi\}$ lies. The endpoints of these intervals are related to $\{-k\phi\}$ .
For msd-first: They define a partition $P(r)$ based on the sequence of integers obtained by "shifting" a negative integer representation (dropping the most significant digit). This partition is shown to be consistent with the msd-first Fibonacci representation, meaning that reading a digit transitions the automaton from one interval in the partition to another specific interval within the same partition.

C. Automated Theorem Proving

A significant portion of the technical proofs, particularly regarding the consistency of partitions and the behavior of intervals under digit appending/dropping, is verified using Walnut, an automated theorem prover for automatic sequences. The authors encode the properties of the Fibonacci word and the interval mappings in first-order logic and use Walnut to rigorously verify the lemmas.

3. Key Contributions and Results

A. Main Theorem: Logarithmic State Complexity

The primary result of the paper is that the state complexity of the shifted Fibonacci word is $O(\log c)$ for both lsd-first and msd-first inputs.

Theorem 1 (lsd-first): There exists an lsd-first DFAO for $(f_{i+c})$ with $O(\log c)$ states.
Theorem 3 (msd-first): There exists an msd-first DFAO for $(f_{i+c})$ with $O(\log c)$ states.

This is a significant finding because:

It contrasts with the Thue-Morse sequence, where msd-first shifts can require $O(c)$ states.
It is close to the information-theoretic lower bound for aperiodic sequences, which is $\Omega(\frac{\log c}{\log \log c})$ .

B. Exact State Complexity Formula (lsd-first)

The authors provide an exact formula for the minimal number of states required for the lsd-first case (Theorem 2):
$\text{States} = 2(|(c)_F| + 1) + 1 - g(c)$
Where:

$|(c)_F|$ is the length of the Zeckendorf representation of $c$ .
$g(c) = 1$ if $f(c-1) = f(c-2) = 0$ , and $0$ otherwise.
This confirms that the $O(\log c)$ bound is optimal, as the number of states grows linearly with the length of the Zeckendorf representation of $c$ .

C. Construction Techniques

lsd-first Construction: The automaton tracks the interval $I_d(m)$ containing $\{n\phi\}$ . Once the input length $d$ is sufficient such that the interval $I_d(m)$ is fully contained within the target interval $J_c = (-(c+1)\phi, -(c+2)\phi)$ (or its complement), the automaton transitions to a "sink" state. The number of such "intermediate" states is bounded by the number of digits in $c$ .
msd-first Construction: The authors construct a partition $P$ by combining the endpoints of partitions $P(-(c+1))$ and $P(-(c+2))$ . Because this partition is consistent with the msd-first representation, the automaton states correspond directly to the intervals in $P$ . The number of endpoints is proportional to the number of Fibonacci numbers less than $c$ , yielding $O(\log c)$ states.

4. Significance

Resolution of a Specific Case: The paper resolves the state complexity question for the most famous aperiodic word (Fibonacci word) under the shift operation, showing it behaves "optimally" compared to other automatic sequences.
Methodological Innovation: It demonstrates the power of combining Diophantine approximation (properties of $\{n\phi\}$ ) with automata theory. The use of fractional parts to define automaton states is a novel and powerful technique for Fibonacci-automatic sequences.
Tool Validation: The successful use of Walnut to prove complex geometric properties of intervals reinforces the utility of automated theorem proving in combinatorics on words.
Generalization Potential: The authors suggest that these techniques may extend to other quadratic irrationals and potentially the Tribonacci word, opening avenues for future research into the state complexity of shifts in other numeration systems.

Summary

The paper proves that shifting the Fibonacci word by $c$ positions results in a sequence that can be recognized by a finite automaton with only $O(\log c)$ states, regardless of whether the input is read from the most or least significant digit. This is achieved by mapping the problem to the geometry of fractional parts of multiples of the golden ratio and constructing specific interval partitions that respect the structure of the Zeckendorf representation. The results highlight the unique structural efficiency of the Fibonacci word compared to other automatic sequences.