共役言語と群の部分集合に対する共役増長

基本情報

• 論文ID: 2510.20923
• タイトル: Conjugacy languages and conjugacy growth relative to subsets of groups
• 著者: André Carvalho (University of Porto), Ana-Catarina C. Monteiro (NOVA FCT)
• 分類: math.GR (群論)
• 提出日時: 2025年10月23日
• 論文リンク: https://arxiv.org/abs/2510.20923

要約

本論文は群論における共役言語（conjugacy languages）の問題、特に一般化共役問題（generalized conjugacy problem）を研究する。核心的な問題は、群元素 $g \in G$ と部分集合 $U \subset G$ が与えられたとき、$g$ が $U$ 内に共役元素を持つかどうかを判定することである（共役子に対する制約がある場合もある）。著者は対応する言語 $\text{ConjGeo}(U,V)$、$\text{CycGeo}(U)$、$\text{ConjSL}(U)$、$\text{ConjMinLenSL}(U,V)$ を定義し、複数の群類に対する正則性結果を証明した：自由群に対して $U, V$ が有理部分集合のとき、これらの言語は正則である；双曲群に対して $U$ が正則測地言語で表現可能なとき成立；仮想循環群と仮想アーベル群についても対応する結果を得た。さらに、著者は相対共役増長関数を定義し、その振る舞いが部分集合の選択に強く依存することを示した。

研究背景と動機

問題背景

1. 古典的共役問題：群論の基本的な問題の一つは共役問題（CP）である。すなわち、2つの群元素が共役であるかどうかを判定する問題である。これは一般化共役問題（GCP）に推広できる：元素 $g$ と部分集合 $U$ が与えられたとき、$g$ が $U$ 内に共役元素を持つかどうかを判定する。
2. 形式言語と群論の交差：形式言語理論は群論の問題を研究するための強力なツールを提供する。例えば、Anisimovの定理は有限群が正確に字問題が正則言語である群であることを示す；Muller-Schupp定理は仮想自由群を字問題が文脈自由である群として特徴付ける。
3. 既存研究の限界：
   • Ciobanuら12は $U = V = G$ の場合の共役言語を研究した
   • Ladraと Silva23は仮想自由群の一般化共役問題が決定可能であることを証明した
   • Carvalhoと Silva10は有理部分集合の二重一般化共役問題を研究した
   • しかし、一般的な部分集合 $U \subset G$ に対する共役言語の性質は体系的に研究されていない

研究動機

1. 理論的完全性：$U = G$ から一般的な部分集合 $U$ への推広により、より完全な理論的枠組みを構築する
2. 決定可能性問題：言語理論の性質（例えば正則性）を通じて決定可能性の結果を確立する
3. 増長関数の振る舞い：相対共役増長関数は古典的共役増長と完全に異なる振る舞いを示す可能性がある
4. 異なる群類の統一的処理：自由群、双曲群、仮想循環群、仮想アーベル群などに対する統一的な言語理論的枠組みを提供する

核心的貢献

1. 相対共役言語の定義：部分集合 $U, V \subseteq G$ に対して、以下の言語を体系的に定義した：
   • $\text{ConjGeo}(U,V)$：最短共役代表の言語（制約付き）
   • $\text{CycGeo}(U)$：循環測地語言語
   • $\text{ConjSL}(U)$：短辞書式順序共役標準形言語
   • $\text{ConjMinLenSL}(U,V)$：最小長短辞書式順序言語
2. 自由群の正則性結果（定理4.5）：自由群 $F_X$ と有理部分集合 $U, V$ に対して、$\text{ConjGeo}(U,V)$ と $\text{ConjMinLenSL}(U,V)$ が正則言語であることを証明した
3. 双曲群の正則性結果（定理5.8）：$\delta$-双曲群に対して、$L$ が正則測地言語であれば、$\text{ConjGeo}(L\pi)$ と $\text{ConjMinLenSL}(L\pi)$ が正則であることを証明した
4. 仮想循環群の完全な特徴付け（定理6.1）：仮想循環群と任意の有理部分集合 $U$ に対して、$\text{ConjSL}(U)$ が正則であることを証明した
5. 仮想アーベル群の言語類保存性（定理7.3, 7.4）：適切な条件下で、$\text{ConjGeo}(U)$ が元の言語類の性質を保存することを証明した
6. 相対共役増長の多様性（定理3.1）：有理部分集合 $U_d$ を構成し、相対累積共役増長 $cc_{F_2,X,U_d}(n)$ が $n^{d-1}$ から $n^d$ の位数の多項式であることを示し、古典的な指数増長との顕著な違いを示した
7. 決定可能性との関連（命題3.2）：共役言語の正則性と一般化共役問題の決定可能性の間の関連を確立した

方法の詳細

問題の定義

核心的な問題：一般化共役問題（制約付き）

• 入力：群元素 $g \in G$、部分集合 $U, V \subseteq G$
• 問題：$u \in U$ と $v \in V$ が存在して $g = v^{-1}uv$ が成立するか
• 特殊な場合：$V = G$ のとき、標準的な一般化共役問題に退化する

重要な定義： $\alpha(K,L) = \bigcup_{u \in L} u^{-1}Ku$

これは $K$ の元素が $L$ の元素によって共役化された後の和集合を表す。

核心的な言語の定義

部分集合 $U, V \subseteq G$ と生成集合 $X$ に対して：

1. $\text{ConjGeo}_X(U,V)$： $\text{ConjGeo}_X(U,V) = \text{ConjGeo}_X(G) \cap \alpha(U,V)\pi^{-1}$$\alpha(U,V)$ 内の各共役類の最短代表語を表す
2. $\text{CycGeo}_X(U)$： $\text{CycGeo}_X(U) = \{w \in \text{Geo}_X(U) \mid w \text{ は循環測地語}\}$
3. $\text{ConjMinLenSL}_X(U,V)$： $\text{ConjMinLenSL}_X(U,V) = \{w_g \in \text{Geo}_X(\alpha(U,V)) \mid |g| = |g|_c\}$ ここで $w_g$ は $g$ の短辞書式順序標準形、$|g|_c$ は共役類内の最小長
4. $\text{ConjSL}_X(U)$： $\text{ConjSL}_X(U) = \{z_c \in \text{Geo}_X(\alpha(U)) \mid c \text{ は共役類}\}$$U$ と交差する各共役類の短辞書式順序標準形

技術的な革新点

1. 自由群の置換言語技術（Permutation Language）

定義4.2：正則言語 $K, L$ に対して、置換言語を定義する $P_{K,L} = \{u\ell \mid \ell \in L, \ell u \in K\}$

重要な補題（命題4.3）：$UV$ が約分的である（reduced）場合、すなわち、すべての $k \in U, \ell \in V$ に対して $|k\ell| \geq |k|$ が成立する場合、 $\text{ConjGeo}(U,V) = \text{ConjGeo}(F_X) \cap P_{U,V}$

証明の概要：

• 最小オートマトン $A = (Q, q_0, T, E)$ を使用して $U$ を認識する
• $P_{U,V} = \bigcup_{p \in Q, t \in T} L_{p,t}(L_{q_0,p} \cap V)$ を証明する
• 重要な観察：自由群では、$UV$ が約分的であることは $\ell$ が $k$ の前置詞であることと $|k\ell| = |k|$ が同値である

2. 双曲群の準測地技術

補題5.1-5.3：双曲群の薄い三角形性質を利用する：

• 補題5.1：完全約分語の共役関係は短共役子（長さ $\leq 2\delta + 1$）を通じて実現可能
• 補題5.2：準測地語の推広版
• 補題5.3：正則測地言語から準約分代表言語を構成可能

命題5.5：$(1,r)$-準測地と $(1,s)$-準測地は有界非同期伴走性質（boundedly asynchronous fellow travel property）を満たし、距離定数 $N$ は $r, s, \delta$ に依存する

系5.6：$(1,\epsilon)$-準測地言語は二重自動構造を構成する

核心的な技術（補題5.7）：正則測地言語 $K$ に対して、 $\text{CycGeo}(\alpha(K\pi)) = S \cup \left[\text{CycGeo}(G) \cap \bigcup_{|z| \leq 2(\delta+\gamma)} \text{Cyc}(L_2(z))\right]$ ここで $S$ は有限言語、$L_2(z)$ は共役関係オートマトンによって定義される

3. 仮想アーベル群の自己同型技術

重要な観察（補題7.2）：アーベル群 $G$ と自己同型 $\phi$ に対して、 $\phi(\text{Geo}_X(U)) = \text{Geo}_{\phi(X)}(\phi(U))$

定理7.4の証明戦略：

• $N$ を有限指標アーベル正規部分群、$T = \{b_1, \ldots, b_n\}$ を剰余類代表とする
• 各 $t \in T$ は共役自己同型 $\alpha_t: n \mapsto t^{-1}nt$ を定義する
• $U = \bigcup_{i=1}^n U_i b_i$（$U_i \in C_\bullet(N)$）に対して、計算する $\alpha(U_i b_i) = \bigcup_{s \in T} [U_i N(Q_{b_i}^{-1} - I)]^{Q_s} \cdot s^{-1}b_i s$ ここで $Q_t$ は $\alpha_t$ の行列表現
• full semi-AFL の閉包性を利用して $\alpha(U_i b_i) \in C_\bullet(G)$ を証明する

実験設定

注：本論文は純粋な理論数学論文であり、実験部分を含まない。すべての結果は厳密な数学的証明である。

構成的な例

定理3.1の構成：

• Rigo26の構成を使用：各 $d \in \mathbb{N}$ に対して、長さ $n$ の語の数が $n^d$ である正則言語 $L_d$ が存在する
• 字母表 $\Sigma_d = \{a_1, \ldots, a_{u_d}\}$、各 $a_i$ を $a^i b^i$ に置き換える
• 言語 $K_d \subseteq \{a,b\}^*$ を得て、その元素は自由群内で自由独立である
• 分析： $\frac{\sum_{i=0}^{\lfloor n/(2u_d) \rfloor} 2i^d}{i-2} < cc_{F_2,X,U_d}(n) < \sum_{i=0}^{\lfloor n/2 \rfloor} i^d$$n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$ を得る

実験結果

主要な理論的結果

1. 自由群（定理4.5）

結果：自由群 $F_X$ と有理部分集合 $U, V$ に対して、

• $\text{ConjGeo}(U,V)$ は正則言語である
• $\text{ConjMinLenSL}(U,V)$ は正則言語である

証明の重要性：

• Carvalho-Silva10の分解を利用：$\alpha(U,V) = \bigcup_{a \in \tilde{X}} (Y_a \cup Z_a)$
• 各分量に置換言語技術を適用する
• $\text{ConjGeo}(F_X)$ の正則性を利用する

意義：10の文脈自由結果を正則言語に改善した

2. 双曲群（定理5.8）

結果：$\delta$-双曲群 $G$ と正則測地言語 $L$ に対して、

• $\text{ConjGeo}(L\pi)$ は正則である
• $\text{ConjMinLenSL}(L\pi)$ は正則である

証明の構造： $\text{ConjGeo}(L\pi) = S \cup \left[\left(\text{CycGeo}(\alpha(L\pi)) \cap \bigcup_{k \geq 8\delta+1} X^k\right) \setminus \text{Cyc}\left(\bigcup_{|\alpha| \leq 2\delta+1} L(\alpha)\right)\right]$

系5.9：仮想自由群の一般化共役問題は決定可能である（新しい言語理論的証明を提供）

3. 仮想循環群（定理6.1）

結果：仮想循環群 $G$ と有理部分集合 $U$ に対して、$\text{ConjSL}(U)$ は正則である

証明の要点：

• 分解 $\text{ConjSL}(U) = (\text{ConjSL}(U) \cap C\pi^{-1}) \cup (\text{ConjSL}(U) \cap (G \setminus C)\pi^{-1})$
• ここで $C$ は $H \cong \mathbb{Z}$ の中心化子
• 第二項は有限である（$G \setminus C$ は有限個の共役類のみを持つため）
• 第一項は $\text{CycGeo}(\alpha(U))$ の正則性と集合操作を通じて得られる

4. 仮想アーベル群（定理7.3, 7.4）

定理7.3：$G$ を仮想アーベル群、$N$ を有限指標アーベル正規部分群、$U \subseteq N$ とする。$C$ が有限和と正則交に対して閉じており、$\text{Geo}_Z(U) \in C$ であれば、生成集合 $Z$ が存在して

• $\text{ConjGeo}_Z(U) \in C$
• $\text{ConjMinLenSL}_Z(U) \in C$

定理7.4：$C$ が full semi-AFL であり、$U \in C_\bullet(G)$ であれば、$\alpha(U) \in C_\bullet(G)$ である

系7.5：$K \in C_\forall(G)$ であれば、$\text{ConjGeo}(K) \in C$ である

増長関数の結果（定理3.1）

構成：各 $d \in \mathbb{N}$ に対して、有理部分集合 $U_d \in \text{Rat}(F_2)$ が存在して $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$

対比：古典的な累積共役増長 $cc_{F_2,X}(n)$ は指数的である

意義：

1. 相対増長が任意の次数の多項式であることを示す
2. 部分集合の選択が増長振る舞いに根本的な影響を与えることを示す
3. 一般化共役問題の複雑性に対する定量的な視点を提供する

決定可能性の結果（命題3.2）

定理：部分集合類 $C$ と言語類 $L$ に対して、以下が成立する場合：

1. $U, V \in C \Rightarrow \text{ConjGeo}(U,V) \in L$ が計算可能
2. $U \in C, g \in G \Rightarrow U^g \in C$ が計算可能
3. $G$ が決定可能な共役問題を持つ
4. $L$ が決定可能な成員問題を持つ

ならば、$G$ は決定可能な $C$-一般化共役問題（$C$-制約付き）を持つ

応用：各群類の正則性結果と組み合わせることで、直接的に決定可能性を得る

関連研究

共役問題の言語理論的研究

1. Holt-Rees-Röver22：
   • 共役問題を序対 $(u,v)$ の集合として定義
   • 仮想自由群の共役問題が非同期索引付きであることを証明
   • 仮想循環群が共役問題が非同期文脈自由である群であることを特徴付ける
2. Levine24：
   • 仮想自由群が各共役類が文脈自由部分集合である群であることを特徴付ける
   • Muller-Schupp定理を推広する
3. Ciobanu-Hermiller-Holt-Rees12：
   • $\text{ConjGeo}(G)$, $\text{ConjMinLenSL}(G)$, $\text{ConjSL}(G)$ などの言語を定義
   • 双曲群の $\text{ConjGeo}(G)$ と $\text{ConjMinLenSL}(G)$ が正則であることを証明
   • 仮想アーベル群の $\text{ConjGeo}(G)$ が区分可測であることを証明
   • 仮想循環群の $\text{ConjSL}(G)$ が正則であることを証明

一般化共役問題の研究

4. Ladra-Silva23：
   • 仮想自由群の有理制約一般化共役問題が決定可能であることを証明
   • 方法：共役子言語を構成し、その正則性を証明
5. Carvalho-Silva10：
   • 二重一般化共役問題を研究
   • 仮想自由群と有理部分集合 $U, V$ に対して、$\alpha(U,V)\pi^{-1}$ が文脈自由であることを証明
   • 測地言語表現の概念を導入
6. Diekert-Gutiérrez-Hagenah16：
   • 自由群における有理制約付き存在理論がPSPACE-完全であることを証明

自動群理論

7. Epstein等17：
   • 自動群と二重自動群の基礎理論
   • 短辞書式順序標準形の正則性
8. Herbst19, Carvalho-Nyberg-Brodda9：
   • 言語部分集合の体系的研究
   • $C_\bullet(G)$ 記号と cone、full semi-AFL の性質

本論文の進展

• $U = G$ から一般的な部分集合へ：既存の結果を体系的に推広
• 統一的な枠組み：複数の群類に対する統一的な言語理論的処理
• より強い結果：自由群について文脈自由から正則へ改善
• 新しい視点：相対増長関数が部分集合選択の重要性を明らかにする

結論と議論

主要な結論

1. 言語理論的特徴付け：
   • 自由群：有理部分集合の相対共役言語は正則である
   • 双曲群：測地表現部分集合の相対共役言語は正則である
   • 仮想循環群：有理部分集合の短辞書式順序言語は正則である
   • 仮想アーベル群：言語類保存性質
2. 増長関数の多様性：相対共役増長は任意の次数の多項式であり、古典的な指数増長と鮮明な対比をなす
3. 決定可能性：言語正則性と一般化共役問題の決定可能性の間の関連を確立

限界

1. 仮想アーベル群の制限：
   • 定理7.3は $U \subseteq N$（アーベル部分群内）を要求
   • 一般的な場合（$U$ が $N$ 内にない）は未解決
2. 言語類の要件：
   • 双曲群は正則測地表現を必要とする
   • 仮想アーベル群は $\text{Geo}(U) \in C$ を必要とする
   • すべての有理部分集合がこれらの条件を満たすわけではない（例7.1など）
3. 構成的側面：
   • 定理3.1の増長次数の界は精密ではない（$n^{d-1}$ と $n^d$ の間）
   • 恰度次数 $d$ の例が存在するかは未知
4. 計算複雑性：
   • 決定可能性を証明したが、複雑性は分析していない
   • オートマトン構成の効率は議論していない

今後の方向

論文は2つの開放問題を明確に提示している：

1. 精密な増長次数（問題1）：
   • 有理部分集合 $U_d$ を構成して $cc_{F_2,X,U_d}(n) \sim n^d$ が恰度成立するか
   • 現在は $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$ のみ
2. 仮想アーベル群の一般的な場合（問題2）：
   • $U \not\subseteq N$ のとき、$\text{ConjGeo}(U)$ の性質はどうか
   • 重要な技術的問題：$\text{ConjGeo}(U)$ の元素が $\text{ConjGeo}(G \setminus \alpha(U))$ に属する部分語を含むことができるか
   • 具体的な言語類から開始することを推奨（例えば正則、区分可測、区分除外）
3. その他の潜在的な方向：
   • 計算複雑性分析
   • 他の群類への推広（例えばCAT(0)群、相対双曲群）
   • 複数の制約を持つ一般化共役問題
   • 相対増長関数の漸近的性質

深い評価

利点

1. 理論的深さ：
   • Ciobanuら12の古典的結果を体系的に推広
   • 複数の重要な群類に対する完全な言語理論的特徴付けを提供
   • 証明技術は精巧、特に置換言語と自己同型方法
2. 統一的な枠組み：
   • $\alpha(U,V)$ 記号を通じて異なる場合を統一的に処理
   • $C_\bullet(G)$ 記号は柔軟な言語類処理方法を提供
   • 命題3.2は言語理論と決定可能性の一般的な関連を確立
3. 技術的革新：
   • 置換言語 $P_{K,L}$ は自由群処理の新しいツール
   • 双曲群の準測地技術は既存方法を推広
   • 仮想アーベル群の自己同型行列方法は新規
4. 増長関数の洞察：
   • 定理3.1は相対増長の豊かさを示す
   • 一般化共役問題の複雑性を理解するための定量的視点を提供
   • 構成方法は一般的
5. 執筆の質：
   • 構造が明確で、一般から特殊へと段階的に展開
   • 予備知識が完全で、定義が精密
   • 証明の詳細が充分で、論理が厳密

不足

1. カバー範囲の制限：
   • 仮想アーベル群の結果は $U \subseteq N$ または $\text{Geo}(U) \in C$ を必要とする
   • 一般的な有理部分集合（例7.1など）の処理が不十分
   • 他の重要な群類（例えば右角群、グラフ群）は未涉及
2. 増長関数の精度：
   • 定理3.1の界は厳密ではない（次数で1つ異なる）
   • 精密な次数に達する構成は与えられていない
   • 他の群類の相対増長は探索されていない
3. 計算的側面：
   • アルゴリズム複雑性は分析されていない
   • オートマトン構成の効率は議論されていない
   • 実際の計算可能性は検証されていない
4. 応用シナリオ：
   • 実際の応用は議論されていない（例えば暗号学、アルゴリズム群論）
   • 他の群論的問題との関連が不十分
   • 具体的な例と計算例が不足
5. 開放問題：
   • 仮想アーベル群の一般的な場合は重要な欠落
   • 問題2の技術的困難は十分に分析されていない
   • これらの問題を解決するための可能な方向が不足

影響力

1. 理論的貢献：
   • 共役言語理論に対する重要な推広を提供
   • 部分集合選択と言語性質の間の深い関連を確立
   • 後続研究のための体系的な枠組みを提供
2. 方法論的価値：
   • 置換言語技術は他の問題に適用可能
   • 自己同型方法は仮想アーベル群研究に新しいツールを提供
   • 言語類保存定理は一般的
3. 再現可能性：
   • 証明は詳細で検証可能性が高い
   • 構成方法は明確
   • ただし計算実装は不足
4. 後続研究：
   • 開放問題は明確で、明確な研究方向がある
   • 他の群類の研究のためのテンプレートを提供
   • 関連問題の研究を刺激する可能性がある

適用シナリオ

1. 理論研究：
   • 組合せ群論における決定問題
   • 形式言語理論と代数の交差
   • 増長関数と漸近的性質の研究
2. アルゴリズム群論：
   • 一般化共役問題の判定アルゴリズムの設計
   • 共役類代表の計算最適化
   • 有理部分集合の記号計算
3. 関連分野：
   • 自動群理論
   • 幾何学的群論（双曲群、CAT(0)群）
   • 計算複雑性理論
4. 潜在的な応用：
   • 暗号学における群基プロトコル
   • 位相幾何学における基本群計算
   • オートマトン理論

参考文献（重要な文献）

12 L. Ciobanu, S. Hermiller, D. Holt, S. Rees. Conjugacy languages in groups. Israel J. Math., 211:311–347, 2016.

• 本論文の直接的な基礎、$U = G$ の場合の共役言語を定義

10 A. Carvalho, P. V. Silva. Geodesic languages for rational subsets and conjugates in virtually free groups. arXiv:2410.20412v2, 2024.

• $\alpha(U,V)\pi^{-1}$ の文脈自由性を証明、本論文は正則に改善

23 M. Ladra, P. V. Silva. The generalized conjugacy problem for virtually free groups. Forum Math., 23:447–482, 2011.

• 仮想自由群の一般化共役問題が決定可能である古典的結果

25 D. E. Muller, P. E. Schupp. Groups, the theory of ends, and context-free languages. J. Comput. System Sci., 26(3):295–310, 1983.

• Muller-Schupp定理：仮想自由群の字問題は文脈自由

19 T. Herbst. On a subclass of context-free groups. RAIRO Inform. Théor. Appl., 25:255–272, 1991.

• 仮想循環群の字問題は one-counter、$C_\bullet$ 記号を導入

9 A. Carvalho, C. F. Nyberg-Brodda. On linguistic subsets of groups and monoids. arXiv:2502.14329, 2025.

• 言語部分集合の体系的理論、定理2.2と2.3の出典

総合評価：これは高品質な理論数学論文であり、共役言語理論を部分集合の場合に体系的に推広し、複数の重要な群類に対する深い言語理論的特徴付けを提供する。技術的には革新的（置換言語、自己同型方法）であり、理論的には深い（増長関数の多様性、言語類保存性）。主な不足は仮想アーベル群の一般的な場合が未解決であること、および計算複雑性分析が不足していることである。論文は後続研究に対して明確な方向を提供し、組合せ群論と形式言語理論に対する継続的な影響が予想される。