🔢 mathematics

State Complexity of Shifts of the Fibonacci Word

本論文は、フィボナッチ無限語のシフトされた系列を生成するオートマトンの状態数が、入力形式（最上位桁先頭または最下位桁先頭）にかかわらず $O(\log c)$ であることを、状態複雑性の手法とディオファントス近似を組み合わせることで示しています。

原著者： Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

公開日 2026-03-20

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🌟 物語の舞台：「フィボナッチ語」という不思議なリズム

まず、**フィボナッチ語（Fibonacci word）**というものを想像してください。
これは、0 と 1 だけで作られた無限に続く文字列です。
01001010... というように、ある決まり（ルール）に従って作られます。

ルール： 「0」は「01」に、「1」は「0」に変わっていく。
結果： このルールを何回も繰り返すと、決まりきったリズム（周期）には収まらず、永遠に新しいパターンが生まれます。これを**「非周期的なリズム」**と呼びます。

このリズムは、自然界の葉の並びや貝殻の螺旋など、美しいパターンとして知られています。

🤖 主人公：「自動販売機」のような機械（オートマトン）

このリズムを読み取るために、私たちは**「自動販売機（オートマトン）」**のような小さな機械を使います。

入力： 機械に「何番目のリズムか（番号）」を数字として入力します。
出力： 機械は「その番号の文字は 0 か 1 か」を答えます。

この機械には**「状態（メモリ）」**というものがあって、これが多ければ多いほど、複雑な計算ができる代わりに、機械自体が大きくなります。

状態数＝機械の複雑さ
状態数が少ない＝シンプルで効率的な機械

🚀 問題：「少しずらす」だけで機械は大きくなる？

ここで、**「シフト（ずらす）」**という操作を考えます。
例えば、元のリズムが 01001... だったとします。

0 番目から読む： 01001...
10 番目からずらして読む： 010...（10 番目以降だけを取り出す）

この「10 番目からずらして読む」という新しいリズムを作る機械は、元の機械よりもどれくらい複雑になるでしょうか？

❌ 一般的な予想：「ずらす量」に比例して巨大化

普通の数字の並び（例えば 10 進法）でこの操作をすると、ずらす量（ $c$ ）が大きくなるほど、機械は巨大になります。

10 ずらすなら 10 倍の大きさ。
100 ずらすなら 100 倍の大きさ。
予想： ずらす量 $c$ に比例して、機械のサイズは $O(c)$ になるはずだ。

✅ この論文の発見：「驚くほどシンプル！」

しかし、このフィボナッチ語の場合、予想とは全く違うことがわかりました。
ずらす量 $c$ がどんなに大きくても、必要な機械のサイズは**「 $c$ の対数（ $\log c$ ）」**で済むのです。

例え話：
- 一般的なリズム：1000 番目をずらすには、1000 個の部屋がある巨大な工場が必要。
- フィボナッチ語：1000 番目をずらすのに必要なのは、たったの10 個の部屋がある小さな事務所。

なぜこんなにシンプルで済むのか？
それは、フィボナッチ語が持つ**「黄金比（ $\phi$ ）」という不思議な性質のおかげです。この性質のおかげで、機械は「ずらす量」そのものを記憶する必要がなく、「ずらす量の桁数（数字の長さ）」**だけを覚えていればいいからです。

🔍 2 つの読み方：「右から」か「左から」か

この研究では、数字の読み方によって 2 つのパターンを調べました。

右から読む（lsd-first）：
- 例：123 を「3, 2, 1」と読む。
- 結果：シンプルに済む（ $O(\log c)$ ）。
- 理由： フィボナッチ数の性質上、下位の桁（右側）の情報だけで、どの区間にあるかが決まるからです。
左から読む（msd-first）：
- 例：123 を「1, 2, 3」と読む。
- 結果：これも驚くほどシンプルに済む（ $O(\log c)$ ）。
- 理由： ここが最も面白い点です。通常、左から読む場合は計算が複雑になりがちですが、フィボナッチ語の場合は、**「黄金比の小数部分」**という幾何学的な性質を使って、機械の設計を最適化できました。

🧩 研究の手法：数学と AI の共演

この結果を証明するために、著者たちは以下の 3 つの武器を組み合わせて使いました。

ディオファントス近似（数値の近似）：
- 黄金比という「無理数」の性質を使って、数字が円周上のどこに位置するかを精密に予測する技術。
状態複雑性（オートマトンの理論）：
- 機械をどう設計すれば最小の部品で済むかを考える技術。
Walnut（ウォルナット）：
- 自動定理証明機（AI の一種）。人間が「こうなるはずだ」と仮説を立てると、AI が論理的に「正しい/間違い」を厳密にチェックしてくれます。

🎯 結論：なぜこれが重要なのか？

この研究は、**「非周期的な（規則的ではない）リズムを扱う際、どれだけ効率化できるか」**という限界に迫るものです。

情報理論的な最小値に近い：
非周期的なリズムを扱う場合、理論的に「これ以上小さくはできない」という限界があります。この論文は、フィボナッチ語のシフト操作が、その**「理論的な最小値に近い」**レベルまで効率化できることを示しました。
応用：
データ圧縮、暗号化、あるいは自然界のパターンを解析するアルゴリズムなど、効率的な計算手法が必要な分野で役立つ可能性があります。

💡 まとめ

この論文は、**「フィボナッチという不思議なリズムは、ずらして読んでも、実はとても小さな機械で処理できる」**という驚くべき発見を報告しています。

一般的な常識： ずらす量が多い＝機械が巨大。
フィボナッチの真実： ずらす量が多い＝機械は**「数字の桁数」**だけ増えればよく、驚くほどコンパクト。

まるで、**「1000 階建てのビルを登るのに、エレベーター（巨大な機械）ではなく、階段（小さな機械）ですぐに上がれる」**ような、数学的な「抜け道」を見つけたようなものです。この「黄金比」の魔法が、計算の世界でこんなにも効率的な解決策を生んでいるとは、本当に面白いですね。

1. 問題設定

対象: フィボナッチ無限語 $f = (f_i)_{i \ge 0} = 01001010\cdots$ 。これは、最も有名な非周期的無限語の一つであり、Zeckendorf 表現（フィボナッチ数を用いた数値表現）の最後の桁として定義されるなど、多様な定義を持つ。
課題: 与えられた定数 $c \ge 0$ に対して、シフトされた系列 $(f_{i+c})_{i \ge 0}$ を生成する決定性有限オートマトン（DFAO）の最小状態数を評価すること。
入力形式: 2 つの異なる入力形式を考慮する。
1. lsd-first (Least Significant Digit first): 最下位桁から入力する形式。
2. msd-first (Most Significant Digit first): 最上位桁から入力する形式。
背景: 一般的な $k$ 進数表現における自動系列（Automatic Sequence）のシフトでは、lsd-first の場合 $O(m \log c)$ 状態（ $m$ は元の状態数）で構築可能だが、Zeckendorf 表現では加算が 1 パスで実行できないため、単純な変換器（transducer）の適用が困難である。また、msd-first の場合、Thue-Morse 系列などでは $O(c)$ 以上の状態が必要になることが知られている。しかし、2 の冪の特性列などでは $O(\log c)$ となる例もあり、フィボナッチ語の場合にどのような複雑性が現れるかが不明であった。

2. 手法とアプローチ

本研究は、ディオファントス近似（Diophantine approximation）、状態複雑性の理論、および**論理（自動定理証明）**を融合させた手法を用いている。

Zeckendorf 表現と負の整数:
- 自然数の Zeckendorf 表現に加え、負の整数を表すための新しい表現法（Rockett-Szusz の一般化）を導入し、シフト操作 $i+c$ を分数部分 $\{i\phi\}$ の移動として捉える。
区間の分割（Partitioning）:
- lsd-first 場合: 整数 $n$ の Zeckendorf 表現の下位 $d$ 桁が、 $\{n\phi\}$ が存在する区間 $I_d(m)$ を決定するという性質（Lemma 3）を利用する。シフト量 $c$ に対応する「臨界点」 $\{-(c+1)\phi\}$ と $\{-(c+2)\phi\}$ が、どの区間の端点となるかを追跡する。
- msd-first 場合: 入力桁を右にシフト（最上位桁を捨てる）操作と、ビットを付加する操作が、区間の分割とどのように対応するかを解析する。 $P(r)$ と呼ばれる、負の整数 $r$ の表現に基づいて定義された区間分割が、msd-first 表現と整合的（consistent）であることを示す（Lemma 5）。
自動定理証明ツール Walnut の活用:
- 複雑な区間の包含関係や、フィボナッチ語の性質に関する証明の一部を、自動定理証明ツール「Walnut」を用いて厳密に検証している。これにより、手計算では困難なケースの網羅的確認が可能になった。

3. 主要な結果

論文の中心的な結論は以下の通りである。

定理 1 (lsd-first 場合):
任意の $c \ge 0$ に対して、シフトされた系列 $(f_{i+c})_{i \ge 0}$ を生成する lsd-first DFAO は、 $O(\log c)$ 状態で構成可能である。
- 具体的には、最小状態数は $2(|(c)_F| + 1) + 1 - g(c)$ で与えられ、ここで $|(c)_F|$ は $c$ の Zeckendorf 表現の桁数、 $g(c)$ は $f(c-1)=f(c-2)=0$ かどうかで決まる補正項である。
- この結果は、 $O(\log c)$ という上限が最適であることを示している。
定理 3 (msd-first 場合):
任意の $c \ge 0$ に対して、シフトされた系列 $(f_{i+c})_{i \ge 0}$ を生成する msd-first DFAO も、 $O(\log c)$ 状態で構成可能である。
- 従来の直感的な予想（msd-first では状態数が $O(c)$ 程度に増大する）とは異なり、フィボナッチ語の特殊な構造により、lsd-first と同様に対数的な増加に抑えられることが証明された。

4. 技術的貢献と意義

対数複雑性の達成:
非周期的な自動系列のシフトにおいて、状態複雑性が $O(\log c)$ となることは、情報理論的な下限に近い極めて稀なケースである。本研究は、フィボナッチ語という代表的な Sturmian 語において、lsd-first と msd-first の両方でこの低い複雑性が達成されることを初めて示した。
手法の革新:
- 単なるオートマトンの構成だけでなく、ディオファントス近似（黄金比 $\phi$ とフィボナッチ数の関係）を用いて、入力桁と実数区間の対応を厳密に結びつけた点。
- 負の整数の Zeckendorf 表現をシフト操作の解析に活用した点。
- 自動定理証明ツールを証明の主要な構成要素として組み込んだ点。
一般化の可能性:
本研究で用いられた手法は、他の二次無理数に基づく系列や、トリボナッチ語（Tribonacci word）などのより複雑な自動系列への拡張が可能であることを示唆している。

5. 結論

この論文は、フィボナッチ語のシフト操作が、入力形式（lsd-first または msd-first）に関わらず、非常に効率的なオートマトン（状態数 $O(\log c)$ ）で表現可能であることを証明した。これは、自動系列のシフトに関する状態複雑性の理論において重要な進展であり、ディオファントス近似と形式言語理論の強力な結合を示す好例となっている。