Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

この論文は、有限文字列における最小の因子複雑性を持つ無限語（特にスチュルミ語など）を中核テーマとし、力学・代数・算術との相互作用を解説するとともに、1999 年のティデマンの定理に対する 2022 年の新しい代数的証明とその帰結を提示する、組合せ論的単語論への入門書である。

要約

この論文は、**「無限に続く文字の列（単語）」**が、どれほど「単純」か「複雑」かを測る数学的な研究です。

タイトルにある「Factor Complexity（因数の複雑さ）」とは、簡単に言うと**「その文字列の中に、長さ n の『小さな断片』が何種類現れるか」**を数えることです。

例えば、121212... という文字列なら、長さ 2 の断片は「12」と「21」の 2 種類しかありません。一方、123456... のようにランダムな文字列なら、長さ 2 の断片はもっと多く、12, 13, 14... と次々と増えます。

この論文は、**「どんなに複雑に見えても、実は非常に単純なルールでできている『特別な文字列』」**について、2 文字の場合から、3 文字、4 文字と増やした場合までを解明しようとしています。

以下に、難しい数学用語を使わず、日常の例え話で解説します。

---

1. 物語の舞台：「文字列の森」と「迷路」

まず、無限に続く文字列を**「無限に続く道」**だと想像してください。
その道には、1 や 2、3 といった「標識（文字）」が並んでいます。

• 複雑さ（Complexity）：
  この道を歩いているとき、「長さ 3 の区間」を眺めたとき、何通りの「景色（標識の並び）」が見えるでしょうか？
  • 景色が 1 種類しかないと、道は単純な「ループ」です（例：121212...）。
  • 景色が無限に増えると、道は完全にランダムで予測不能です。
  • この論文が探しているのは、「景色が『最小限』しか増えないが、決してループしない（単純な繰り返しではない）道」です。

2. 第一章：2 文字の世界（ストルミアン語）

まず、標識が 1 と 2 だけの世界を考えます。

• モーゼとヘドランドの定理（1938 年）：
  「もし道が『ループ（繰り返し）』なら、景色の種類は有限で止まる。逆に、景色の種類が『n 以下』に収まるなら、その道は必ずループしている」
  つまり、「ループしない道」なら、景色の種類は必ず「n+1 種類」以上必要だと言っています。

• ストルミアン語（Sturmian words）：
  「ループしない道」の中で、最も景色が少なく（n+1 種類）、最も単純な道があります。これを「ストルミアン語」と呼びます。

  • 例え： これは、**「黄金比（フィボナッチ数列）」**という特別な比率で 1 と 2 を並べた道です。
  • 特徴： この道は、円周上の回転や、ビリヤードの玉の動きと深く結びついています。数学的には「有理数（分数）で表せない数（無理数）」と関係しています。

3. 第二章：3 文字以上の世界への挑戦

次に、標識が 1, 2, 3 と増えた世界（3 文字以上）を考えます。

• 問題点：
  2 文字の世界では「ループしない＝面白い」と言えましたが、3 文字以上になると、ただ「ループしない」だけでは不十分です。
  例え話で言うと、1, 2, 3 がランダムに並んでいるように見えても、実は 1 と 2 だけが活躍し、3 はたまにしか出てこないような「偏った道」は、本質的には 2 文字の道と変わらない「つまらない道」です。

• 新しい条件：「有理独立（Rational Independence）」
  面白い道を見つけるための新しい条件は、**「各文字（1, 2, 3...）が現れる割合（頻度）が、お互いに『分数の関係』で結びついていないこと」**です。

  • 例え： 1 が 1/2 回、2 が 1/2 回なら、これは「1:1」の単純な関係です。でも、1 が「黄金比の逆数」の割合で現れ、2 が別の無理数の割合で現れるなら、それらは「独立」しています。
  • この「独立した割合」を持つ道こそが、真に「面白い道」です。

• ティデマンの定理（1999 年）：
  この「独立した割合」を持つ道において、「最も景色が少ない（最も単純な）道」の複雑さは、(d-1) × n + 1 であると証明されました。

  • 2 文字（d=2）なら n+1。
  • 3 文字（d=3）なら 2n+1。
  • 4 文字（d=4）なら 3n+1。
    文字が増えるほど、最低限必要な「景色の種類」も増えるという、とても美しい法則です。

4. 第三章：新しい証明と「木」の発見

最後の章では、著者たちがティデマンの定理を、**「線形代数（行列）」**という新しい道具を使って、よりシンプルに証明し直しました。

• フロー行列（Flow Matrix）：
  道の上を流れる「文字の流れ」を、電気回路の電流のように考えました。
  「ある地点に流入する電流」と「流出する電流」のバランス（キルヒホッフの法則）を行列で表し、その「核（Kernel）」を調べることで、複雑さの限界を導き出しました。

• 重要な発見：「木（Dendric）」
  この証明から、**「最も単純な道は、必ず『木（Tree）』のような構造を持っている」**という新しい事実がわかりました。

  • 例え： 道が分岐する際、ループ（輪っか）を作らず、常に一本の木のように枝分かれしていく構造です。
  • これまで知られていた「ストルミアン語」やその仲間たち（アルヌックス・ラウジ語など）は、すべてこの「木」の構造を持っています。つまり、**「最も単純な道＝木のような道」**であることが、3 文字以上の世界でも成り立つことが示されました。

---

まとめ：この論文が伝えたかったこと

1. 無限の道には、驚くほど単純なルールがある。
   ランダムに見えても、実は「黄金比」や「無理数」のような数学的な美しさに基づいて作られている。
2. 文字が増えると、単純さの基準も変わる。
   2 文字のときは「ループしない」だけでよかったが、3 文字以上では「文字の割合がバラバラ（独立）であること」が重要になる。
3. 新しい証明で、その正体がわかった。
   複雑な道は、実は「木」のように枝分かれする構造をしており、それが「最も単純な道」の正体である。

この研究は、**「一見複雑に見える自然現象や情報処理の背後には、驚くほどシンプルで美しい数学的構造が隠れている」**というメッセージを、文字列という小さな世界を通じて伝えています。

技術概要

論文「Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words」の技術的サマリー

1. 概要と背景

本論文は、組合せ論的単語論（Combinatorics on Words）における「無限単語の因子複雑性（factor complexity）」、特にその最小値に関する研究をまとめた講義ノートです。著者 Mélodie Andrieu は、1938 年の Morse-Hedlund の定理から 1999 年の Tijdeman の定理、そして 2022 年の著者自身と J. Cassaigne による新たな代数的証明に至るまでの発展を体系的に解説しています。

中心的なテーマは、**「非自明な（non-trivial）無限単語の最小複雑性とは何か」**という問いです。ここで「非自明性」の定義をどう定めるかが、アルファベットサイズ（$d$）によって変化することが論点となります。

2. 問題設定と主要な問い

• 複雑性の定義: 無限単語 $w$ の複雑性 $p_w(n)$ は、長さ $n$ の異なる因子（部分文字列）の数を表す関数です。
• 基本問題:
  1. 有限アルファベット（$d$ 文字）上の「興味深い」無限単語の最小複雑性は何か？
  2. その最小複雑性を達成する単語はどのような構造を持つのか？
• 文脈:
  • $d=2$ の場合: Morse-Hedlund の定理により、最終的に周期的でない単語の最小複雑性は $p_w(n) = n+1$ であり、これらは**シュトゥルミアン語（Sturmian words）**として完全に特徴付けられています。
  • $d \ge 3$ の場合: 「最終的に周期的でない」という条件だけでは、最小複雑性 $n+d-1$ を達成する単語が「人工的」な構造（シュトゥルミアン語に単なる接頭辞を付加しただけのもの）に留まってしまうという問題が生じます。

3. 手法とアプローチ

本論文は 3 つの章で構成され、それぞれ異なるアプローチと結果を示しています。

第 1 章：シュトゥルミアン語と Morse-Hedlund の定理（$d=2$）

• 手法: 組合せ論的定義から出発し、連分数（continued fractions）、力学系（円回転、台球、トーラス上の線形フロー）、幾何学的表現（直線の離散化）との関係を解説。
• 核心: シュトゥルミアン語は、文字頻度の比が無理数であること（有理独立）と密接に関連しており、これが非周期性の代わりとなる重要な性質であることを示唆します。

第 2 章：$d$ 文字アルファベットへの一般化と Tijdeman の定理

• 問題提起: $d \ge 3$ において、「非周期的」ではなく「文字頻度が有理独立（rationally independent）」であるという条件を「非自明性」の定義として採用します。
• Tijdeman の定理 (1999): 文字頻度が有理独立な $d$ 文字無限単語の複雑性は、$p_w(n) \ge (d-1)n + 1$ である。この下限を達成する単語が存在する。
• 議論: 従来の「準シュトゥルミアン語（quasi-sturmian words）」は、この有理独立性の条件を満たさないことが示され、より本質的な一般化が必要であることが強調されます。

第 3 章：Tijdeman の定理の代数的証明と新たな結果（2022 年）

• 手法: 従来の組合せ論的証明（Tijdeman 原著）に代わり、線形代数を用いた新しい証明を提示します。
  • Rauzy グラフ: 長さ $n$ の因子を頂点、長さ $n+1$ の因子を辺とする有向グラフ。
  • フロー行列（Flow Matrix）: 電流回路のキルヒホッフの法則に着想を得た行列 $M$ を定義。行は長さ $n$ の因子、列は長さ $n+1$ の因子に対応し、要素は $1, -1, 0$ で構成されます。
  • 証明の骨子:
    1. 擬似頻度ベクトル（pseudo-frequency vector）がフロー行列 $M$ の核（kernel）に属することを示す（キルヒホッフの法則の離散版）。
    2. ランク・ヌリティー定理（rank-nullity theorem）を用いて、核の次元を評価する。
    3. 文字の最大無理次数（maximal degree of irrationality, $\Delta_w$）と複雑性の増加分を結びつけ、$p_w(n) \ge (\Delta_w - 1)(n-1) + d$ というより強い不等式を導出する。
• 新たな結果: この証明の副産物として、Tijdeman の最小複雑性を達成する単語はすべて**デンドリック語（dendric words）**であることが証明されました。デンドリック語とは、各因子の拡張グラフ（extension graph）が木（tree）であるような単語のクラスです。

4. 主要な結果と貢献

1. Tijdeman の定理の再発見と強化:

   • Tijdeman の元の定理（1999）は、最小の無理次数 $\delta_w$ に基づいていましたが、著者らは最大の無理次数 $\Delta_w$ に基づくより強い不等式 $p_w(n) \ge (\Delta_w - 1)(n-1) + d$ を導出しました。
   • 文字頻度の存在を仮定せず、部分列極限（pseudo-frequencies）の集合 $F_w$ に対して一般化されています。

2. 代数的証明の提示:

   • 組合せ論的な議論に依存せず、フロー行列と線形代数を用いた概念的に新しい証明を提供しました。これは、複雑性の増減と代数構造（有理独立な次元）を直接的に結びつけるものです。

3. デンドリック語との同値性の確立:

   • 有理独立な文字頻度を持ち、Tijdeman の最小複雑性 $(d-1)n+1$ を達成する無限単語の集合は、有理独立な文字頻度を持つデンドリック語の集合と一致することを証明しました。
   • これにより、$d \ge 3$ における「最小複雑性を持つ非自明な単語」の構造が、シュトゥルミアン語の一般化であるデンドリック語という明確なクラスに収束することが示されました。

4. シュトゥルミアン語の完全な特徴付けの再確認:

   • $d=2$ の場合、この枠組みはシュトゥルミアン語（$n+1$）と一致し、$d \ge 3$ への自然な拡張を提供します。

5. 意義と将来の展望

• 理論的意義: 組合せ論的単語論、力学系、数論（連分数、有理独立）を統合する強力な枠組みを提供しました。特に、複雑性の下限を「文字頻度の有理独立な次元」という代数的量と結びつけた点は画期的です。
• 実用的意義: 最小複雑性を持つ構造（デンドリック語）の同定は、データ圧縮、符号理論、および準結晶（quasicrystals）の数学的モデルにおいて重要です。
• 未解決問題: $d \ge 3$ において、Tijdeman の最小複雑性を持つ単語を、シュトゥルミアン語のように「代数的・幾何学的・動的」に完全に特徴付ける（例えば、特定のアルゴリズムや力学系として記述する）ことは、依然として開かれた問題です。本論文はこれを「デンドリック語」という組合せ論的クラスに限定しましたが、より具体的な動的記述への道筋を示唆しています。

総じて、本論文は低複雑性無限単語の研究において、古典的な結果を再評価し、新しい代数的手法によってその構造を深く解明した重要な貢献と言えます。