Higmanの埋め込み定理

同義語:ヒグマンの埋め込み定理Higman embedding theoremHigman's embedding theorem

概要

Higmanの埋め込み定理(Higman embedding theorem)とは、有限生成の群が有限表示群の部分群と同型になるのは、その群が帰納的に表示されるとき、すなわち有限個の生成元と帰納的可算な関係子の集合による表示をもつときであり、そのときに限るという定理である。必要性は、有限表示群で単位元を表す語が機械的に列挙できることから従う。HNN拡大の構成で可算群を2元で生成される群に埋め込むと、帰納的に表示される可算群も有限表示群に埋め込める。帰結として、すべての有限表示群を部分群に含む有限表示群と、語の問題が解けない有限表示群が存在する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 群の表示, HNN拡大, 帰納的可算集合

Higman の埋め込み定理(Higman embedding theorem)は、有限生成の群が有限表示群の部分群として実現できるのは、その群の関係が機械的に数え上げられるときであり、そのときに限る、という定理である。G. Higman が 1961 年に証明したHig61。有限個の生成元と関係式で書ける群の部分群という群論の性質が、関係の集合が帰納的可算であるという計算可能性の性質とちょうど一致する。群の言葉で計算を書き表せることを示す代表的な結果である。
この記事では、主定理の易しい方向と、有限生成でない群に主定理を使うための Higman–Neumann–Neumann の埋め込み(可算群は 2 元で生成される群に埋め込める)を完全に証明する。主定理の難しい方向は証明しないが、それを使って、すべての有限表示群を部分群に含む有限表示群と、語の問題が解けない有限表示群の存在を導く。名前の似た Higmanの補題 は、語の部分列の順序についての別の定理である。

帰納的に表示される群

群の表示 $\langle X\mid R\rangle=F(X)/N(R)$ の記法は 群の表示 に従う。$F(X)$ は $X$ 上の自由群、$N(R)$ は $R$ の正規閉包である。語は 語の問題(群論) の定義のとおり自然数で番号付けし、語の集合が帰納的可算であるとは、番号の集合がそうであることをいう。生成元が可算無限個 $x_0,x_1,\dots$ のときも、文字 $x_i^{\pm1}$ を $(i,\pm1)$ の番号で書いて同じように番号付けする。

帰納的な表示

群の表示 $\langle X\mid R\rangle$ で、$X$ が有限集合または $\{x_0,x_1,\dots\}$ であり、関係子の集合 $R$ が帰納的可算であるものを 帰納的な表示(recursive presentation)という。帰納的な表示をもつ群を 帰納的に表示される群 という。

$R$ が帰納的可算で $r_0,r_1,\dots$ と列挙されるなら、$r_k$ を語 $r_k(x_0x_0^{-1})^k$ に替えた集合は同じ正規閉包をもち、語の長さを見れば所属を判定できる。この意味で、帰納的可算を決定可能に替えても同じ群の族になる。名前の「帰納的」はこれによる。
有限生成の群については、この性質を語の問題の言葉で言い換えられる。$S$ を群 $G$ の有限な生成系とし、$S$ 上の語のうち $G$ で単位元を表すものの集合を $W(G,S)$ と書く(語の問題(群論) の定義「語の問題」)。

単位元を表す語の集合

$G$ を有限生成の群、$S$ をその有限な生成系とする。$G$ が帰納的に表示されることと、$W(G,S)$ が帰納的可算であることは同値である。特に、帰納的に表示されるかは有限な生成系の選び方によらない。

正規閉包を数え上げる

$W(G,S)$ が帰納的可算なら、$\langle S\mid W(G,S)\rangle$ が $G$ の帰納的な表示である。実際、自然な全射 $F(S)\to G$ の核は、$W(G,S)$ の語が表す $F(S)$ の元の全体であり、これは核自身なので正規閉包をとっても変わらない。
逆に $G=\langle X\mid R\rangle$ を帰納的な表示とする。$R$ の列挙と並行して、すでに列挙した $r\in R$ とその逆の共役の有限個の積 $u_1r_1^{\pm1}u_1^{-1}\cdots u_kr_k^{\pm1}u_k^{-1}$ を 1 つずつ列挙できる(各段で、列挙済みの関係子と長さの上限を 1 つずつ増やす)。語の問題(群論) の命題「有限表示群の単位元を表す語」の証明と同じく、語 $w$ の既約化がそのどれかの既約化と一致するまで探せば、$w\in N(R)$ のときちょうど止まる(自由群 の定理「既約語の群」)。よって $X$ 上の語で単位元を表すものの集合は帰納的可算である。
$X$ が有限でなくても、$G$ は有限な $S$ で生成されるので、各 $s\in S$ の像を表す $X$ 上の語 $v_s$ を 1 つずつ固定できる。$S$ 上の語 $w$ の文字 $s^{\pm1}$ を $v_s^{\pm1}$ に置き換えた語を $\tau(w)$ とすると、$w$ と $\tau(w)$ は $G$ の同じ元を表す。$S$ は有限なので $\tau$ は計算でき、$w\in W(G,S)\iff\tau(w)\in N(R)$ である。右辺が半決定可能なので、$W(G,S)$ は帰納的可算である。$\square$

有理数の加法群

有限表示群は帰納的に表示される。有限生成でない例として、
$$ Q:=\langle x_1,x_2,\dots\mid x_ix_jx_i^{-1}x_j^{-1}\ (i,j\ge1),\ \ x_n^{\,n}x_{n-1}^{-1}\ (n\ge2)\rangle $$
を考える。関係子の集合は決定可能である。$x_n\mapsto1/n!$ は関係を保つので準同型 $Q\to(\mathbb Q,+)$ を定め、$1/N!$ たちが $\mathbb Q$ を生成するので全射である。$Q$ は可換で、$n\le N$ なら $x_n=x_N^{N!/n!}$ だから、$Q$ の元は $x_N^{c}$($c\in\mathbb Z$)と書ける。これが $0$ に写れば $c/N!=0$ で $c=0$ である。よって $Q\cong\mathbb Q$ であり、thm-he-hnn と主定理を合わせると、$\mathbb Q$ も有限表示群に埋め込める。

主定理

Higman の埋め込み定理

有限生成の群 $G$ について、次は同値である。

  1. ある有限表示群 $H$ と単射準同型 $G\to H$ がある。
  2. $G$ は帰納的に表示される。
証明の分担

この形の主張は Mik23 の Theorem 1.1 による(そこでは Higman の原論文の Theorem 1 として引かれている)。1 ⇒ 2 は次の命題で証明する。2 ⇒ 1 はこの記事では証明しない。証明の筋道は後の節「難しい方向の証明の筋道」で述べる。

有限表示群の有限生成部分群

有限表示群 $H$ の有限生成部分群は、帰納的に表示される。

語を置き換えて半決定に帰着する

$H=\langle Y\mid Q\rangle$ を $Y$、$Q$ がともに有限な表示とし、$G\le H$ を有限な生成系 $S$ で生成される部分群とする。各 $s\in S$ について、$H$ で $s$ を表す $Y$ 上の語 $v_s$ を固定し、$S$ 上の語 $w$ の文字 $s^{\pm1}$ を $v_s^{\pm1}$ に置き換えた語を $\tau(w)$ とする。$w$ が $G$ で表す元と $\tau(w)$ が $H$ で表す元は同じなので、
$$ w\in W(G,S)\iff\tau(w)\in W(H,Y) $$
である。$W(H,Y)$ は 語の問題(群論) の命題「有限表示群の単位元を表す語」により半決定可能で、$\tau$ は計算できるので、$W(G,S)$ は帰納的可算である。lem-he-wordset により $G$ は帰納的に表示される。単射準同型 $G\to H$ があれば $G$ はその像と同型なので、主定理の 1 ⇒ 2 が従う。$\square$

可算群を 2 元で生成される群に埋め込む

主定理は有限生成の群についての定理だが、任意の可算群を 2 元で生成される群に埋め込めば、有限生成でない群にも使える。これは Higman、B. H. Neumann、H. Neumann によるHNN49(CV18 §1 の引用による)。この節では、帰納的な表示が保たれることまで含めて証明する。以下、自由群 $F(a,b)$ の元
$$ u_i:=a^{-i}ba^{i}\qquad(i\ge0) $$
を使う。$u_0=b$ である。

共役の族は自由基底

$\{u_i\}_{i\ge0}$ は、それが生成する $F(a,b)$ の部分群の自由基底である。さらに、$S\subseteq\mathbb N$ と $n\in\mathbb N$ について、$u_n\in\langle u_i\mid i\in S\rangle$ となるのは $n\in S$ のときに限る。

既約語の形を読む

$u_i^{\pm1}$ の積で、隣り合う $u_i^{\varepsilon}u_i^{-\varepsilon}$ を含まないものをとる。同じ添字が続くところをまとめると、
$$ w=u_{j_1}^{m_1}u_{j_2}^{m_2}\cdots u_{j_r}^{m_r}\qquad(r\ge1,\ m_l\ne0,\ j_l\ne j_{l+1}) $$
の形になる。$u_j^{m}=a^{-j}b^{m}a^{j}$ なので、$F(a,b)$ では
$$ w=a^{-j_1}\,b^{m_1}\,a^{j_1-j_2}\,b^{m_2}\,a^{j_2-j_3}\cdots a^{j_{r-1}-j_r}\,b^{m_r}\,a^{j_r} $$
である。$b$ の指数 $m_l$ も、間の $a$ の指数 $j_l-j_{l+1}$ もすべて $0$ でないので、右辺は既約語であり(両端の $a^{-j_1}$、$a^{j_r}$ は $0$ 乗なら省く)、$r\ge1$ だから空でない。自由群 の定理「既約語の群」から $w\ne e$ で、$\{u_i\}$ は自由基底である。
後半について、$u_n\in\langle u_i\mid i\in S\rangle$ とすると、$u_n$ は上の形の $w$ で、すべての $j_l$ が $S$ に属するもので書ける。$u_n$ の既約語は $a^{-n}ba^{n}$ で、$b$ を 1 回だけ含む。既約語は一意なので、$w$ の既約語と比べて $r=1$、$m_1=1$、$a^{-j_1}=a^{-n}$ となり、$n=j_1\in S$ である。逆は明らかである。$\square$

$a$ と $b$ を入れ替える $F(a,b)$ の自己同型で写すと、$v_i:=b^{-i}ab^{i}$($i\ge0$)についても同じことが成り立つ。

Higman–Neumann–Neumann の埋め込み

可算群 $G$ は、2 元で生成されるある群 $K$ の部分群と同型である。さらに、$G$ が帰納的な表示 $\langle g_1,g_2,\dots\mid R\rangle$ をもつなら、$K$ として、2 つの生成元 $a,t$ をもつ帰納的な表示の群をとれる。

HNN 拡大で生成元を 2 つに減らす

$G$ を生成する元の列 $g_1,g_2,\dots$ をとる($G$ の元を全部並べてもよい。有限個しかなければ単位元を繰り返す。帰納的な表示の生成元が有限個なら、生成元 $g_j$ と関係子 $g_j$ を足して無限個にする)。$g_0:=e$ とおく。自由積 $H:=G\ast F(a,b)$ の中で、
$$ v_i:=b^{-i}ab^{i},\qquad y_i:=g_i\,u_i=g_i\,a^{-i}ba^{i}\qquad(i\ge0) $$
とし、$A:=\langle v_i\mid i\ge0\rangle$、$B:=\langle y_i\mid i\ge0\rangle$ とおく。
$A$、$B$ は $\{v_i\}$、$\{y_i\}$ を基底とする自由群である。 $A$ については lem-he-free の後の注意による。$B$ については、$G$ を潰して $F(a,b)$ を動かさない準同型 $\pi\colon H\to F(a,b)$(自由積 の命題「自由積は群の圏の余積」)を使う。記号 $z_0,z_1,\dots$ 上の自由群から $H$ への準同型 $\beta\colon z_i\mapsto y_i$ を考えると、$\pi\circ\beta$ は $z_i\mapsto u_i$ で、lem-he-free により単射である。よって $\beta$ も単射であり、$B$ は $\{y_i\}$ を基底とする自由群である。したがって $\varphi(v_i):=y_i$ は同型 $\varphi\colon A\to B$ を定める。
HNN 拡大をとる。 $K:=H\ast_\varphi$ とし、安定文字を $t$ とする。HNN拡大 の系「底群の埋め込み」と、自由積が因子を含むことから、$G\to H\to K$ は単射である。$K$ では $tv_it^{-1}=y_i$ なので、$i=0$ から $tat^{-1}=b$、$i\ge1$ から
$$ g_i=t\,v_i\,t^{-1}\,u_i^{-1}=t\,b^{-i}ab^{i}\,t^{-1}\,a^{-i}b^{-1}a^{i} $$
が成り立つ。$H$ は $G$ と $a,b$ で生成されるので、$K$ は $a,t$ で生成される。
帰納的な表示。 $G=\langle g_1,g_2,\dots\mid R\rangle$ とすると、自由積 の系「群の表示による自由積の記述」と HNN拡大 の定義の後の注意(結合部分群の生成系で関係を書けばよい)により
$$ K=\langle g_1,g_2,\dots,a,b,t\mid R,\ \ t\,v_i\,t^{-1}=g_i\,u_i\ (i\ge0)\rangle $$
である。$F(a,t)$ の元を $\bar b:=tat^{-1}$、$\gamma_0:=e$、$\gamma_i:=t\,\bar b^{-i}a\bar b^{i}\,t^{-1}\,a^{-i}\bar b^{-1}a^{i}$($i\ge1$)で定め、$R$ の語の $g_i$ に $\gamma_i$ を代入した語の集合を $R'$ とする。代入は計算できるので $R'$ は帰納的可算である。$L:=\langle a,t\mid R'\rangle$ とおく。
$g_i\mapsto\gamma_i$、$a\mapsto a$、$b\mapsto\bar b$、$t\mapsto t$ は $K$ の関係を保つ。$R$ の語は $R'$ の語に写り、$tv_it^{-1}=g_iu_i$ は $F(a,t)$ の中で $t\,\bar b^{-i}a\bar b^{i}\,t^{-1}=\gamma_i\,a^{-i}\bar ba^{i}$ に写るが、これは $\gamma_i$ の定義そのものである($i=0$ では $tat^{-1}=\bar b$)。よって準同型 $\psi\colon K\to L$ が定まる(群の表示 の命題「表示からの準同型」)。逆に $a\mapsto a$、$t\mapsto t$ は、$K$ で $\gamma_i=g_i$ なので $R'$ の語を単位元に写し、準同型 $\chi\colon L\to K$ を定める。$\psi\chi$ は生成元 $a,t$ を、$\chi\psi$ は生成元 $g_i,a,b,t$ をそれぞれ動かさないので、$K\cong L$ である。$\square$

主定理から導かれること

主定理の 2 ⇒ 1 を認めると、次の 2 つが従う。どちらも主定理と thm-he-hnn を組み合わせるだけで証明できる。

普遍的な有限表示群

有限表示群 $U$ で、すべての有限表示群を部分群として含むものが存在する。$U$ は、帰納的に表示される有限生成の群もすべて部分群として含む。

有限表示を全部並べる

記号 $x_1,x_2,\dots$ の上の有限表示 $\langle x_1,\dots,x_m\mid r_1,\dots,r_k\rangle$ を機械的に $P_1,P_2,\dots$ と列挙し、$P_n$ の表す群を $G_n$ とする。$P_n$ の記号 $x_j$ を $x_{n,j}$ に付け替えて全部並べた表示は、生成元が可算個で関係子の集合が帰納的可算(実は決定可能)であり、自由積 の系「群の表示による自由積の記述」により自由積 $G:=\ast_nG_n$ を表す。各 $G_n$ は $G$ の部分群である。thm-he-hnn により $G$ は 2 元で生成される帰納的に表示される群に埋め込まれ、主定理によりそれはある有限表示群 $U$ に埋め込まれる。有限表示群は $G_n$ のどれかと同型なので $U$ に含まれる。帰納的に表示される有限生成の群は主定理によりある有限表示群に埋め込まれるので、やはり $U$ に含まれる。$\square$

次の系は 語の問題(群論) の定理「Novikov–Boone の定理」と同じ結論である。$S\subseteq\mathbb N$ について、群
$$ G_S:=\langle a,b,t\mid t\,u_i\,t^{-1}=u_i\ (i\in S)\rangle $$
を考える。これは $F(a,b)$ の、$C_S:=\langle u_i\mid i\in S\rangle$ の恒等写像による HNN 拡大である(HNN拡大 の定義の後の注意)。

集合を読み出す関係

$G_S$ で $t\,u_n\,t^{-1}=u_n$ となるのは $n\in S$ のときに限る。

Britton の補題を使う

$n\in S$ なら定義の関係である。$n\notin S$ とすると、lem-he-free により $u_n\notin C_S$ である。語 $t\,u_n\,t^{-1}u_n^{-1}$ は安定文字を 2 つ含み、その間の $u_n$ が結合部分群 $C_S$ に属さないので、挟み込みをもたない。HNN拡大 の系「Britton の補題」により、この語は $G_S$ で単位元でない。$\square$

語の問題が解けない有限表示群

語の問題が解けない有限表示群が存在する。

自己停止集合を群に書き込む

$K:=\{e\mid\varphi_e(e)\!\downarrow\}$ を自己停止集合とする(帰納的可算集合 の例「帰納的可算集合の例」)。$K$ は帰納的可算なので、$G_K$ の関係子の集合 $\{t u_it^{-1}u_i^{-1}\mid i\in K\}$ も帰納的可算で、$G_K$ は帰納的に表示される。主定理により $G_K$ はある有限表示群 $H$ に埋め込まれる。$H$ の語の問題が解けるとすると、語の問題(群論) の命題「有限生成部分群」により $G_K$ の語の問題も解ける。すると lem-he-gs により、$n$ に対して語 $tu_nt^{-1}u_n^{-1}$ を作って判定すれば $n\in K$ が決定できる。これは $K$ が決定可能でないことに反する。$\square$

難しい方向の証明の筋道

2 ⇒ 1 の証明はこの記事では行わない。Higman の原論文の流れは、Mik23 §1.1 によれば次のとおりである。

  1. 帰納的可算集合の代数的な特徴づけ。 有限個を除いて $0$ をとる整数値の関数 $f\colon\mathbb Z\to\mathbb Z$ の集合を考え、その部分集合が帰納的可算であることを、2 つの初期集合からいくつかの集合演算を有限回施して得られることとして特徴づける。
  2. 良性部分群。 有限生成の群 $G$ の部分群 $C$ が 良性(benign)であるとは、$G$ がある有限表示群 $M$ に埋め込まれ、$M$ のある有限生成部分群 $L$ について $G\cap L=C$ となることをいう(Mik23 Definition 3.1)。有限表示群の有限生成部分群は良性である。関数の集合 $\mathcal B$ に階数 3 の自由群の部分群 $A_{\mathcal B}$ を対応させ、$\mathcal B$ が帰納的可算であることと $A_{\mathcal B}$ が良性であることが同値であることを、1 の演算ごとに融合積と HNN 拡大を組み立てて示す。これが証明の中心である。
  3. 埋め込み。 有限生成の自由群の部分群は、帰納的可算であるとき、またそのときに限り良性であることを導き、最後に帰納的に表示される群を有限表示群に埋め込む。この段は Higman のロープの技法(rope trick)と呼ばれることがある。
    融合積と HNN 拡大だけで計算を模倣することが要点である。Mik23 はこの方針を保ったまま 2 の段を短くした証明を与えている。ほかに、Matiyasevich の定理(帰納的可算集合は Diophantus 的)を使う Valiev の方針による証明や、Turing 機械を半群と群の語の問題に書き写す Aanderaa の方針による証明が教科書にある(同 §1.3)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
関係子の集合が帰納的可算$G_{\mathbb N\setminus K}$主定理の 1(有限表示群への埋め込み)
群が可算実数の加法群 $(\mathbb R,+)$thm-he-hnn の結論(2 元で生成される群への埋め込み)
埋め込み先が有限表示(必要性の方向)$G_{\mathbb N\setminus K}$ を 2 元で生成される群に埋め込むprop-he-necessity(部分群は帰納的に表示される)
$u_i$ が自由基底$u_i$ を $b^{i}$ に替え、$S=\{2,3\}$、$n=5$lem-he-free の後半
反例の確かめ

帰納的可算。 $G_{\mathbb N\setminus K}$ は 3 元で生成される可算群である。有限表示群に埋め込めたとすると、prop-he-necessity と lem-he-wordset により $W(G_{\mathbb N\setminus K},\{a,b,t\})$ は帰納的可算で、lem-he-gs により $\mathbb N\setminus K=\{n\mid tu_nt^{-1}u_n^{-1}\in W\}$ も帰納的可算になる。これは 帰納的可算集合 の系「補集合が帰納的可算でない集合」に反する。関係子の集合 $\{tu_it^{-1}u_i^{-1}\mid i\notin K\}$ は帰納的可算でなく、別の帰納的な表示もない。
可算。 有限表示群は可算個の語の類からなるので可算であり、その部分群も可算である。非可算な $\mathbb R$ はどの有限表示群にも、どの有限生成の群にも埋め込めない。
埋め込み先が有限表示。 thm-he-hnn の前半により $G_{\mathbb N\setminus K}$ は 2 元で生成される群 $K'$ に埋め込める。$K'$ は有限生成だが、その有限生成部分群 $G_{\mathbb N\setminus K}$ は、上で見たとおり帰納的に表示されない。prop-he-necessity で $H$ を有限生成の群に弱めると成り立たない。
自由基底。 $\langle b^2,b^3\rangle$ は $b=b^3b^{-2}$ を含むので $b^5$ を含むが、$5\notin\{2,3\}$ である。$b^i$ は自由基底でなく($b^2$ と $b^3$ は可換)、prf-he-free の既約語の比較が使えない。

関連項目

参考文献

[1]
G. Higman, Subgroups of finitely presented groups, Proceedings of the Royal Society of London. Series A, 1961, pp. 455–475
[2]
Graham Higman, B. H. Neumann, Hanna Neumann, Embedding theorems for groups, Journal of the London Mathematical Society, 1949, pp. 247–254
[3]
V. H. Mikaelian, A modified proof for Higman's embedding theorem, arXiv:1908.10153, 2023, §1.1、§1.3、Theorem 1.1、Definition 3.1。arXiv:1908.10153v8
[4]
Maurice Chiodo, Rishi Vyas, Torsion, torsion length and finitely presented groups, Journal of Group Theory, 2018, pp. 949–971。§1

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する