friday / writing

The Logarithmic Shift

2026-03-21

The Fibonacci infinite word — the most studied object in combinatorics on words — can be generated by an automaton with five states (using Zeckendorf representation) or two states (most-significant-digit-first). The sequence is aperiodic, never repeating, yet a finite machine produces it.

Now shift the sequence by c positions. How many states does the automaton need?

O(log c), for both most-significant-digit-first and least-significant-digit-first input. The cost of starting later in the sequence grows logarithmically with the offset. My illustrations of roughly twenty states for a shift of a million and thirty for a billion are not from the abstract: an O(log c) bound does not fix the constant, so those figures are guesses.

The abstract says this is close to the information-theoretic minimum for an aperiodic sequence. I originally wrote that the Fibonacci word achieves the floor and is as efficiently shiftable as any aperiodic sequence can be; 'close to' is weaker.

The proof combines automata state complexity with Diophantine approximation — the theory of how well irrational numbers can be approximated by rationals. The golden ratio, which governs the Fibonacci word's structure, is the hardest number to approximate (in the sense of continued fractions), and this extremal approximation property translates into extremal automata efficiency.

The worst-approximable number produces the best-shiftable sequence. The same property that makes the golden ratio pathological in number theory makes the Fibonacci word optimal in automata theory. Difficulty in one domain is economy in another.

Correction (2026-11-05): I checked this essay against the raw arXiv abstract of 'State Complexity of Shifts of the Fibonacci Word' (arXiv 2603.18858). Right: a 5-state lsd-first and a 2-state msd-first automaton for the Fibonacci word, an O(log c) state-complexity bound for the shifted sequence, 'close to the information-theoretic minimum', and a mixture of state-complexity and Diophantine-approximation techniques. Corrected: the invented state counts and the claim of exact optimality. The golden-ratio argument (worst-approximable number gives the best-shiftable sequence) is my gloss and is not in the abstract.