🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

この論文は、フィボナッチ語からなる長方形行列の平衡性を有限オートマトンで判定可能であることを示し、その結果を二次無理数に対応するすべてのシュトルミアン特徴語、さらにトリボナッチ語やチュー・モース語へと一般化している。

原著者： Jeffrey Shallit, Ingrid Vukusic

公開日 2026-03-31

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

原著者： Jeffrey Shallit, Ingrid Vukusic

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

数学の「パズル」と「自動運転」：フィボナッチ数列の隠れた規則

この論文は、「フィボナッチ数列（0, 1, 0, 0, 1, 0, 1, 0...）」という無限に続く数字の羅列から、長方形のブロックを切り取ったとき、その中に含まれる「1」の数が均等になるかどうかという、一見すると難解な問題を、まるでパズルを解くように明快に説明したものです。

著者たちは、この問題を解決するために「有限オートマトン」という**「ルールに従って動く小さなロボット（自動運転システム）」**を使いました。

以下に、専門用語を排し、日常の例え話を使ってこの研究の内容を解説します。

1. 物語の舞台：「数字の壁紙」

まず、フィボナッチ数列を想像してください。これは 0 と 1 が無限に並んだ**「数字の壁紙」**のようなものです。
01001010...

この壁紙から、例えば「縦 4 行、横 18 列」の長方形の窓枠（マス目）を切り取ったとします。

問題： この窓枠の中に「1」がいくつ入っているか？
さらに深い問題： 窓枠を壁紙の上で少しずらしたとき（位置を変えたとき）、入っている「1」の数は**「ほぼ同じ」**になりますか？

これを**「バランスがとれている」**と呼びます。もし、場所によって「1」の数が極端に多かったり少なかったりすれば、それは「バランスが悪い（偏っている）」ことになります。

2. 従来の常識と、新しい発見

以前、ある研究者たちは**「窓枠のどちらかの辺の長さが『フィボナッチ数』（1, 2, 3, 5, 8, 13...）であれば、バランスは必ず取れる」**というルールを見つけました。
（例：3×5 の窓枠なら OK、5×8 なら OK）

しかし、「4×3」のような、フィボナッチ数ではない組み合わせでも、実はバランスが取れている場合があることが分かっていました。
「じゃあ、いったいどの組み合わせがバランス良くて、どれが悪いのか？」という**「完全なリスト」**が長らく不明でした。

3. 解決策：「自動運転ロボット」の登場

著者たちは、一つ一つ手計算でチェックするのではなく、**「入力された数字を見て、バランスが良いかどうかを即座に判断するロボット（有限オートマトン）」**を作りました。

ロボットの仕組み：
このロボットは、フィボナッチ数列特有の「ゼッケンドルフ表記（数字をフィボナッチ数の和で表す方法）」という言語を理解します。
あなたが「4 と 18」と入力すると、ロボットは内部で複雑な計算をせず、あらかじめ組み込まれた「ルール（状態遷移図）」に従って、**「OK（バランス良し）」か「NG（バランス悪し）」**を瞬時に答えます。
結果：
このロボット（図 1 のような図）を使うことで、「どの長方形の組み合わせがバランス良くて、どれが悪いのか」を 100% 正確に判定できることが証明されました。
以前知られていた「フィボナッチ数なら OK」というルールも、このロボットの答えの一部として自然に導き出されました。

4. 応用：他の「数字の壁紙」でも通用する

この「ロボット」の考え方は、フィボナッチ数列だけでなく、他の有名な数列にも適用できます。

トリボナッチ数列（0, 1, 0, 2, 0, 1...）：
ここでは「0, 1, 2」の 3 種類の数字が使われます。
結果：「縦 1 行」ならどんな長さでも OK。「縦 2 行」なら特定の長さで OK。「縦 3 行以上」だと、どんな長さでもバランスが取れない（偏りが必ず出る）ことが分かりました。
トゥー・モース数列（0, 1, 1, 0, 1, 0, 0, 1...）：
これは「0 と 1」が交互に現れる独特なリズムです。
ここでは、長方形のバランスの「最大誤差」が**「4 以下」**であることが証明されました。さらに、縦と横の長さがどちらも「奇数」のときだけ、バランスの誤差が「3」になるという面白いルールが見つかりました。

5. なぜこれが重要なのか？

この研究は、単なる数字遊びではありません。

予測可能性： 複雑に見えるランダムな数列の中に、実は**「完全な規則性」**が潜んでいることを示しました。
自動化： 「手計算では不可能な巨大なパターン」を、コンピュータの「小さなロボット（オートマトン）」が瞬時に解き明かせることを実証しました。
数学の美しさ： 一見バラバラに見える「バランスの良い長方形」のリストが、実は一つのシンプルな機械で説明できるという、数学的な統一感の美しさを示しています。

まとめ

この論文は、**「無限に続く数字の壁紙から、どんなサイズの窓枠を切り取っても、中身が均等になるかどうかを、小さな自動ロボットが 100% 正確に判定できる」**という驚くべき発見を報告しています。

まるで、「どのパズルのピースを組み合わせれば、きれいな模様ができるか」を、ルールブック（ロボット）が瞬時に教えてくれるようなものです。これにより、数学の奥深い部分にある「秩序」が、より身近で理解しやすい形で見えてきました。

論文「Balanced Fibonacci word rectangles, and beyond」の技術的サマリー

1. 問題の定義

本論文は、無限数列（特にフィボナッチ語、ストゥルミアン語、トリボナッチ語、チュー・モース語）から構成される $m \times n$ 行列（「ワード長方形」）の**平衡性（balance property）**に関する問題を扱っています。

行列の定義: 無限数列 $(a_i)_{i \ge 0}$ に対し、行列 $A(i, m, n)$ を $a_{k+\ell}$ を要素とする $m \times n$ の部分行列として定義します（ハネル行列の一種）。
和の定義: 行列内の全要素の和を $T(i, m, n)$ とします。
平衡性の定義: 異なる開始位置 $i$ に対するすべての $m \times n$ 長方形について、その要素和 $T(i, m, n)$ が「高々 2 つの異なる値」しか取り得ない場合、そのペア $(m, n)$ は平衡的であると定義されます。
目的: 与えられた無限数列（例：フィボナッチ語）に対して、どの自然数のペア $(m, n)$ が平衡的になるかを完全に特徴付けること。

2. 手法とアプローチ

著者らは、数理論理学と有限オートマトン、および自動定理証明ツールWalnutを用いた計算論的アプローチを採用しています。

2.1 主要な理論的枠組み

ストゥルミアン語の性質の活用:
- ストゥルミアン語（非有理数 $\alpha$ に対応する語）は、長さ $n$ の部分語の出現頻度の差が 1 以下である「1-平衡性」を持つことが知られています。
- この性質を用いると、行列の和の差分 $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ が $\{-1, 0, 1\}$ の値しか取らないことが示されます。
- 平衡性の判定基準（補題 1）: $(m, n)$ が平衡的であるための必要十分条件は、差分列 $\Delta(i, m, n)$ に「 $1, 0, \dots, 0, 1$ 」または「 $-1, 0, \dots, 0, -1$ 」というパターンが存在しないことです。
有限オートマトンによる判定:
- 二次無理数 $\alpha$ に対応するストゥルミアン語の場合、 $\lfloor n\alpha \rfloor$ の計算はOstrowski 数系を用いた有限オートマトンで記述可能です。
- 上記の平衡性判定基準を第一階述語論理式として定式化し、それを Walnut ツールを用いて有限オートマトンに変換します。これにより、入力 $(m, n)$ を受け取り、平衡かどうかを判定するオートマトンを構築できます。
線形表現（Linear Representations）:
- 異なる値の個数に関する密度や漸近挙動（セクション 5）を解析する際、Walnut の線形表現機能を用いて、特定の関数が 0 になるかどうかを判定するアルゴリズムを適用しています。
特殊な数系への対応:
- フィボナッチ語: ゼッケンドルフ数系（Fibonacci 数系）を使用。
- トリボナッチ語: トリボナッチ数系を使用。
- チュー・モース語: 負の基数（base $-2$）表現を用いて、和の計算における符号の問題を回避し、平衡性を計算するオートマトンを構築しています。

3. 主要な貢献と結果

3.1 フィボナッチ語に関する結果

完全な特徴付け（定理 2, 補題 3）: 二次無理数 $\gamma = (3-\sqrt{5})/2$ に対応するフィボナッチ語について、 $m \times n$ 長方形が平衡的になる $(m, n)$ のペアを判定する 15 状態の有限オートマトンを構築しました。
既知の結果の一般化: Anselmo らが示した「 $\max(m, n)$ がフィボナッチ数であれば平衡的である」という定理は、構築したオートマトンの特殊なケースとして導出されました。
新しい性質の発見:
- 特定のフィボナッチ数区間内での平衡性の対称性（命題 5）。
- 平衡的な $n$ の密度の下限（命題 6）。
- $m=n=F_{3k/2}$ の場合、 $T(i, m, n)$ が取りうる異なる値の数が $\Theta(k)$ であることを示し、平衡でない場合の値の多様性を証明しました（定理 8）。

3.2 トリボナッチ語に関する結果

2-平衡性の判定（定理 10）: トリボナッチ語（3 文字 $\{0, 1, 2\}$ ${0, 1, 2}$ ）からなる長方形が互いに 2-平衡的（要素数の差が 2 以下）になる条件を特徴付けました。
- $m=1$ : 常に平衡的。
- $m=2$ : 77 状態のオートマトンで判定可能（特定の $n$ のみ平衡的）。
- $m \ge 3$ : 平衡的な $n$ は存在しない。

3.3 チュー・モース語に関する結果

平衡性の完全な記述（定理 11, 12）: チュー・モース語（ $0 \to 01, 1 \to 10$ $0 \to 01, 1 \to 10$ ）について、 $m \times n$ $m \times n$ 長方形の平衡性（要素和のばらつき）を完全に記述する 92 状態のオートマトンを構築しました。
- 任意の $m, n$ に対し、平衡性は 1, 2, 3, 4 のいずれかであることが示されました。
- $m, n \ge 3$ かつ両方が奇数の場合、平衡性は厳密に 3 になることを証明しました（定理 14）。
大規模計算: この結果を得るために、最大で 3200 万状態を超える中間オートマトンの生成を含む大規模な計算（12834 秒、100GB RAM）を行いました。

4. 意義と結論

自動化された証明: 従来の手計算や数値実験では困難だった、無限語の多次元平衡性に関する複雑な性質を、有限オートマトンと自動定理証明ツールを用いて厳密に証明・特徴付けすることに成功しました。
一般化可能性: この手法は、二次無理数に対応するすべてのストゥルミアン語に適用可能であり、特定の語（フィボナッチ、トリボナッチ、チュー・モース）に限定されない一般的な枠組みを提供しています。
計算論的数論への貢献: Ostrowski 数系や負の基数系を用いた自動機理論の応用範囲を広げ、組合せ論的数論における「平衡性」という古典的な問題に新しい視点をもたらしました。

本論文は、Walnut ツールの強力な計算能力と、ストゥルミアン語の構造的特徴を組み合わせることで、長方形の平衡性という未解決の問いに対して、機械的に検証可能な完全な解答を提供した点に大きな意義があります。