Exact msd-first state complexity of shifts of the Fibonacci word

Abstract

Let f=f(0)f(1)f(2)…=01001010… be the Fibonacci word and let sc(c) be the number of states of the smallest deterministic finite automaton with output that reads a Zeckendorf representation most-significant-digit first and generates the shifted word (f(i+c))_(i ≥ 0). Moradi, Popoli, Shallit and Vukusic determined the least-significant-digit-first state complexity of these shifts exactly, and proved that sc(c)=O(log c) with no explicit constant, no lower bound, and no table of values. We compute sc(c) exactly for 112 shifts — every c ≤ 100, together with eleven larger ones ranging up to c=20000 — the values running from 2 to 26; for each of these c with c ≥ 2 we show in addition that the automaton produced by their construction is already minimal, which they do not claim, and that sc(c) = |zk(c)|+ν(F_(|zk(c)|+2)-1-c), where |zk(c)| is the number of Zeckendorf digits of c and ν(d) is the index of the lowest Fibonacci number occurring in zk(d), with ν(0):=|zk(c)|. An exact computation in ℤ[φ] confirms the identity for every 2 ≤ c ≤ 4000, and its right-hand side against the size of their construction to c=20000; beyond that it is a conjecture, whose missing half we isolate. The instrument is a change of coordinate: writing varepsilon(w)=sh(w)-vv(w)φ ∈ ℤ[φ] replaces the circle used in the earlier work by an interval of length exactly one on which appending a digit is a contraction, so that the correctness of an automaton for all i becomes a finite check in ℤ[φ] — in particular no appeal to an automated prover for automatic sequences is needed. All statements below are machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   b618a0dfbb4fb96a54089611d4e34745dd61c7895e4fd66eb9cdb01b90f097c3