The Conjugacy Relation on One-sided Subshifts is Non-treeable

本論文は、記述集合論の観点から片側部分シフトの共役関係を研究し、特にアルファベット集合が$\{0,1\}$である場合の共役関係が非木化可能かつ非アメンナブルであることを示しています。

要約

この論文は、数学の「記述集合論」という難しい分野の話ですが、実は**「同じ形をしたパズルをどう見分けるか」**という、とても直感的なテーマを扱っています。

著者の李瑞文（Ruiwen Li）さんは、**「片側シフト（One-sided subshifts）」**と呼ばれるある種の動的システム（ルールに従って並ぶ数字の列）について研究しました。

この論文の核心を、日常の言葉と面白い例えを使って説明しますね。

---

1. 物語の舞台：「無限の数字の列」と「変形ルール」

まず、想像してみてください。
「0」と「1」だけで書かれた、無限に長いテープがあるとします。
例えば：01011001... とずっと続いています。

このテープを**「左にずらす」**という操作を繰り返します。

• 1 回ずらすと：1011001...
• 2 回ずらすと：011001...

この「ずらす操作」を繰り返してできるパターンの集まりを**「片側シフト」**と呼びます。
このテープには、あるルール（禁止された並び）があって、そのルールに従って作られたテープの集まりが「部分シフト」と呼ばれる世界です。

2. 問題：「同じもの」を見分けるのはどれくらい難しい？

ここで、ある質問が出ます。
「2 つのテープの集まり（システム）A と B が、本質的に『同じもの』かどうか、どうやって見分ければいい？」

これを数学的には**「共役（conjugacy）」**と呼びます。

• 例え話：
  • システム A は「赤いブロックでできた城」
  • システム B は「青いブロックでできた城」
  • もし、赤いブロックをすべて青いブロックに置き換え、形も動きも全く同じなら、これらは「同じ城（共役）」です。

数学者たちは、この「同じかどうか」を判定するルールが、どれくらい複雑で、どれほど難しい問題なのかを調べたいのです。

3. 発見：「木」には描けない複雑さ

この論文で著者が証明した最大の発見は、この「同じかどうか」を判定する問題は、「木（ツリー）」の形では描けないほど複雑だということです。

• 「木（ツリー）」とは？

  • 家族の家系図や、会社の組織図を想像してください。
  • 「A は B の親、B は C の親」というように、枝分かれして繋がっている図です。
  • 数学では、もし「同じかどうか」を判定するルールが、この家系図のようにシンプルに枝分かれして整理できるなら、それは**「木化可能（treeable）」**と呼ばれ、比較的「扱いやすい（単純な）」問題だと考えられています。

• この論文の結果：

  • 「0」と「1」だけで作られた片側シフトの「同じかどうか」を判定するルールは、家系図（木）には描けないほど入り組んでいる！
  • つまり、これは**「非常に複雑で、整理しきれない（非木化可能）」**な問題であることが証明されました。

さらに、この問題は**「アミナブル（amenable）」という性質（ある意味で「穏やかで、計算しやすい」性質）も持っていないことがわかりました。
つまり、「この問題は、単純なルールや穏やかな方法では解決できない、極めて複雑な難問だ」**ということです。

4. どうやって証明したの？（魔法の箱と変形）

著者は、以下のような手順で証明しました。

1. 複雑な「魔法の箱」を作る：
   まず、6 種類の異なる記号（a1〜a6 など）を使った、非常に複雑な「テープの集まり」のグループを用意しました。このグループには、「2 つのテープが同じかどうか」を判定するのが、家系図（木）では無理なほど複雑なルールが潜んでいました。

2. それを「0」と「1」に変換する：
   次に、この複雑なグループを、「0」と「1」だけで書かれたテープに変換する「翻訳機（写像）」を作りました。

   • 例：a1 → 110100...（22 桁の 0 と 1 の並び）
   • この変換は、元の複雑なルールを壊さずに、0 と 1 の世界にそのまま持ち込むことができます。

3. 結論：
   「0 と 1」の世界でも、元の複雑なルールが生き残っているため、「0 と 1」だけで作られたテープの「同じかどうか」も、家系図（木）では描けないほど複雑だという結論になりました。

まとめ：この論文が教えてくれること

この論文は、**「一見単純に見える『0 と 1』の並び方でも、その『同じかどうか』を判定するのは、家系図のように整理できるほど単純ではない」**ということを証明しました。

• 日常への例え：
  もしあなたが「2 つのレシピが同じかどうか」を判断しようとしたとき、それが単に「材料のリスト」を比べるだけなら簡単ですが、この論文は「実はそのレシピの背後には、家系図のように整理できないほど複雑な『隠れたルール』が潜んでいる」と言っているのです。

数学の世界では、この発見は**「記述集合論」という分野において、この問題が「非常に高いレベルの複雑さ」を持っている**ことを示す重要な一歩となりました。

一言で言うと：
「0 と 1 の並びパズルが『同じもの』かどうか見分けるのは、家系図のように整理できるほど簡単ではなく、とてつもなく複雑で奥深い問題だった！」というのが、この論文のメッセージです。

技術概要

論文「一側サブシフト上の共役関係は非木型である」の技術的サマリー

著者: Ruiwen Li (南開大学)
日付: 2026 年 3 月 6 日 (arXiv:2603.04776v1)

1. 問題設定と背景

この論文は、記述集合論（Descriptive Set Theory）の観点から、一側サブシフト（one-sided subshifts）の共役関係（conjugacy relation）の複雑性を研究するものである。

• 背景: 記述集合論において、標準ボレル空間上の同値関係の複雑さは「ボレル還元（Borel reducibility）」を用いて比較される。特に、可算ボレル同値関係（countable Borel equivalence relations）の階層構造は重要な研究対象である。
• 既知の成果:
  • 両側サブシフト（two-sided subshifts）の共役関係は、Clemens [5] によって普遍的可算ボレル同値関係 $E_\infty$ とボレル双同値（Borel bireducible）であることが示されている。
  • 特定のクラス（Toeplitz サブシフトや指定性を持つサブシフトなど）については、その複雑性が研究されており、非木型（non-treeable）や非アメンナブル（non-amenable）であることが知られている。
• 未解決の問題: 一側サブシフト（特にアルファベット集合が $\{0, 1\}$ の場合）の共役関係の正確な複雑性は長らく不明であった。Clemens [5] はこの問題（Question 1.1）を提起している。
• 本研究の目的: 一側サブシフト、特にアルファベット $\{0, 1\}$ 上の推移的（transitive）なサブシフトの共役関係が、記述集合論的に「非木型」かつ「非アメンナブル」であることを証明すること。

2. 手法と構成

著者は、両側サブシフトにおける Deka ら [7] の構成を基盤としつつ、一側サブシフトの非可逆性（left shift が可逆でないこと）を克服するための修正を加えることで証明を行っている。

2.1. 主要な構成要素

1. 禁止語によるサブシフトの定義:

   • 文字集合 $A$ を $\{a_i, \tilde{a}_i \mid 1 \le i \le 6\} \cup \{\#\}$ と定義する。
   • 奇数長の単語の集合 $R \subset (A \setminus \{\#\})^*_{odd}$ を選び、禁止語の集合を $\{ \#w\# \mid w \in R \}$ として、対応するサブシフト $X(R)$ を定義する。
   • これらのサブシフトの集合 $S(A)$ は、ヴィエトリス位相（Vietoris topology）のもとでコンパクトな距離空間となる。

2. 群作用の構築:

   • 両側シフト空間 $A^\mathbb{Z}$ 上の自己同型群 $\text{Aut}(A^\mathbb{Z})$ の部分群 $\Gamma$ を構成する。
   • 6 個の生成元 $f_1, \dots, f_6$ を定義し、これらは特定のブロックコード（block code）によって定義される。
   • これらの生成元は「#-保存（#-preserving）」であり、$f_i^2 = \text{id}$ を満たす。
   • 生成される群 $\Gamma$ は、$(\mathbb{Z}_2 * \mathbb{Z}_2 * \mathbb{Z}_2)^2$ に同型であり、自由積の構造を持つ。

3. 埋め込み（Embedding）の構成:

   • 両側サブシフトの集合 $S(A)$ から、アルファベット $\{0, 1\}$ 上の一側推移的サブシフトの集合へのボレル単射 $\phi$ を構成する。
   • 各記号 $a \in A$ を長さ 22 の固定された 0-1 列 $\rho(a)$ に符号化する（$\rho$）。
   • 符号化された列 $\rho(x)$ を用いて、一側サブシフト $\phi(X)$ を生成する。
   • この符号化は「一意に読める（uniquely readable）」ように設計されており、元のサブシフト $X$ の構造が $\phi(X)$ に保存される。

2.2. 証明の論理

1. 群作用の性質: 群 $\Gamma$ の $S(A)$ への作用は、測度保存かつほとんど至る所自由（a.e. free）である。
2. 同値関係の複雑性:
   • $\Gamma$ は $F_2 \times F_2$（2 個の自由群の直積）を部分群として含む。
   • Pemantle と Peres [19] の結果により、$F_2 \times F_2$ の測度保存自由作用によって誘導される同値関係は**非木型（non-treeable）**である。
   • $\Gamma$ は非アメンナブル群であるため、誘導される同値関係は**非アメンナブル（non-amenable）**である。
3. 共役関係への還元:
   • 構成した写像 $\phi$ は、$S(A)$ 上の $\Gamma$ による軌道同値関係（conjugacy relation）を、$\{0, 1\}$ 上の推移的一側サブシフトの共役関係にボレル還元する。
   • 具体的には、$X_1, X_2 \in S(A)$ が $\Gamma$ によって共役（同値）であるとき、$\phi(X_1)$ と $\phi(X_2)$ は位相的共役（topologically conjugate）であることを示す。

3. 主要な結果

定理 1.2:
アルファベット集合 $\{0, 1\}$ 上の推移的（transitive）一側サブシフトの共役関係は、**非木型（non-treeable）かつ非アメンナブル（non-amenable）**な可算ボレル同値関係である。

• 非木型（Non-treeable）: この同値関係は、ボレル非巡回グラフ（Borel acyclic graph）の連結成分として記述できない。これは、その複雑さが「木型」な構造（例えば超有限関係）よりも高いことを意味する。
• 非アメンナブル（Non-amenable）: この同値関係は、アメンナブルな群の作用によって誘導されない。これは、その構造が非常に複雑で、単純な近似ができないことを示唆する。

4. 意義と貢献

1. Clemens の問いへの部分的回答:

   • Clemens [5] が提起した「$\{0, 1\}^\mathbb{N}$ 上のシフト同型の複雑性は何か？」という問いに対し、その複雑性が「非木型かつ非アメンナブル」であることを初めて示した。
   • 両側サブシフトの共役関係が普遍的可算ボレル同値関係 $E_\infty$ であるのに対し、一側サブシフトの共役関係も同様に高い複雑性を持つことが示された。

2. 一側サブシフトの理論的進展:

   • 一側サブシフトは非可逆な力学系であり、両側サブシフトとは異なる技術的困難（特にアルファベット集合の縮小が容易でない点）がある。
   • 著者は、両側の場合の構成 [7] を巧妙に修正し、一側の場合でも同様の複雑性結果が得られることを示した。

3. 記述集合論的力学系への寄与:

   • 力学系の分類問題において、どのようなクラスが「複雑（非分類可能）」であるかを明確にする重要なステップである。
   • 非木性や非アメンナブル性は、その同値関係が「超有限（hyperfinite）」や「滑らか（smooth）」ではないことを意味し、分類不可能性の強力な指標となる。

5. 結論

本論文は、記述集合論の枠組みを用いて、一側サブシフトの共役関係が非常に高い複雑性（非木型かつ非アメンナブル）を持つことを証明した。この結果は、力学系の分類問題における「複雑な」クラスの範囲を明確にし、一側サブシフトが両側サブシフトと同様に、記述集合論的に非自明な構造を持つことを示唆している。