On a sequence of Kimberling and its relationship to the Tribonacci word

Each language version is independently generated for its own context, not a direct translation.

この論文は、数学の「言葉の世界（組合せ論）」において、ある不思議な数字の並び（数列）の正体を暴き、その性質を解明した研究報告です。専門用語を避け、日常の風景や物語に例えて解説します。

📜 物語の舞台：クリンリングの「魔法のレシピ」

まず、2017 年にクリンリングという数学者が、ある「魔法のレシピ」を見つけました。
それは、0 と 1 という 2 つの数字だけを使った、無限に続く文字列（B）を作るルールです。

始め方： 「00」という 2 文字からスタート。
変身ルール：
- 「00」は「0101」に変わる。
- 「0」は「0」のまま。
- 「1」は「10」に変わる。

このルールを繰り返していくと、文字列はどんどん長くなり、ある特定の形（0100101100...）に落ち着いていきます。クリンリングは「この文字列の長さは、実はある有名な数列（A288465）とぴったり一致するはずだ」と予想しました。しかし、このルールは単純な「置き換え」ではなく、少し複雑な「ブロック単位の変身」なので、証明するのが非常に難しかったのです。

🔍 探偵たちの登場： Walnut と自動車の力

この難問を解決したのが、著者たち（ドヴォラコバ、ペラントバ、シャリット）です。彼らが使ったのは、**「Walnut（ウォルナット）」**という、数学の定理を証明するプログラム（定理証明機）です。

これを**「超高性能な探偵」や「自動運転の車」**に例えてみましょう。
人間が手計算で「この文字列の 100 万文字目は何か？」と調べるのは不可能ですが、Walnut という探偵は、文字列の規則性を「自動車のナビゲーション（有限オートマトン）」のように捉え直しました。

トリボナッチの地図： この文字列 B は、実は「トリボナッチ語（TR）」という、もっと有名な「黄金の文字列」を、ある変換フィルター（鏡やフィルター）に通したものと全く同じであることがわかりました。
Walnut の活躍： 著者たちは、この「フィルターを通した後の地図」を Walnuts という探偵に読み込ませました。すると、探偵は瞬く間に「クリンリングの予想は正しい！」と証明し、さらに「この文字列は 3 回までバランスが良いが、2 回ではダメだ」といった、人間には見えない微細な性質まで見つけ出しました。

🌟 発見された 3 つの驚き

この研究で明らかになった 3 つの重要な発見を、日常の言葉で説明します。

1. 長さの謎が解けた（クリンリングの予想）

クリンリングは「この文字列の長さの並びは、特定の数列と一致する」と予想していました。Walnut という探偵が、この文字列を構成する「ブロック（1, 10, 100）」の数を数え上げ、数学的な方程式を解くことで、**「予想は完全に正しかった！」**と証明しました。

2. 隠れた「双子」の関係（トリボナッチ語との関係）

この文字列 B は、実は「トリボナッチ語（TR）」という有名な文字列の**「双子」**でした。

トリボナッチ語： 0, 1, 2 の 3 つの数字を使って作られる、非常に規則的な文字列。
B（クリンリングの文字列）： このトリボナッチ語を、ある「変換フィルター（0→10, 1→0, 2→1）」に通して作られたもの。

つまり、B という複雑な文字列は、実は TR という有名な文字列の「変身姿」だったのです。この関係がわかったことで、B の性質を調べるのが格段に簡単になりました。

3. 繰り返しの限界（臨界指数）

「この文字列の中に、同じパターンが何回も繰り返されるか？」という問いがあります。
例えば「010101」は「01」が 3 回繰り返されています。
この文字列 B には、**「2.19 回」**という、ある決まった限界（臨界指数）がありました。

意味： この文字列の中に、「010101」のように、同じパターンが 3 回以上連続して現れることは絶対にない。でも、2.19 回分くらいなら、ギリギリ現れる可能性がある。
アナロジー： これは「あるリズムの音楽」を想像してください。そのリズムは、3 回連続で同じメロディを鳴らすと「飽きてしまう（破綻する）」けど、2 回半くらいなら「心地よい繰り返し」として成立する、という限界値が見つかったのです。

🎓 なぜこの研究は重要なのか？

一見すると「0 と 1 の並び」を調べるだけですが、この論文の真価は**「方法論」**にあります。

複雑なパズルの解き方： 人間には難しすぎる複雑なルールでも、コンピュータ（Walnut）と数学の組み合わせを使えば、証明できることを示しました。
応用可能性： この「Walnut を使った探偵のやり方」は、この文字列だけでなく、他のどんな複雑な数列やパターンに対しても使える「万能の鍵」です。

🏁 まとめ

この論文は、**「ある数学者が作った不思議な数字の並び（B）」というパズルを、「有名な文字列（トリボナッチ）の変身」として見抜き、「超高性能な探偵（Walnut）」**を使って、その長さの法則や、繰り返しの限界を完璧に解明した物語です。

数学の世界では、一見無関係に見える 2 つのものが実は「双子」だったとわかり、さらにコンピュータの力を借りて、その性質を厳密に証明できたという、知的な冒険の記録なのです。

Each language version is independently generated for its own context, not a direct translation.

1. 問題設定 (Problem)

対象となる列: クラーク・キンバリングが定義した無限列 $B$ $B$ （OEIS A288462）。
- 初期値： $B_0 = 00$
- 生成規則（インフレーション規則）：$00 \mapsto 0101 $,$ 1 \mapsto 10 $,$ 0 \mapsto 0$
- この規則は単純な準同型写像（morphism）ではなく、最大ブロック（$00 $,$ 0 $,$ 1$）に分解して適用する形式であるため、解析が困難とされていた。
未解決の課題:
- 列 $B$ の長さ $|B_i|$ が満たす漸化式に関するキンバリングの予想。
- 列 $B$ と無限トリボナッチ語（Tribonacci word, TR）との構造的な関係。
- 列 $B$ の「因子複雑度（factor complexity）」と「臨界指数（critical exponent）」の決定。
- 関連する列（1 の出現位置、0 の出現位置）に関する定数値の予想。

2. 手法 (Methodology)

著者らは、以下の 3 つの手法を組み合わせて問題を解決しました。

Walnut 定理証明支援系の活用:
- 列 $B$ を計算する決定性有限オートマトン出力付き（DFAO）を構築しました。
- 入力には整数 $n$ を「トリボナッチ表現（Tribonacci representation）」で与え、出力として $B[n]$ を返す自動機を作成しました。
- この自動機を用いて、列の性質（バランス性、因子の出現など）を第一階述語論理で記述し、Walnut によって「真（TRUE）」または「偽（FALSE）」を厳密に判定させました。
トリボナッチ語との関係性の導出:
- 列 $B$ がトリボナッチ語 $TR$ のある準同型写像による像であることを数学的に証明しました。具体的には、 $B$ が $TR$ の「戻り語（return words）」の集合を用いて記述できることを示し、 $B = 0f(TR)$ （ $f$ は特定の準同型写像）という関係式を導きました。
組合せ論的・代数的解析:
- 双特別因子（bispecial factors）の構造を分析し、トリボナッチ数を用いて因子複雑度や臨界指数を理論的に計算しました。
- 平衡性（balance）や臨界指数の上限・下限を評価するために、トリボナッチ数の漸近的な性質を利用しました。

3. 主要な貢献と結果 (Key Contributions and Results)

A. キンバリングの予想の証明

長さの漸化式: 列 $B_i$ の長さ $|B_i|$ が、 $c_0=2, c_1=4, c_2=6, c_3=10$ かつ $i \ge 4$ で $c_i = 2c_{i-1} - c_{i-4}$ を満たすことを証明しました。
関連列の平衡性: 列 $B$ が「3-バランス」であるが「2-バランス」ではないことを Walnut によって証明しました（反例は長さ 47 で発生）。

B. トリボナッチ語との関係

構造的同値性: 列 $B$ が、トリボナッチ語 $TR$ に準同型写像 $f$ （$0 \mapsto 10, 1 \mapsto 0, 2 \mapsto 1 $）を適用し、先頭に 0 を付加したものであること（$ B = 0f(TR)$）を証明しました。
これにより、 $B$ の性質が $TR$ の性質から直接導かれることが示されました。

C. 関連する列（1 と 0 の出現位置）

列 $B$ $B$ における $n$ $n$ 番目の 1 の位置 $I_1(n)$ $I_{1} (n)$ と 0 の位置 $I_0(n)$ $I_{0} (n)$ について、キンバリングの定数予想をより精密な形で証明しました。
- $I_0(n)$ はトリボナッチ定数 $\psi$ （ $X^3-X^2-X-1=0$ の実根、約 1.8393）を用いて $\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$ と評価されます。
- $I_1(n)$ は $\gamma = (\psi^2+1)/2$ （約 2.1915）を用いて同様に評価されます。

D. 因子複雑度と臨界指数

因子複雑度: 列 $B$ の因子複雑度（長さ $n$ の異なる部分列の数）は、すべての $n \ge 1$ に対して $2n $であることを証明しました。これは$ B$ が「ロート語（Rote word）」のクラスに属することを意味します。
臨界指数: 列 $B$ の臨界指数（無限列に含まれる部分列の指数の上限）は、
$2 + \frac{1}{\psi - 1} \approx 3.19148788$
であることを証明しました。これはトリボナッチ語の臨界指数と一致します。

4. 意義 (Significance)

方法論の確立: 複雑なインフレーション規則で定義された列を、自動機理論（Walnut）と組合せ論的解析を融合させることで厳密に解析できることを示しました。このアプローチは、同様の複雑な列を扱う際の「入門書（primer）」として機能します。
未解決問題の解決: 長年未解決だったキンバリングの複数の予想を、コンピュータ支援証明と理論的証明の両面から完全に解決しました。
構造の解明: 一見複雑な列 $B$ が、有名なトリボナッチ語の単純な変形に過ぎないことを明らかにし、両者の深い数学的関連性を確立しました。
計算機科学への寄与: 定理証明支援系 Walnut を用いた組合せ論的 word 理論の研究における、具体的な応用例として重要な論文となっています。

総じて、この論文は、特定の数列の定義から出発し、高度な数学的ツールを駆使してその本質的な構造と不変量を明らかにした、理論計算機科学および組合せ論の分野における重要な成果です。