その語が単位元かどうかは決められない - 群の語の問題と決定不能性

有限表示群 $G = ⟨ S ∣ R ⟩$ と生成元の語 $w$ を受けとり、 $G$ の中で $w = e$ かどうかを答える。この判定を、どんな有限表示群にも通用する形で行う手続きは存在しません^[1]。

まだ見つかっていない、ではない。存在しないことのほうが証明されています。

語の問題

$S$ 上の自由群を $F (S)$ 、 $R$ が生成する正規閉包を $N$ と書きます。有限表示群とは商 $F (S) / N$ のことです。

語 $w$ が $G$ で単位元を表すことは、 $w \in N$ と同じ。書き下すと次の形になります。

$w = i = 1 \prod k u_{i} r_{i}^{ε_{i}} u_{i}^{- 1}, r_{i} \in R, u_{i} \in F (S), ε_{i} = \pm 1$

関係語を好きな元で共役にとり、好きな個数だけ掛け合わせる。それで $w$ に届くかどうかが問われています。

語の問題とは、 $w$ を入力してこの形に書けるかを答える判定問題です^[5]。

片側だけは必ず終わる

$w$ が単位元を表すなら、上の積が現実に存在します。 $k$ と $u_{i}$ の長さに上限を決めて全部試し、外れたら上限を $1$ 上げる。有限個ずつの照合を積み重ねれば、いつか必ず当たります。

つまり「単位元である」という答えのほうは、有限時間で確認できる。単位元を表す語の全体は帰納的可算です^[5]。

止まらないのは反対側です。 $w$ が単位元でないとき、照合は当たりを引かないまま伸び続ける。どこで打ち切ってよいかを教えてくれるものが、どこにもない。

決定不能性の正体はこの非対称にあります。「はい」なら必ず分かり、「いいえ」が分からない。

Dehn が 1911 年に並べた 3 つ

Dehn は生成元と関係式による表示を使い、3 つの判定問題を立てました^[3]。表示という考え方そのものは、その前に von Dyck が詳しく調べています^[3]。

語の問題。語

w

が単位元を表すか。

共役問題。2 つの語

u, v

に対し

v = g u g^{- 1}

となる

g

があるか。

同型問題。2 つの有限表示が同じ群を定めるか。

Dehn 自身は 1 番目を Identitätsproblem と呼びました。「群の元が生成元からの組み立てで与えられている。その元が単位元に等しいかどうかを有限回の操作で決める方法を示せ」というのが原文の言い回しです^[3]。

共役問題は語の問題を含みます。 $v = e$ ととれば、 $u$ が単位元と共役であることと $u = e$ が同じになるため^[3]。難しさの順は語、共役、同型と上がっていきます。

3 つを並べたあと、Dehn はこれらを解くには対象を深く調べるほかないだろうと書き添えました^[3]。

Dehn のアルゴリズム

翌年、Dehn は曲面群でこの問題を解いています^[4]。種数 $g \geq 2$ の向きづけ可能閉曲面の基本群は、次の表示を持ちます^[2]。

$π_{1} (Σ_{g}) = ⟨ α_{1}, β_{1}, \dots, α_{g}, β_{g} ∣ [α_{1}, β_{1}] \dots [α_{g}, β_{g}] = 1 ⟩$

関係語を $r = [α_{1}, β_{1}] \dots [α_{g}, β_{g}]$ とします。長さは $4 g$ です。

短縮関係 $r_{1} = r_{2}$ を、次の 3 つを満たす組と定めます^[2]。

∣ r_{1} ∣ > ∣ r_{2} ∣

である。

r_{1} r_{2}^{- 1}

か

r_{2} r_{1}^{- 1}

が

r

の巡回置換になっている。

∣ r_{1} ∣ + ∣ r_{2} ∣ = ∣ r ∣

である。つまり

r_{1}

と

r_{2}

の継ぎ目で打ち消しが起きない。

Dehn の定理はこうです。簡約語 $w \neq = 1$ が $π_{1} (Σ_{g})$ で単位元を表すなら、 $w$ はある短縮関係の左辺 $r_{1}$ を部分語として含む^[2]。

$∣ r_{1} ∣ > ∣ r_{2} ∣$ と $∣ r_{1} ∣ + ∣ r_{2} ∣ = 4 g$ を合わせると $∣ r_{1} ∣ > 2 g$ が出ます。関係語の半分より長い断片が、必ず語の中に顔を出しているという主張。

手続きはこれだけです。半分より長い部分語を探し、あれば短いほうへ置き換えて簡約する。長さが真に減るので有限回で止まり、空語になれば単位元、置き換えが見つからなくなれば単位元ではない。

置き換えは長さを $2$ ずつ落とします。種数 $2$ なら $∣ r ∣ = 8$ で、 $5$ 本の断片が $3$ 本に縮む。これを繰り返すと語は必ず尽きます。

なぜ半分より長い断片が必ず出るのか。双曲幾何で読めます^[2]。

単位円板モデルの中に、原点から距離 $R$ の点を等間隔に $4 g$ 個とって正 $4 g$ 角形を作ります。 $R \to 1$ では頂点が無限遠に届いて内角が $0$ に近づき、 $R \to 0$ ではユークリッドの正 $4 g$ 角形に近づいて内角が $\frac{4 g - 2}{4 g} π$ に近づく。

$\frac{4 g - 2}{4 g} π > \frac{1}{2 g} π$

不等式が成り立つので、中間値の定理から内角がちょうど $\frac{π}{2 g}$ になる $R$ がとれます^[2]。

この角度なら 1 つの頂点のまわりに $4 g$ 枚が集まって $2 π$ になり、双曲平面がすきまなく貼れる。貼り合わせの規則が曲面の関係式と一致し、タイルの辺全体が $π_{1} (Σ_{g})$ のケイリーグラフになります。

単位元を表す簡約語は、このグラフの中の閉じた道です。閉じた道の内側は有限枚のタイルで埋まっていて、その枚数についての帰納法が効く。角度が $\frac{π}{2 g}$ にそろっているぶん道の折れ方に制限がかかり、外周のタイルのうち少なくとも 1 枚は、道と $2 g$ 本より多くの辺を共有します^[2]。

一般には解けない

1947 年、Post と Markov が有限表示半群で語の問題の決定不能性を示しました^[3]。群まで届くのに、そこから 5 年かかっています。

Novikov が 1952 年に結果を告げ、1955 年に証明を発表しました^[3]。Church の学生だった Boone が独立に到達し、1954 年から 57 年の 6 本の論文を経て 1959 年に発表^[3]。Britton も 1958 年に独立の証明を与えています。

定理の形はこうです。語の問題が決定不能な有限表示群が存在する^[1]。

半群と群の差は逆元にあります。半群では書き換えが一方通行で、いちど書いたものが消えない。群では $x x^{- 1}$ がいつでも消えるので、計算の跡が語に残りません。この差を埋めるのに 5 年かかったことになる。

Novikov は語の問題より先に、1954 年に共役問題の非可解性を出しています。

語の問題より広い問いなので、非可解性はこちらのほうが先に届いた。

停止問題を群に埋める

方針は、群の語の問題を停止問題と同じ難しさにすることです^[1]。任意のプログラム $p$ に語 $w_{p}$ を対応させ、 $p$ が停止することと $w_{p} = e$ が同値になるように群を組む。

いま最も短い道筋は Higman の埋め込み定理を通ります^[3]。有限生成群が有限表示群に埋め込めるための必要十分条件は、その群が帰納的可算な関係式の集合で表示できることです。

帰納的可算だが帰納的でない集合 $E \subset N$ をとります。停止するプログラムの番号の集合がその例で、存在は対角線論法から出ます^[5]。

$G = ⟨ a, b, c, d ∣ a^{- n} b a^{n} = c^{- n} d c^{n} (n \in E)⟩$

関係式の集合は帰納的可算なので、Higman の定理から $G$ は有限表示群 $G^{'}$ へ埋め込めます^[3]。

$G$ の中で $a^{- n} b a^{n} c^{- n} d^{- 1} c^{n} = e$ が成り立つのは $n \in E$ のときに限ります。 $E$ が帰納的でない以上、この判定はできない。埋め込みは単射なので、 $G^{'}$ の中でも同じ語の判定ができません。

無限個の関係式を有限個へ詰め直す。Higman の定理が引き受けているのはその一点だけです。

手で書ける例

Tseytin が 1957 年に挙げた半群は、生成元 5 個と関係式 9 個で書けます^[3]。

$⟨ a, b, c, d, e ∣ a c = c a, a d = d a, b c = c b, b d = d b, ce = ec a, d e = e d b, c d c a = c d c a e, c aaa = aaa, d aaa = aaa ⟩$

判定できないのは、与えられた語が $aaa$ に等しいかどうかです。判定できない相手をひとつの語に固定してもなお決まらない、という強い形になっています^[3]。

半群なら生成元 2 個と関係式 3 個の例まで知られています^[3]。群の側では Borisov が 1969 年、Collins が 1986 年に具体的な表示を書き下しました。

どんな性質も表示からは読めない

Markov 性質を次で定めます^[1]。

同型で保たれる。

その性質を持つ有限表示群が存在する。

その性質を持つどんな有限表示群にも埋め込めない有限表示群が存在する。

有限であることが例になります^[1]。有限群は存在し、 $Z$ はどんな有限群にも埋め込めない。2 つ目と 3 つ目がこれで埋まります。

Adian が 1955 年、Rabin が 1958 年に示した定理はこうです。任意の Markov 性質 $P$ について、与えられた有限表示が $P$ を持つ群を定めるかどうかを判定するアルゴリズムは存在しない^[1]。

証明は一様な語の問題の埋め込みです^[1]。有限表示群 $G$ と語 $w$ から別の有限表示群 $K$ を組み立て、 $K$ が $P$ を持つことと $G$ で $w = e$ が同値になるようにする。 $P$ が判定できるなら語の問題も解けてしまう、という向きで矛盾が出ます。

自明・有限・可換・冪零・可解・自由・ねじれ自由・残余有限。どれも表示からは機械的に読めません^[3]。

判定できる問い

生成元の個数、関係式の個数、生成元と関係式の長さ。表示に書いてあるものは数えれば分かる

判定できない問い

その表示が定める群が自明か、有限か、可換か。書いていないものは、どう読んでも出てこない

多様体の同相問題が決定不能であることも、ここからそれほど遠くない場所で出ます^[3]。基本群の表示を経由するためです。

解ける側も広い

決定不能なのは一様な手続きのほうで、個々の群では解けることが多い。

有限群では元を全部並べればよく、自由群では簡約して空語かどうかを見るだけ。1 関係式群は Magnus が解いています^[6]。

残余有限な有限表示群には、きれいな手が使えます。2 つの探索を同時に走らせるだけです。

片方は $w$ が関係語の共役の積で書けるかを、上限を上げながら探す。もう片方は $G$ から有限群への準同型を小さいほうから全部並べ、 $w$ の像が単位元にならないものを探す。

$w = e$ なら 1 つ目が当たります。 $w \neq = e$ なら、残余有限性から $w$ を単位元へ送らない有限商があるので 2 つ目が当たる。どちらかは必ず止まるので、両方を並行に走らせておけば答えが出ます。

冒頭の非対称が、ここでは両側にそろっている。片側しか止まらない探索を 2 本ぶつけると判定になる、という形です。

双曲群では Dehn のアルゴリズムがそのまま動きます。1980 年代半ばに、双曲的であることと語の問題が線形時間で解けることが同値だと分かりました^[6]。

Dehn 関数で言い直すと、双曲的であることは Dehn 関数が線形であることと同値で、さらに二次より真に小さいだけでも線形に落ちます^[6]。線形と二次のあいだに何もない。

自動群、CAT(0) 群、半双曲群では Dehn 関数が二次で抑えられます^[6]。

解けるとは、上限があるということ

面積関数を定めます。長さ $n$ 以下で単位元を表す語について、必要な共役の個数の最小値をとり、その最大値を $Area (n)$ とする。

Gersten の定理は、有限表示について次の 3 つが同値だと言います^[6]。

語の問題が解ける。

Area

が帰納的関数である。

Area

が帰納的関数で上から抑えられる。

「解ける」ことと「証明の長さに計算可能な上限がある」ことが、同じ意味だと述べています。上限さえあれば、そこまで探して見つからなかった時点で単位元ではないと結論できる。

冒頭で見た非対称が、ここで正確な形になりました。止まらない側を止めるものは、上限のほかにありません。

有限表示群 $G$ で、語 $w$ が単位元を表すかどうかを探索したとします。正しいのはどれですか。

$w = e$ でも $w \neq = e$ でも、探索は有限時間で止まる
$w = e$ なら必ず止まるが、 $w \neq = e$ では止まるとは限らない
$w \neq = e$ なら必ず止まるが、 $w = e$ では止まるとは限らない

__RESULT__

$w = e$ なら関係語の共役の積として書けるので、短いものから順に照合すればいつか一致します。 $w \neq = e$ のときは一致が起きず、打ち切ってよい根拠も出てきません。この片側だけ止まる性質が、単位元を表す語の全体が帰納的可算だということの中身です。

$w$ が単位元かどうかは、有限個の記号で完全に書かれた問いです。それでも答えを出す機械が作れない。書けることと決められることのあいだに、埋まらない隙間がある。

参考

Bjorn Poonen, *Undecidability in group theory, topology, and analysis*, Rademacher Lecture 2, MIT

Andrew Putman, *The word problem for surface groups and hyperbolic geometry*, University of Notre Dame

Stefan Müller-Stach, *Max Dehn, Axel Thue, and the Undecidable*

Pierre de la Harpe, *Topologie, théorie des groupes et problèmes de décision*, Gazette des mathématiciens

Joseph J. Rotman, *The Word Problem*, chapter 12 of *An Introduction to the Theory of Groups*

Jon McCammond, *Algorithms, Dehn functions, and automatic groups*

有限表示群 $G$ と語 $w$ を渡されても、$w = e$ かどうかを判定する一般の手続きはありません。単位元である側だけは有限時間で確認でき、そうでない側はいつまでも終わらない。この非対称が決定不能性の中身です。Dehn が 1911 年に並べた 3 つの問題から始め、曲面群で動く Dehn のアルゴリズムを双曲平面のタイル貼りで説明し、Novikov と Boone の定理、Higman の埋め込み定理を経由する短い構成、Adian と Rabin の定理まで。解ける側では、残余有限な群で 2 本の探索をぶつける手と、解けることは証明の長さに計算可能な上限があることだ、という Gersten の同値も扱いました。