The complexity of finite smooth words over binary alphabets

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

🍎 物語の舞台：「言葉のレシピ」

まず、この研究の主人公は**「滑らかな言葉」という、無限に続く数字の羅列です。
一番有名な例は「1」と「2」だけで作られた「コラツキ語（Oldenburger-Kolakoski word）」**というものです。

これを料理に例えてみましょう。

レシピ（ルール）： 「数字が何回連続しているか」を数えて、その数字自体を次のレシピにする。
- 例：「2 が 2 回、1 が 2 回、2 が 1 回…」と並んでいるなら、次の行は「2, 2, 1」となります。
滑らかな言葉： この「レシピを適用する作業」を無限回繰り返しても、必ず数字の羅列として成立し続けるような、完璧に調和した言葉のことです。

この言葉は、自然界の結晶や音楽の旋律のように、一見ランダムに見えながら、実は深い規則性を持っています。しかし、その「規則性（複雑さ）」がどれくらい複雑なのか、何十年も謎でした。

🔍 研究者の挑戦：「巨大な城」の設計図

研究者たちは、この無限に続く「滑らかな言葉」そのものを直接調べるのは難しすぎると考えました。そこで、**「有限の断片（f-smooth words）」**という、城のレンガや壁の断片に注目しました。

f-smooth words（有限の滑らかな言葉）： 無限の言葉から切り取った「断片」で、これも同じルールで無限に分解できるもの。
研究の目的： 「この断片（レンガ）を並べると、無限の城（滑らかな言葉）が作れるのか？」そして、「その城の壁の広さ（複雑さ）は、どれくらい速く増えるのか？」を突き止めること。

🏆 この論文の 3 つの大きな発見

著者たちは、この「城の設計図」を完成させ、3 つの重要な成果を上げました。

1. 「断片」と「城」は同じだった（定理 1.31）

これまで、「無限の城から切り取った断片」と「無限に分解できる断片」が完全に一致するかどうかは謎でした。

発見： 「無限の城（滑らかな言葉）に含まれるすべての断片」は、実は「無限に分解できる断片（f-smooth words）」と100% 同じであることが証明されました。
意味： これにより、研究者は「無限の城」全体を調べる代わりに、もっと扱いやすい「断片」だけを調べるだけで、城の全貌（複雑さ）がわかることが確定しました。

2. 「城の広さ」の正確な予測（定理 1.32）

「城の壁の広さ（複雑さ）」は、長さ $n$ に対して、 $n$ の何乗くらいで増えるのか？という問題です。

発見： 数字の組み合わせが「偶数＋偶数」や「偶数＋奇数」の場合、この広さは**「 $n$ の $\rho$ 乗」**という形で増えることが証明されました。
例え： 城が成長するスピードが、単に「直線的」ではなく、「指数関数的」だが、ある特定の「黄金比」のような定数で決まっていることがわかったのです。特に、数字が偶数の組み合わせ（例：2 と 4）の場合、この予測が完璧に当てはまることが証明されました。

3. 「奇数」の組み合わせへの新アプローチ（定理 1.33）

数字が「奇数＋奇数」（例：1 と 3）の場合、これまでの研究では「城の広さ」の上限（最大でもこれくらい）があまり正確にわかっていませんでした。

発見： 新しい数学的な手法を使って、これまでの予想よりも**「より狭い範囲（より正確な上限）」**を導き出しました。
意味： 以前は「城はこれ以上大きくならない」という線がぼんやりしていましたが、今回、その線をぐっと引き締めて、より正確な「城の大きさ」を推定できるようになりました。

🌟 なぜこれがすごいのか？

この研究は、「無限の複雑さ」を「有限の断片」で完全に理解できることを示しました。

従来： 「無限の言葉」を直接見るのは難しすぎて、複雑さを正確に測ることはできませんでした。
今回： 「断片（レンガ）」の性質を詳しく調べることで、無限の城の成長スピード（複雑さ）を、**「偶数の組み合わせなら完璧に、奇数の組み合わせならより正確に」**予測できるようになりました。

🎈 まとめ

この論文は、**「無限に続く不思議な数字の列（滑らかな言葉）」**という巨大な城の設計図を完成させた物語です。

「城の断片」と「無限の城」は同じものだと証明し、研究の土台を固めました。
**「城がどれくらい速く成長するか」**という謎を、偶数の組み合わせについては完全に解き明かしました。
奇数の組み合わせについても、これまでの「おおよその予想」から、**「より精密な予測」**へと進化させました。

これは、数学の「言葉の組み合わせ」という分野において、長年続いていた「複雑さの謎」に対する、非常に重要な一歩を踏み出した成果と言えます。まるで、複雑怪奇な迷路の出口を、地図を整理することで見つけたようなものです。

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

1. 問題設定と背景

Oldenburger-Kolakoski 言葉 ( $\kappa_{2,1}$ ) は、アルファベット $\{1, 2\}$ 上のランレングス符号化（run-length encoding）の不動点として定義される無限言葉です。この言葉の因子（部分列）の集合や複雑性（長さ $n$ の異なる因子の数 $p(n)$ ）は、組合せ論における長年の未解決問題の一つです。

滑らかな言葉 (Smooth words, $C^\infty$ ): 無限に微分可能（derivable）な無限言葉の集合。
有限滑らかな言葉 (f-smooth words, $C^\infty_f$ ): 滑らかな言葉の有限版。特定の「微分」操作を無限回繰り返して空語 $\varepsilon$ に到達できる有限言葉の集合。
既存の知見:
- 滑らかな言葉のすべての因子は f-smooth 言葉であることは知られていたが、その逆（すべての f-smooth 言葉が滑らかな言葉の因子であるか）は未証明だった。
- Sing は、アルファベット $\{a, b\}$ における f-smooth 言葉の複雑性が $p_{C^\infty_f}(n) = \Theta(n^\rho)$ で与えられると予想した。ここで $\rho = \frac{\log(a+b)}{\log(\frac{a+b}{2})}$ 。
- 以前の研究では、複雑性の上下界は多項式でしか示されておらず、正確な漸近挙動は不明だった。

本研究の目的:

任意の二文字アルファベットにおいて、滑らかな言葉の因子集合と f-smooth 言葉の集合が一致することを証明する。
Sing の予想（複雑性の漸近挙動）について、偶数アルファベット（ $a, b$ がともに偶数）および奇数アルファベット（ $a, b$ がともに奇数）に対して、より精密な上下界を導出する。

2. 手法と主要な概念

本研究では、以下の概念と手法を駆使して分析を行っています。

2.1 微分操作と f-smooth 言葉の定義

アルファベット $A=\{a, b\}$ ($1 \le a < b $) に対して、有限言葉$ u $を標準的な因数分解$ a^{p_1} \dots a^{p_n} $に分解し、その指数列に対して「cut」操作を適用して新しい言葉$ D_f(u) $を生成する微分演算$ D_f$ を定義します。

$u$ が f-smooth であるとは、 $D_f$ を無限回適用しても常に定義可能であり、最終的に $\varepsilon$ に到達することです。

2.2 r-smooth 言葉の導入 (Theorem 1.31 の証明)

滑らかな言葉の因子がすべて f-smooth 言葉であることを示すために、**r-smooth 言葉（右微分可能言葉）**という新しい概念を導入しました。

r-smooth 言葉は、滑らかな言葉の「接頭辞（prefix）」の役割を果たします。
証明のロジック:
1. 任意の f-smooth 言葉 $u$ に対して、ある r-smooth 言葉 $v$ が存在し、 $u$ が $v$ の因子となることを示す（数学的帰納法による高さの議論）。
2. 接頭辞がすべて r-smooth である無限言葉は滑らかであることを示す。
3. 結果として、任意の f-smooth 言葉は、ある滑らかな言葉の因子として現れることが証明されました。

2.3 二重特殊因子 (Bispecial Factors) と複雑性の計算

言葉の複雑性 $p(n)$ を計算するために、**二重特殊因子（bispecial factors）**の理論を用います。

二重特殊因子 $u$ は、左右に任意の文字を付加しても言葉の集合内に留まるような因子です。
その「多重度（multiplicity）」 $m(u)$ を用いて、複雑性の差分 $b(n) = p(n+1) - 2p(n) + p(n-1)$ を計算します（Theorem 1.5）。
ツリー構造の構築: 二重特殊 f-smooth 言葉は、有限原始（finite primitives） $P_{f,a}, P_{f,b}$ $P_{f, a}, P_{f, b}$ を用いて生成される無限二進木（Tree $T$ $T$ ）の頂点として記述できます。
- 強二重特殊（strong）と弱二重特殊（weak）の言葉が、異なる木（ $T, T^{(1)}, \dots, T^{(4)}$ ）に分類されます。
- 複雑性の評価は、これらの木における言葉の長さ分布（特に最小長さ $l_i$ と最大長さ $L_i$ ）の漸近挙動を解析することで行われます。

2.4 誤りの指摘

Huang の先行研究 [11] における誤りを指摘しました。Huang は異なる微分定義を用いており、これにより得られた複雑性の上限が実際よりも緩い（あるいは誤った）ものであったことを示し、正しい定義 $D_f$ を用いた分析の重要性を強調しました。

3. 主要な結果 (Theorems)

結果 1: 因子集合の一致 (Theorem 1.31)

定理: 任意の二文字アルファベットにおいて、滑らかな言葉の因子集合 $L(C^\infty)$ は f-smooth 言葉の集合 $C^\infty_f$ と等しくなります。
$L(C^\infty) = C^\infty_f$
意義: これにより、滑らかな言葉の複雑性 $p_{C^\infty}(n)$ と f-smooth 言葉の複雑性 $p_{C^\infty_f}(n)$ は等しくなり、f-smooth 言葉の解析が滑らかな言葉の解析そのものであることが確定しました。

結果 2: 複雑性の漸近挙動 (Theorem 1.32)

Sing の予想 $\Theta(n^\rho)$ について、以下の結果を得ました。

下限: 任意の二文字アルファベット $\{a, b\}$ において、 $p_{C^\infty_f}(n) = \Omega(n^\rho)$ が成り立ちます（ $\rho = \frac{\log(a+b)}{\log(\frac{a+b}{2})}$ ）。
偶数アルファベットの場合: $a, b$ がともに偶数の場合、 $p_{C^\infty_f}(n) = \Theta(n^\rho)$ が証明されました。つまり、Sing の予想は偶数アルファベットで完全に解決されました。

結果 3: 奇数アルファベットにおける新しい上限 (Theorem 1.33)

奇数アルファベットの場合: $a, b$ がともに奇数の場合、新しい上限 $p_{C^\infty_f}(n) = O(n^\zeta)$ を導出しました。
ここで $\zeta$ は、特定の行列のスペクトル半径や $a=1$ かどうかによって定義される定数です。
改善: この上限 $\zeta$ は、以前の既知の上限（Theorem 1.21 の $\beta$ ）よりも厳密に小さく、Sing の予想値 $\rho$ に近づいています（ただし、 $\zeta = \rho$ であるかどうかは未解決のままです）。

4. 技術的詳細と洞察

偶数 vs 奇数アルファベットの対称性:
- 偶数アルファベット: 木 $T$ 内の言葉の長さはすべて偶数であり、最小長さ $l_i$ と最大長さ $L_i$ が一致します（ $l_i = L_i$ ）。これにより、Weakley の予想（ $L_{i-1} \le l_i$ ）が自明に満たされ、正確な漸近挙動 $\Theta(n^\rho)$ が導かれます。
- 奇数アルファベット: 言葉の長さの分布がより複雑になります。 $l_i$ と $L_i$ の成長率が異なり（ $L_i$ の成長が $l_i$ よりも速い）、 $L_{i-1} \le l_i$ が成り立たない場合があります。このため、上限の評価には行列 $M$ の支配的固有値（spectral radius）を用いたより高度な解析が必要となり、結果として $\zeta$ という値が導かれました。
平均長さの解析:
複雑性の下限を導くために、各世代 $T_i$ における言葉の「平均長さ」を解析し、それが $(a+b)^i$ に比例して増加することを示しました。これが $\Omega(n^\rho)$ の根拠となります。

5. 意義と結論

この論文は、滑らかな言葉の複雑性に関する研究において以下の点で画期的な進歩をもたらしました。

基礎的な同値性の証明: 滑らかな言葉の因子と f-smooth 言葉が一致することを証明し、研究対象を明確に f-smooth 言葉に集約させました。
予想の部分的解決: Sing の複雑性予想を、偶数アルファベットに対して完全に証明しました。
奇数アルファベットへの進展: 奇数アルファベットにおいても、既存の上限を大幅に改善し、予想値に近づける新しい上限を提供しました。
誤りの修正: 関連する先行研究の誤りを指摘し、正しい微分定義に基づく解析の重要性を再確認させました。

今後の課題としては、奇数アルファベットにおける上限 $\zeta$ が予想値 $\rho$ に一致するか（すなわち $\zeta = \rho$ か）、あるいはより精密な解析が必要かという点、および滑らかな言葉の因子頻度（factor frequencies）に関する問題（Keane の予想の一般化）へのアプローチが挙げられます。

総じて、この研究は組合せ論における滑らかな言葉の構造理解を深め、その複雑性の漸近挙動に関する長年の謎に決定的な光を当てた重要な業績です。