ソフィックシフトにおける被覆半径の有理数性と計算可能性に関する技術的概要

本論文「Sofic Shifts における被覆半径の有理数性と計算可能性（RATIONALITY AND COMPUTABILITY OF THE COVERING RADIUS FOR SOFIC SHIFTS）」は、Tom Meyerovitch と Aidan Young によって執筆され、情報理論におけるノイズのあるチャネルでのデータ伝送に応用される「シフト空間の被覆半径（covering radius）」の性質を研究したものです。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定と背景

背景

• 被覆半径（Covering Radius）: 符号理論において、コード $C$ の被覆半径は、任意の語 $w$ に対して、$C$ 内のある語 $v$ が $w$ と $R$ 以下の座標でしか異ならないような最小の $R$ として定義されます。
• シフト空間への拡張: 有限長の符号から無限長列（シフト空間）への自然な拡張として、シフト空間 $X$ の被覆半径 $R(X)$ が定義されます。これは、制約付き符号化（constrained coding）やエラー訂正の実装において重要なパラメータです。
• ソフィックシフト（Sofic Shifts）: 有向ラベル付きグラフによって記述できるシフト空間のクラスであり、実世界のデータ伝送や記憶システムにおいて頻繁に現れます。

研究課題

先行研究 [3] では、特定のソフィックシフト（例：走査長制限シフトなど）の被覆半径が具体的に計算されており、その値が常に有理数であることが観察されていました。しかし、一般のソフィックシフトに対して以下の 2 つの根本的な問いが残されていました。

1. ソフィックシフトの被覆半径は常に有理数か？
2. ソフィックシフトの被覆半径を計算する一般的なアルゴリズムは存在するか？

本論文は、**原始的（primitive）**なソフィックシフト（対応するグラフが原始的である場合）という基本的なケースにおいて、これら 2 つの問いに肯定的な回答を与えます。

2. 手法と理論的枠組み

著者らは、以下の 3 つの主要な数学的枠組みを組み合わせて証明を行いました。

2.1. 熱帯畳み込み（Tropical Convolution）

整数値関数空間上の二項演算として「熱帯畳み込み」を導入しました。

• 関数 $f, g$ に対して、$(f * g)(u, w) = \min_{v} (f(u, v) + g(v, w))$ と定義されます。
• これは、通常の加法・乗法の代わりに、最小値・加法を用いる「熱帯半環（min-plus semiring）」における畳み込みに対応します。
• この演算を用いることで、グラフ上の歩道の連結（concatenation）と、対応するコスト関数の関係を代数的に扱えるようにしました。

2.2. 平均利得ゲーム（Mean Payoff Games）

A. Ehrenfeucht と J. Mycielski が導入した「交互型平均利得ゲーム」の変種として、非交互型（non-alternating）ゼロ和二人ゲームを定式化しました。

• プレイヤー: アリス（グラフ $H$ 上の歩道を選択）とボブ（グラフ $G$ 上の歩道を選択）。
• 利得: 選択された歩道 $p$（アリス）と $q$（ボブ）に対して、利得関数 $P(q_i, p_i)$ の和を最大化/最小化するゲーム。
• このゲームの値 $V(G, H, P)$ が、シフト空間の被覆半径と直接対応します。

2.3. 最適戦略の空間とソフィック性

• ゲームの「最適戦略」に対応する歩道の集合を定義し、それらが生成するシフト空間（$X^\dagger_H$ や $Y^\dagger_{(H,G)}$）がソフィックシフトであることを証明しました。
• ソフィックシフトの性質（有限のフォロワー集合を持つこと）を利用し、最適戦略の空間が周期的な点（周期歩道）を含むことを示しました。

3. 主要な結果と定理

本論文の核心的な成果は以下の 2 つの定理です。

定理 A（有理数性）

「原始ラベル付きグラフ $G$ によって定義されるシフト空間 $X_G$ の被覆半径 $R(X_G)$ は、有理数である。」

• 任意のソフィックシフト（原始的である場合）の被覆半径は、有理数値をとることが保証されます。

定理 B（計算可能性）

「原始ラベル付きグラフ $G$ を入力として受け取り、有限時間で $R(X_G)$ を計算するアルゴリズムが存在する。」

• 被覆半径の計算は決定論的アルゴリズムによって可能であり、無限極限を直接計算する必要はありません。

定理 C（一般化されたゲームの値）

上記の定理は、より一般的な結果である定理 Cから導かれます。

• 「2 つの原始グラフ $G, H$ と利得関数 $P$ に対して、ゲームの値 $V(G, H, P)$ は有理数であり、有限時間で計算可能である。」
• 被覆半径の計算問題は、この特定のゲーム設定（$H$ を完全グラフ、$P$ をハミング距離に基づく関数とする）に帰着させることで解決されます。

4. 証明の鍵となる論理

1. ゲーム値と被覆半径の対応: 被覆半径 $R(X_G)$ は、特定のグラフ $H$（全状態から全シンボルへの自己ループを持つグラフ）と利得関数 $P$（ラベルが一致すれば 0、不一致なら 1）を用いたゲームの値 $V(G, H, P)$ と等しくなることを示しました。
2. 非改善歩道（Non-improvable Walks）の構造: 最適戦略に対応する歩道の集合を定義し、その集合が有限の「局所的フォロワー集合」を持つことを示しました（定理 F）。これにより、最適戦略の空間がソフィックシフトであることが証明されました。
3. 周期性と極限値: ソフィックシフトには周期的な点（周期歩道）が存在するため、無限極限としてのゲーム値は、ある周期 $k$ と定数 $V^\dagger$ を用いて $V = V^\dagger / k$ と表せます。ここで $V^\dagger$ と $k$ は有限の計算で求められるため、結果として値は有理数となり、計算可能です。
4. 熱帯畳み込みの性質: 関数空間における最大値の性質（Lemma 3.1, 3.2）や、歩道の連結による値の変化（Lemma 4.1）を厳密に制御し、有限状態機械による計算の正当性を担保しました。

5. 意義と今後の課題

学術的・実用的意義

• 理論的保証: 情報伝送における重要なパラメータである被覆半径が、広範なクラス（原始ソフィックシフト）において常に有理数であり、計算可能であることを初めて一般論として証明しました。
• アルゴリズムの提供: 具体的な計算アルゴリズムの存在を示すことで、実際の符号設計やエラー訂正能力の評価に数学的基盤を提供します。
• ゲーム理論と力学系の融合: 平均利得ゲームの理論を、記号力学系（Symbolic Dynamics）の具体的な問題解決に応用した成功例です。

今後の課題（Open Problems）

論文の最後に、以下の未解決問題が提起されています。

• 非原始グラフへの拡張: 現在の結果は「原始的（primitive）」なグラフに限定されています。可約な（reducible）グラフの場合、有理数性や計算可能性が成り立つかどうかは未解決です（周期分解を用いることで解決できる可能性は示唆されています）。
• 実数値利得関数: 利得関数が有理数値ではなく実数値（例：$\mathbb{Q}(\sqrt{2})$ や $\mathbb{R}$）をとる場合、値が有理数（または代数的数）になるか、また計算可能かは未解決です。
• 最適戦略空間の性質: 実数値利得関数の場合でも、最適戦略の空間 $Y^\dagger_{(H,G)}$ がソフィックシフトであり、周期点を含むかどうかは不明です。

結論

本論文は、ソフィックシフトの被覆半径という情報理論的な量について、その有理数性と計算可能性を数学的に厳密に証明した画期的な研究です。熱帯幾何学（熱帯畳み込み）とゲーム理論を巧みに組み合わせることで、複雑な極限値の問題を有限の組合せ論的構造に帰着させる手法は、記号力学系や制御理論の分野においても重要な示唆を与えています。