Exact state complexity of the shifts of the Fibonacci–Thue–Morse sequence
Abstract
Let t(i) be the number of ones in the Zeckendorf representation of i, reduced modulo 2 (the Fibonacci–Thue–Morse sequence, OEIS A095076), and let sc(c) be the number of states of the smallest automaton with output that reads a Zeckendorf representation most-significant-digit first, reaches no state on an input containing two consecutive ones, and outputs t(i+c) on every representation of i. Moradi, Rampersad and Shallit proved sc(c)=O(c) and asked for a matching lower bound (their Problem 1: "Prove the number of states in a minimal automaton generating (t(i+c))_(i ≥ 0) is Θ(c)"). We determine sc(c) exactly for every 0 ≤ c ≤ 100: the values run from sc(0)=4 to sc(100)=568, they are all even, they are not monotone, and 5c<sc(c) ≤ 7c for 2 ≤ c ≤ 100. Each value is certified from below by a list of sc(c) pairwise inequivalent input words and from above by the minimised automaton of the Moradi–Rampersad–Shallit construction, whose transition rule — the Dekking morphism A → AD, B → A, C → CB, D → C acting on windows of the pair sequence (t(i),f(i)), f the Fibonacci word — is proved correct for every shift and every window length. The case c=0 shows that the four-state automaton for t given by Shallit is minimal. Nothing is claimed for general c: the linear lower bound of Problem 1 remains open, and we record the exact values to c=300 and an empirical first-difference rule for the size of the construction as computations only. All theorems 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
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
1fab296aa7e18d35f16bf8057b8fd7d50be07e9fe4e58dd559a9fc1e33dcbe35
Claim ledger
Stated results
T1candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T2known data2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T3routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T4known2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T5known data2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T6routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T7measurement2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
This ledger entry is reported in prose and is not bound to a Lean theorem.T8known2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T9candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
T10measurement2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Fibonacci (Zeckendorf) representation writes n as a sum of distinct non-consecutive Fibonacci numbers Fᵢ, i ≥ 2, and records the coefficients as a binary word eₜ ⋯ e₂ read most significant digit first; [x] is the value of a word and (n) the canonical word of n. A word is *valid* when it has no 11.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7