組合せ群論

同義語：combinatorial group theory組み合わせ群論

概要

前提知識: 群, 自由群, 群の表示

組合せ群論（combinatorial group theory）は、群を生成元と関係式で与え（群の表示）、生成元を並べた語を操作することで群を調べる群論の分野である。無限群の多くは元を並べた表では扱えないが、有限個の生成元と関係式なら書き下せる。組合せ群論は、そのような有限の記述から群の性質をどこまで読み取れるか、読み取る手続き（アルゴリズム）があるかを問う。
この記事では、まず分野の対象と主な問いを定義とともに述べ、代表的な定理を、それを扱う記事とともに一覧にする。続いて代表例として「自由群は剰余有限であり、有限生成の剰余有限群は Hopf 的である」を完全に証明し、そこから「階数 $n$ の自由群を生成する $n$ 個の元は基底である」と「剰余有限な有限表示群の語の問題は解ける」を導く。最後に学ぶ順の道筋を示す。

定義

集合 $X$ 上の自由群 $F(X)$ と部分集合 $R\subset F(X)$ に対し、$R$ を含む最小の正規部分群（正規閉包）を $N(R)$ と書き、剰余群 $\langle X\mid R\rangle:=F(X)/N(R)$ を生成元 $X$・関係子 $R$ で与えられる群という。群 $G$ とこの剰余群との同型を、$G$ の表示という（群の表示の定義「群の表示」）。$X$ も $R$ も有限にとれる群を有限表示群、$X$ を有限にとれる群を有限生成群という。すべての群は表示をもつ（群の表示の命題「すべての群は表示を持つ」）。

組合せ群論

群をその表示 $\langle X\mid R\rangle$ を通じて調べ、とくに $X$ の文字とその逆を並べた語の変形・比較・数え上げによって群の性質を導く群論の分野を組合せ群論という。

同じ群は多くの表示をもつ。たとえば $\langle a\mid a^2\rangle$ と $\langle a,b\mid a^2,\ b\rangle$ はどちらも位数 2 の巡回群を表す。有限表示どうしは、関係子の追加・削除と生成元の追加・削除からなる Tietze 変換で移り合う（群の表示の定理「Tietzeの定理」）。組合せ群論の主張は、表示の取り方によらない群の性質についてのものと、具体的な表示から何かを計算する手続きについてのものとに分かれる。

組合せ群論の主な問い

Dehn の 3 つの問題

$G=\langle X\mid R\rangle$ を有限表示とする。

語の問題・共役問題・同型問題

語の問題：語 $w$ が与えられたとき、$w$ が $G$ の単位元を表すかどうかを判定する。
共役問題：語 $u,v$ が与えられたとき、$u$ と $v$ が $G$ の中で共役(群論)であるかどうかを判定する。
同型問題：2 つの有限表示が与えられたとき、それらが同型な群を表すかどうかを判定する。
それぞれについて、どの入力に対しても有限回の手順で正しい答えを出して止まる手続き（アルゴリズム）があるとき、その問題は解けるという。

2 つの語 $u,v$ が同じ元を表すことは $uv^{-1}$ が単位元を表すことと同値なので、語の問題は「語が $N(R)$ に属するか」の判定である。自由群では語を既約化して比べればよく、語の問題は解ける（自由群の注意「標準形と語の問題」）。一方、語の問題が解けない有限表示群が存在する（群の表示の注意「二つの異なる判定課題」。この記事では証明しない）。

部分群と構成

表示から部分群の表示を求めること、2 つの群を貼り合わせて新しい群を作ることも主な問いである。自由群の部分群は自由群であり（Nielsen–Schreierの定理）、2 つの群の自由積や、共通の部分群に沿った融合積（Van Kampenの定理の定義「群の融合積」）は、もとの群の表示を並べ、融合積では共通の部分群の像を同一視する関係式を加えることで表示できる。空間の基本群の表示は、空間を貼り合わせに分けて Van Kampenの定理で計算でき、組合せ群論の対象の多くは位相幾何から来る。

代表的な定理

定理	主張の要点	記事
自由群の標準形	自由群の元は既約語としてただ一通りに書ける	自由群
すべての群は表示をもつ	任意の群は自由群の剰余群	群の表示
Tietze の定理	同じ群の 2 つの有限表示は有限回の Tietze 変換で移り合う	群の表示
Nielsen–Schreier の定理	自由群の部分群は自由群で、指数 $k$ なら階数は $k(n-1)+1$	Nielsen–Schreierの定理
自由積の構成	自由積は簡約語の群として作れ、群の圏の余積である	自由積
Van Kampen の定理	貼り合わせた空間の基本群は融合積	Van Kampenの定理
剰余有限群は Hopf 的	有限生成の剰余有限群の全射な自己準同型は同型	この記事

代表例：自由群は Hopf 的である

有限な対象への写像で無限群を調べる方法は、組合せ群論の基本の手法の一つである。

剰余有限群と Hopf 的な群

群 $G$ が剰余有限（residually finite）であるとは、単位元でない任意の $g\in G$ に対し、有限群 $Q$ への群準同型 $\pi\colon G\to Q$ で $\pi(g)\ne1$ となるものが存在することをいう。
群 $G$ が Hopf 的（Hopfian）であるとは、全射な準同型 $G\to G$ がすべて単射であることをいう。

$G$ が Hopf 的でないことは、単位元以外を含む正規部分群 $N$ で $G/N\cong G$ となるものがあることと同値である（全射 $f\colon G\to G$ の核を $N$ とすれば準同型定理により $G/N\cong G$、逆に同型 $G/N\cong G$ と標準的な全射の合成は核 $N$ の全射である）。有限群は剰余有限であり（恒等写像をとる）、Hopf 的である（全射な自己写像は単射）。

自由群は剰余有限

任意の集合 $X$ について、自由群 $F(X)$ は剰余有限である。より詳しく、長さ $n\ge1$ の既約語 $w$ に対し、対称群 $S_{n+1}$ への準同型 $\pi$ で $\pi(w)\ne1$ となるものがある。

$w=a_1a_2\cdots a_n$（$a_i$ は文字）を既約語とし、集合 $\Omega:=\{0,1,\dots,n\}$ の置換を作る。各 $x\in X$ について、$\Omega$ の元の対応 $\sigma_x$ を次の指定で部分的に定める。

$a_i=x$ のとき、$\sigma_x(i):=i-1$。
$a_i=x^{-1}$ のとき、$\sigma_x(i-1):=i$。
この指定が矛盾せず単射な部分写像を与えることを確かめる。定義域の同じ点 $j$ に 2 つの値が指定されるのは、$a_j=x$（$j\mapsto j-1$）かつ $a_{j+1}=x^{-1}$（$j\mapsto j+1$）のときだけで、これは $a_ja_{j+1}=xx^{-1}$ となり $w$ の既約性に反する。同じ値 $j-1$ が 2 つの点から指定されるのは、$a_j=x$（$j\mapsto j-1$）かつ $a_{j-1}=x^{-1}$（$j-2\mapsto j-1$）のときだけで、$a_{j-1}a_j=x^{-1}x$ となりやはり既約性に反する。有限集合の上の単射な部分写像は全単射に延ばせる（定義域の補集合から値の補集合へ、両者は同じ個数なので全単射をとる）。延ばしたものも $\sigma_x$ と書く。$w$ に現れない $x$ には $\sigma_x:=\mathrm{id}$ とする。
自由群の普遍性により、$x\mapsto\sigma_x$ を延ばす準同型 $\pi\colon F(X)\to S_{n+1}$（$S_{n+1}$ は $\Omega$ の置換の群で、積は合成）がある。指定から、各 $i$ について $\pi(a_i)$ は $i$ を $i-1$ に写す（$a_i=x^{-1}$ なら $\sigma_x(i-1)=i$ より $\sigma_x^{-1}(i)=i-1$）。よって
$$ \pi(w)(n)=\pi(a_1)\circ\pi(a_2)\circ\cdots\circ\pi(a_n)(n)=0\ne n $$
であり、$\pi(w)\ne1$ である。$\square$

交換子を検出する置換

$F_2=F(\{a,b\})$ の交換子 $w=aba^{-1}b^{-1}$（$n=4$）で証明の構成を行う。指定は $\sigma_a(1)=0$、$\sigma_b(2)=1$、$\sigma_a(2)=3$、$\sigma_b(3)=4$ で、たとえば $\sigma_a=(0\ 1)(2\ 3)$、$\sigma_b=(1\ 2)(3\ 4)$ と延ばせる。$\pi(w)(4)$ を右から計算すると、$\sigma_b^{-1}(4)=3$、$\sigma_a^{-1}(3)=2$、$\sigma_b(2)=1$、$\sigma_a(1)=0$ であり、$\pi(w)\ne1$ となる。したがって $F_2$ で $ab\ne ba$ であることが、$S_5$ の 2 つの置換が可換でないことから確かめられる。

有限生成の剰余有限群は Hopf 的

有限生成の剰余有限群は Hopf 的である。

$G$ を有限集合 $S$ で生成される剰余有限群とし、$f\colon G\to G$ を全射な準同型とする。$f(g)=1$ かつ $g\ne1$ となる $g$ があると仮定して矛盾を導く。
剰余有限性により、有限群 $Q$ への準同型 $\pi$ で $\pi(g)\ne1$ となるものがある。$G$ から $Q$ への準同型全体の集合 $\mathrm{Hom}(G,Q)$ を考える。準同型は生成系 $S$ の像で決まるので、$\mathrm{Hom}(G,Q)$ は高々 $\lvert Q\rvert^{\lvert S\rvert}$ 個の元からなる有限集合である。写像
$$ f^*\colon\mathrm{Hom}(G,Q)\to\mathrm{Hom}(G,Q),\qquad\psi\mapsto\psi\circ f $$
は単射である。実際、$\psi\circ f=\psi'\circ f$ なら、$f$ が全射なのですべての元で $\psi=\psi'$ となる。有限集合からそれ自身への単射は全射なので、$\pi=\psi\circ f$ となる $\psi$ がある。すると $\pi(g)=\psi(f(g))=\psi(1)=1$ となり、$\pi(g)\ne1$ に反する。よって $f$ は単射である。$\square$

自由群を生成する元は基底

$X$ を $n$ 元の有限集合とする。$F(X)$ の $n$ 個の元 $g_1,\dots,g_n$ が $F(X)$ を生成するならば、$\{g_1,\dots,g_n\}$ は $F(X)$ の基底である。

$X=\{x_1,\dots,x_n\}$ とし、普遍性により $\theta(x_i)=g_i$ となる準同型 $\theta\colon F(X)\to F(X)$ をとる。$\theta$ の像は $g_1,\dots,g_n$ を含む部分群なので $F(X)$ 全体であり、$\theta$ は全射である。thm-cgt-free-rf と thm-cgt-rf-hopfian により $\theta$ は単射でもあり、同型である。
$\{g_i\}$ が基底であることを確かめる。群 $G$ と写像 $g_i\mapsto h_i\in G$ を与える。普遍性により $x_i\mapsto h_i$ となる準同型 $\varphi$ があり、$\varphi\circ\theta^{-1}$ は $g_i\mapsto h_i$ を満たす準同型である。$g_i$ は $F(X)$ を生成するので、このような準同型はただ一つである。また $g_i$ は相異なる（同じ元があれば $\theta$ は相異なる $x_i$ を同じ元に写し単射でない）。よって $F(X)$ は $\{g_1,\dots,g_n\}$ 上の自由群である。$\square$

基底の判定

$F_2=F(\{a,b\})$ で、組 $\{a,\ ab\}$ は $F_2$ を生成する（$b=a^{-1}\cdot ab$）ので、cor-cgt-generating-basis により基底である。組 $\{ab,\ ab^2\}$ も $b=(ab)^{-1}ab^2$、$a=ab\cdot b^{-1}$ から $F_2$ を生成し、基底である。一方、組 $\{a^2,\ b\}$ は $F_2$ を生成しない。$a\mapsto1$、$b\mapsto0$ で定まる準同型 $F_2\to\mathbb Z/2\mathbb Z$ が $a^2$ と $b$ をどちらも $0$ に写すので、それらが生成する部分群は核に含まれ、$a$ を含まないからである。
2 個より少ない元では $F_2$ は生成されない。$F_2$ が 1 元 $g$ で生成されれば $F_2$ は可換になるが、$ab\ne ba$ である（ex-cgt-commutator-permutation）。一般に、階数 $n$ の自由群は $n-1$ 個以下の元では生成されない。生成されたとすると、アーベル化 $F_n^{\mathrm{ab}}\cong\mathbb Z^n$（自由群の定理「自由群のアーベル化」）とさらに $2$ で割った $(\mathbb Z/2\mathbb Z)^n$ も $n-1$ 個以下の元で生成されるが、$\mathbb{F}_2$ 上の $n$ 次元ベクトル空間は $n-1$ 個以下の元では張られない。したがって cor-cgt-generating-basis は、元の個数が最小のときの生成系がいつも基底であることを述べている。

剰余有限性は、語の問題にも答えを与える。

剰余有限な有限表示群の語の問題

有限表示 $G=\langle X\mid R\rangle$ が剰余有限な群を表すならば、$G$ の語の問題は解ける。

語 $w$ が与えられたとき、次の 2 つの手続きを交互に 1 段ずつ進める。
(1) $N(R)$ は、$R$ の元とその逆元の共役 $grg^{-1}$（$g\in F(X)$）の有限個の積の全体に等しい（群の表示の定義の節）。このような積は語の長さと個数の順に番号を付けて 1 つずつ列挙できるので、それぞれを既約化して $w$ の既約化と比べる。一致すれば「$w$ は単位元を表す」と答えて止まる。
(2) $m=1,2,3,\dots$ の順に、集合 $\{1,\dots,m\}$ の上の乗積表で群の公理を満たすものを 1 つずつ列挙し（各 $m$ について有限個）、それぞれの有限群 $Q$ と写像 $X\to Q$（有限個）について、各関係子の $Q$ での値が単位元かを計算する。すべての関係子が単位元になれば、その写像は準同型 $G\to Q$ を定める（群の表示の命題「表示からの準同型」）。そのうえで $w$ の値が単位元でなければ「$w$ は単位元でない」と答えて止まる。
$w$ が $G$ の単位元を表すなら $w\in N(R)$ なので (1) がいずれ止まり、(2) はけっして止まらない（準同型は単位元を単位元に写す）。$w$ が単位元を表さないなら、(1) はけっして止まらない。一方、剰余有限性から有限群 $Q$ への準同型 $\pi$ で $\pi(w)\ne1$ となるものがあり、$Q$ は $m=\lvert Q\rvert$ のときに列挙される乗積表のどれかと同型なので、(2) がいずれ止まる。いずれの場合も、ちょうど一方が止まって正しい答えを返す。$\square$

反例：仮定を外すと崩れること

外す条件	反例	成り立たなくなること
有限生成である（thm-cgt-rf-hopfian）	可算無限集合 $\{x_0,x_1,\dots\}$ 上の自由群	Hopf 的であること
剰余有限である（thm-cgt-rf-hopfian）	$\langle a,b\mid a^{-1}b^2a=b^3\rangle$	Hopf 的であること
剰余有限である（prop-cgt-rf-word-problem）	語の問題が解けない有限表示群	語の問題が解けること

1 行目：この自由群は thm-cgt-free-rf により剰余有限である。$x_0\mapsto1$、$x_{i}\mapsto x_{i-1}$（$i\ge1$）で定まる準同型は全射で（各 $x_i$ は $x_{i+1}$ の像）、$x_0\ne1$ を $1$ に写すので単射でない。
2 行目：この群は 2 元で生成されるが Hopf 的でない。これは Baumslag と Solitar の定理で、BS62 Theorem 1 の (c)（p. 200）に証明の概略がある。この記事では証明しない。thm-cgt-rf-hopfian の対偶により、この群は剰余有限でない。
3 行目：そのような群の存在は群の表示の注意「二つの異なる判定課題」にある（この記事では証明しない）。prop-cgt-rf-word-problem の対偶により、そのような群は剰余有限でない。

学ぶ順の道筋

組合せ群論の基礎は、次の順に記事をたどると学べる。

群の基礎：群 → 部分群 → 正規部分群・剰余群 → 準同型定理。全体像は群論にある。
自由群と表示：自由群（既約語・普遍性・階数）→ 群の表示（Tietze 変換・語の問題）→ アーベル化・交換子部分群。
部分群：剰余類・部分群の指数 → Nielsen–Schreierの定理。
構成：自由積 → Van Kampenの定理（融合積）。
位相幾何との往復：基本群 → 被覆空間 → Cayleyグラフ。具体的な群としてブレイド群・二面体群・モジュラー群がある。
その先：群を距離空間として調べる幾何学的群論。
2 と 3 は、自由群の既約語の一意性だけを道具にして進められる。この記事の代表例も、自由群の普遍性と既約語だけで証明できる。

歴史

20 世紀の初めに Dehn が、曲面や結び目の基本群の研究の中で語の問題・共役問題・同型問題を提起し、表示から群を調べる方法が分野として形をとった。続いて Nielsen と Schreier が自由群の部分群を調べ、Schreier の方法による部分群の表示の計算は、その後の組合せ群論の基本の道具になった。20 世紀半ばには、語の問題が一般には解けないことが示され、表示から何が計算できて何ができないかが分野の中心的な問いの一つになった。