Grigorchuk群(Grigorchuk group)とは、根付きの無限二分木に作用する 4 つの位数 $2$ の自己同型 $a,b,c,d$ が、木の上の簡単な再帰で生成する群である。有限生成の無限群ですべての元の位数が $2$ の冪であり、一般の Burnside 問題の反例になる。増大関数が多項式より速く指数関数より遅い中間増大をもつ最初の例であり、従順であるが初等従順ではない。
Grigorchuk群(Grigorchuk group)は、根付きの無限二分木の自己同型 $a,b,c,d$ で生成される群 $G$ である。R. Grigorchuk が 1980 年代に構成した(GP06 p. 1。年は同 p. 16 の文献 [3](1980 年)・[4](1983 年)による)。4 つの生成元はどれも位数 $2$ で、定義は木の上の簡単な再帰で書けるが、群としては次の性質をあわせもつ。
| 結果 | 内容 | この記事での扱い |
|---|---|---|
| prop-gg-klein | 生成元の関係 | 証明する |
| lem-gg-psi | 自己相似性と書き換え規則 | 証明する |
| thm-gg-infinite | $G$ は無限群 | 証明する |
| thm-gg-torsion | $G$ の元の位数は $2$ の冪 | 証明する |
| prop-gg-commensurable | $G$ と $G\times G$ は通約的 | 証明する |
| thm-gg-growth | 中間増大 | 多項式でないことは証明、評価は主張と所在 |
| thm-gg-amenable | 従順で、初等従順でない | 上の評価を使って証明 |
0 と 1 からなる有限列の全体を $T$ とし、空列を根、列 $v$ の子を $v0,v1$ とする根付きの二分木とみる。$\lvert v\rvert$ を列の長さ(段)とする。$T$ の自己同型は、根を固定し、各段を保ち、子の関係を保つ全単射 $T\to T$ である。積は合成 $(gh)(v)=g(h(v))$ とする。
$T$ の写像 $a,b,c,d$ を、列 $u$ に対して次の式で列の長さについて再帰的に定める(空列は固定する)。
$$
\begin{aligned}
a(0u)&=1u, & a(1u)&=0u,\\
b(0u)&=0\,a(u), & b(1u)&=1\,c(u),\\
c(0u)&=0\,a(u), & c(1u)&=1\,d(u),\\
d(0u)&=0u, & d(1u)&=1\,b(u).
\end{aligned}
$$
これらが生成する $T$ の自己同型群 $G=\langle a,b,c,d\rangle$ を Grigorchuk群 という。
列の長さについての帰納法で、4 つの写像は長さを保ち、各段の上で全単射で、列の接頭辞の関係を保つので、$T$ の自己同型である。$a$ は最初の文字を入れ替え、$b,c,d$ は最初の文字を変えずに、残りに $a,c,d$ などを作用させる。$b,c,d$ は「右の枝 $1,11,111,\dots$ に沿って進み、そこから左に出た部分木に $a$ を作用させるかどうか」で区別される。$b$ は $1^k$ の左の部分木に、$k\equiv0,1\pmod3$ のとき $a$ を作用させ、$c$ は $k\equiv0,2$、$d$ は $k\equiv1,2$ のとき作用させる(GP06 p. 6 の式 $(*)$)。
$a^2=b^2=c^2=d^2=1$ であり、$b,c,d$ は互いに可換で $bc=d$、$cd=b$、$db=c$ を満たす。とくに $\{1,b,c,d\}$ は Klein四元群 と同型で、$G=\langle a,b,c\rangle$ である。
$a^2=1$ は定義から明らかである。$b^2,c^2,d^2$ と $bc,cd,db$ について、列の長さについての帰納法で示す。最初の文字が $0$ の列では $b,c$ は残りに $a$、$d$ は恒等写像を作用させるので、$b^2(0u)=0a^2(u)=0u$、$bc(0u)=0a^2(u)=0u=d(0u)$ などとなる。最初の文字が $1$ の列では、$b,c,d$ は残りにそれぞれ $c,d,b$ を作用させるので、$b^2(1u)=1c^2(u)$、$bc(1u)=1cd(u)$、$cd(1u)=1db(u)$、$db(1u)=1bc(u)$ となり、帰納法の仮定(短い列 $u$ での等式)から $1u$、$1b(u)$、$1c(u)$、$1d(u)$ に等しい。可換性は $cb=c^{-1}b^{-1}=(bc)^{-1}=d^{-1}=d=bc$ などから従う。$b(00)=c(00)=01$、$d(100)=101$ なので $b,c,d$ はどれも恒等写像でなく、$bc=d\ne1$ などから互いに異なる。$\square$
$S=\{a,b,c,d\}$ についての語の長さを $\ell(g)$ と書く。$g$ を長さ $\ell(g)$ の語で書くと、$aa$ も、$b,c,d$ の 2 文字の並びも、prop-gg-klein でより短く書き直せるので現れない。したがって最短の語は $a$ と $b,c,d$ の文字が交互に並ぶ。
最初の段 $\{0,1\}$ の各点を固定する $G$ の元の全体を $H$ とする。$b,c,d\in H$、$a\notin H$ で、$G$ の元は $H$ に入るか $aH$ に入るので、$H$ は指数 $2$ の正規部分群である。語 $w$ が表す元が $H$ に入ることは、$w$ の中の $a$ の個数が偶数であることと同値である。
$g\in H$ は、ある $g_0,g_1$ について $g(0u)=0\,g_0(u)$、$g(1u)=1\,g_1(u)$ と書ける。$\psi(g):=(g_0,g_1)$ とおく。$\psi(gh)=(g_0h_0,g_1h_1)$ なので $\psi$ は準同型で、$g$ は $g_0,g_1$ で決まるので単射である。
$\psi(H)$ の各成分への射影は全射である。1 の 6 つの元の第 0 成分 $a,a,1,c,d,b$ も、第 1 成分 $c,d,b,a,a,1$ も $G$ を生成するからである。これは GP06 Lemma 5.3(p. 8)であり、各頂点 $v$ を固定する元を $v$ 以下の部分木に制限した群が $G$ 自身になること(自己相似性、同 Corollary 5.5, p. 8)が段についての帰納法で従う。
$G$ は無限群である。
$G$ が有限だとする。$H$ は指数 $2$ なので $\lvert H\rvert<\lvert G\rvert$ である。一方、$\psi$ の第 0 成分への射影 $H\to G$ は全射なので $\lvert H\rvert\ge\lvert G\rvert$ である。これは矛盾である。$\square$
これは GP06 Corollary 5.4(p. 8)である。
$G$ のすべての元の位数は有限で、$2$ の冪である。
「長さ $\ell(g)\le n$ の元の位数は $2$ の冪」を $n$ についての帰納法で示す。$n\le1$ では prop-gg-klein による。$\ell(g)=n\ge2$ とし、短い元については正しいとする。共役は位数を変えないことを繰り返し使う。また $g\in H$ で $\psi(g)=(g_0,g_1)$ なら、$\psi$ は単射準同型なので $g$ の位数は $g_0,g_1$ の位数の最小公倍数であり、$g\notin H$ なら $g^2\in H$ で、$g^2$ の位数が $2^k$ なら $g$ の位数は $2^{k+1}$ を割る。
最短の語 $w$ は交互に並ぶ。両端が同じ種類の文字なら、$w=ava$ のとき $aga$ は長さ $n-2$ 以下、$w=xvy$($x,y\in\{b,c,d\}$)のとき $xgx=v(yx)$ は長さ $n-1$ 以下の元で、$g$ と共役である。両端が異なる種類なら $n=2m$ は偶数で、必要なら最初の文字で共役をとって $w=ax_1ax_2\cdots ax_m$ としてよい。
$m$ が偶数のとき. $g\in H$ で、lem-gg-psi の 3 により $\ell(g_0),\ell(g_1)\le m< n$ なので、帰納法の仮定が使える。
$m$ が奇数で、$x_i$ に $d$ があるとき. $g^2$ の成分の長さは $2m-k_d< n$ なので、帰納法の仮定から $g^2$ の位数は $2$ の冪である。
$m$ が奇数で、$x_i$ は $b,c$ だけで、$c$ を含むとき. $g^2$ の成分の語を $u$ とする。$x_i^{(0)}=a$、$x_i^{(1)}\in\{c,d\}$ で、lem-gg-psi の 3 の証明のとおり $u$ は各 $x_i$ から $a$ と $x_i^{(1)}$ を 1 文字ずつ受け取る。並べ方を追うと $u$ は $a$ と $\{c,d\}$ の文字が交互に並ぶ長さ $2m$ の語で、$a$ を $m$ 個(奇数個)含み、$x_i=c$ から来る文字 $d$ を含む。そこで $u^2$ の成分の語の長さは $2m-(u\text{ の }d\text{ の個数})< n$ であり、帰納法の仮定から $u^2$ の位数、したがって $u$ の位数は $2$ の冪である。2 つの成分について同じなので、$g^2$ の位数は $2$ の冪である。
$x_i$ がすべて $b$ のとき. $g=(ab)^m$ である。lem-gg-psi の 2 から $\psi((ad)^2)=(b,b)$、$\psi((ac)^2)=(da,ad)$、$\psi((ab)^2)=(ca,ac)$ で、$da=(ad)^{-1}$、$ca=(ac)^{-1}$ である。よって $(ad)^4=1$、$(ac)^8=1$、$(ab)^{16}=1$ となり、$g$ の位数は $16$ を割る。$\square$
最後の場合の計算から $(ad)^4=(ac)^8=(ab)^{16}=1$ が得られる(GP06 Exercise 4.4, p. 7)。さらに $\psi((ad)^2)=(b,b)\ne1$、$\psi((ac)^4)=((da)^2,(ad)^2)\ne1$、$\psi((ab)^8)=((ca)^4,(ac)^4)\ne1$ なので、$ad,ac,ab$ の位数はちょうど $4,8,16$ である。thm-gg-torsion は GP06 Exercise 7.5(p. 12)である。
有限生成群の増大関数 $\beta_S(r)=\lvert B_S(r)\rvert$ とその同値は 幾何学的群論 の定義「増大関数」による。$G$ では $S=\{a,b,c,d\}$ をとる。
$\psi(H)$ は $G\times G$ の指数 $64$ 以下の部分群である。したがって $G$ と $G\times G$ は、互いに同型な指数有限の部分群 $H\cong\psi(H)$ をもつ。
$b$ の $G$ での正規閉包を $N$ とする。$G/N$ は $a,d$ の像で生成され($c=bd$)、$a^2=d^2=(ad)^4=1$ を満たすので、位数 $8$ の二面体群の商であり、$[G:N]\le8$ である。$x\in H$、$\psi(x)=(x_0,x_1)$ とすると $\psi(x^{-1}dx)=(1,\ x_1^{-1}bx_1)$ で、$x_1$ は $G$ のすべての元を動くので、$\psi(H)\supset1\times N$ である。$ada$ を使えば同様に $N\times1\subset\psi(H)$ である。よって $[G\times G:\psi(H)]\le[G\times G:N\times N]=[G:N]^2\le64$ である。$\square$
これは GP06 Proposition 6.1・Lemmas 6.2・6.3(p. 9)である。増大関数の言葉では、$\beta$ と $\beta^2$ が同値になる(幾何学的群論 の命題「指数有限の部分群は準等長」と定理「増大度の準等長不変性」による)。
$\lim\beta_S(n)^{1/n}$ が $1$ より大きいことが指数関数的な増大であり、多項式で抑えられることが多項式増大である。thm-gg-growth はそのどちらでもない増大が実際に起こることを示す。
1 の論法(増大が指数関数的でなければ球が Følner 集合をなす)は一般の有限生成群で通る(DK17 Proposition 18.6, p. 573)。
$G$ は、一般の群について期待されがちな次の主張の反例になる。
| 主張 | $G$ で成り立たない理由 |
|---|---|
| 有限生成の周期群は有限である(一般の Burnside問題) | thm-gg-infinite・thm-gg-torsion |
| 有限生成群の増大は多項式か指数関数である | thm-gg-growth |
| 従順群は初等従順である | thm-gg-amenable |
| 有限生成群は仮想可解か $F_2$ を含む(Titsの二者択一 の結論を一般の群に) | 周期群なので $F_2$ を含まず、無限なので仮想可解でない |
| 無限の有限生成群 $\Gamma$ は $\Gamma\times\Gamma$ と通約的でない($\mathbb Z^n$ では正しい) | prop-gg-commensurable |
4 行目:$G$ の元はすべて位数有限なので、位数無限の元をもつ $F_2$ は $G$ に含まれない。有限生成の仮想可解な周期群は有限である(Titsの二者択一 の例「反例の確かめ」の 2 行目と同じ論法:有限指数の可解部分群は有限生成で、導来列についての帰納法により有限)。$G$ は無限なので仮想可解でない。したがって $G$ はどの体の上の一般線形群にも埋め込めない。
5 行目:$\mathbb Z^n$ では、$\mathbb Z^n\times\mathbb Z^n=\mathbb Z^{2n}$ の増大は $2n$ 次で $n$ 次と同値でない(幾何学的群論 の系「$\mathbb Z^m$ と $\mathbb Z^n$ の区別」)ので、指数有限の部分群が互いに準等長であることから $\mathbb Z^n$($n\ge1$)は $\mathbb Z^n\times\mathbb Z^n$ と通約的でない。$G$ では prop-gg-commensurable により通約的になる。
check.py)。Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する