Grigorchuk群

同義語:Grigorchuk group

概要

Grigorchuk群(Grigorchuk group)とは、根付きの無限二分木に作用する 4 つの位数 $2$ の自己同型 $a,b,c,d$ が、木の上の簡単な再帰で生成する群である。有限生成の無限群ですべての元の位数が $2$ の冪であり、一般の Burnside 問題の反例になる。増大関数が多項式より速く指数関数より遅い中間増大をもつ最初の例であり、従順であるが初等従順ではない。

$$\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}} $$

前提知識: 群, 群作用, 二分木, 部分群の指数

Grigorchuk群(Grigorchuk group)は、根付きの無限二分木の自己同型 $a,b,c,d$ で生成される群 $G$ である。R. Grigorchuk が 1980 年代に構成した(GP06 p. 1。年は同 p. 16 の文献 [3](1980 年)・[4](1983 年)による)。4 つの生成元はどれも位数 $2$ で、定義は木の上の簡単な再帰で書けるが、群としては次の性質をあわせもつ。

  1. 有限生成の無限群で、すべての元の位数が $2$ の冪である。したがって「有限生成の周期群は有限か」という一般の Burnside問題 の反例になる。
  2. 増大関数が多項式より速く、指数関数より遅い(中間増大)。Milnor が問うた「有限生成群の増大は多項式か指数関数か」に否定的に答えた最初の例である(GP06 p. 1)。
  3. 従順群であるが、可解群などから組み立てられる初等従順群ではない。
    この記事では、群の定義と自己相似性、無限であること、周期群であること、$G$ と $G\times G$ の通約性、多項式増大でないこと、従順であることを証明する。増大の上下からの評価は主張と所在を述べる。
    結果内容この記事での扱い
    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))$ とする。

Grigorchuk群

$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$ で決まるので単射である。

書き換え規則
  1. $\psi(b)=(a,c)$、$\psi(c)=(a,d)$、$\psi(d)=(1,b)$、$\psi(aba)=(c,a)$、$\psi(aca)=(d,a)$、$\psi(ada)=(b,1)$ である。
  2. $a$ の個数が偶数の語 $w$ について、$x\in\{b,c,d\}$ の各出現に「その前にある $a$ の個数の偶奇 $p$」を付ける。$x^{(0)},x^{(1)}$ を $\psi(x)=(x^{(0)},x^{(1)})$ の成分とし、$w$ の $a$ を消して、偶奇 $p$ の出現 $x$ を第 0 成分の語では $x^{(p)}$、第 1 成分の語では $x^{(1-p)}$ に置き換える。得られる 2 つの語が表す元の組が $\psi(w)$ である。とくに $\psi(H)\subset G\times G$ である。
  3. 2 で、$w$ の $a$ でない文字が $k$ 個なら、2 つの成分の語の長さは $k$ 以下である。$a$ の個数が奇数の語 $v$ について、$v^2$ の 2 つの成分の語の長さは、$v$ の $a$ でない文字の個数を $k$、そのうちの $d$ の個数を $k_d$ として、どちらも $2k-k_d$ である。
  1. 前半の 3 つは定義そのものである。$(axa)(0u)=a(x(1u))=a(1\,x^{(1)}(u))=0\,x^{(1)}(u)$、同様に $(axa)(1u)=1\,x^{(0)}(u)$ なので $\psi(axa)=(x^{(1)},x^{(0)})$ である。
  2. $w=a^{e_0}x_1a^{e_1}x_2\cdots x_ka^{e_k}$($x_i\in\{b,c,d\}$)とし、$p_i\equiv e_0+\dots+e_{i-1}\pmod2$ とする。$a^2=1$ と $e_0+\dots+e_k$ が偶数であることから、$w=\prod_{i=1}^k a^{p_i}x_ia^{p_i}$ である(隣り合う $a^{p_i}a^{p_{i+1}}$ が $a^{e_i}$ に、両端が $a^{e_0}$、$a^{e_k}$ に一致する)。$\psi$ は準同型なので、1 から主張の形になる。
  3. 前半は、各 $x$ が各成分に高々 1 文字を与えることから従う。後半:$v$ の $a$ の個数は奇数なので、$v^2=vv$ の中で $v$ の各文字 $x$ は前後 2 回、互いに逆の偶奇で現れる。したがって各成分の語は、各 $x$ から $x^{(0)}$ と $x^{(1)}$ を 1 文字ずつ受け取る。$b\mapsto(a,c)$、$c\mapsto(a,d)$ は 2 文字、$d\mapsto(1,b)$ は 1 文字を与えるので、長さは $2k-k_d$ である。$\square$

$\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$ は無限群である。

$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)である。

周期群であること

元の位数は 2 の冪

$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\}$ をとる。

$G$ と $G\times G$ の通約性

$\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$ が同値になる(幾何学的群論 の命題「指数有限の部分群は準等長」と定理「増大度の準等長不変性」による)。

中間増大
  1. $G$ の増大関数はどの多項式でも上から抑えられない。
  2. ある $0<\alpha\le\nu<1$ と定数 $C\ge1$ について、$\exp(n^\alpha)\le C\beta_S(Cn)$ かつ $\beta_S(n)\le C\exp((Cn)^\nu)$ である。
  3. とくに $\lim_{n\to\infty}\beta_S(n)^{1/n}=1$ である。
  1. 多項式で抑えられるとすると、幾何学的群論 の定理「Gromov の多項式増大度定理」により、$G$ は指数有限の冪零部分群 $N$ をもつ。$N$ は有限生成群の指数有限の部分群なので有限生成で、thm-gg-torsion により周期群である。有限生成の冪零な周期群は有限である(DK17 Proposition 13.65, p. 480)。すると $G$ も有限になり、thm-gg-infinite に反する。
    2 は GP06 Corollary 6.5(p. 10、下からの評価)と Proposition 9.2(p. 13、上からの評価)であり、この記事では証明しない。下からの評価は prop-gg-commensurable の $\beta\sim\beta^2$ から、上からの評価は第 3 段の 8 個の成分の長さの和が $\frac56\ell(g)+8$ 以下になること(同 Lemma 9.1, p. 13)から導かれる。3 は 2 の上からの評価と $\nu<1$ から従う。$\square$

$\lim\beta_S(n)^{1/n}$ が $1$ より大きいことが指数関数的な増大であり、多項式で抑えられることが多項式増大である。thm-gg-growth はそのどちらでもない増大が実際に起こることを示す。

従順性

従順だが初等従順でない
  1. $G$ は従順群である。
  2. $G$ は初等従順群(有限群と可換群を含み、部分群・商・拡大・増大和で閉じた最小のクラスの群)でない。
  1. 従順群 の定理「Følner 条件を満たす群は従順」により、Følner 条件を示せばよい。有限集合 $K\subset G$ と $\varepsilon>0$ をとり、$r:=\max_{s\in K}\ell(s)$ とする。$F=B_S(n)$ とおくと、$s\in K$ について $sF\subset B_S(n+r)$ かつ $\lvert sF\rvert=\lvert F\rvert$ なので
    $$ \lvert sF\triangle F\rvert=2\lvert sF\setminus F\rvert\le2\bigl(\beta_S(n+r)-\beta_S(n)\bigr) $$
    である。すべての $n$ で $\beta_S(n+r)>(1+\varepsilon/2)\beta_S(n)$ なら、$\beta_S(kr)>(1+\varepsilon/2)^k$ となり $\liminf\beta_S(n)^{1/n}\ge(1+\varepsilon/2)^{1/r}>1$ で thm-gg-growth の 3 に反する。よってある $n$ で $\beta_S(n+r)\le(1+\varepsilon/2)\beta_S(n)$ で、そのとき $\lvert sF\triangle F\rvert\le\varepsilon\lvert F\rvert$ である。
  2. 有限生成の初等従順群は、仮想冪零であるか、2 元で生成される自由半群を含む(Chou の定理、DK17 Theorem 18.58, p. 593)。$G$ が仮想冪零でないことは thm-gg-growth の 1 の証明で示した。$x,y\in G$ が自由半群を生成するとすると、$x$ の位数を $k$ として $x^{k+1}=x$ は異なる 2 つの正の語の間の関係なので矛盾である。$\square$

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 により通約的になる。

ほかの性質

  • 残余有限. 第 $n$ 段の各点を固定する元の全体 $H_n$ は、$G$ から第 $n$ 段の置換群への準同型の核なので、指数有限の正規部分群である。$\bigcap_nH_n=1$ なので $G$ は残余有限群である。
  • 語の問題. lem-gg-psi の書き換えを繰り返すと、語が単位元を表すかを判定できる。GP06 Theorem 8.2(p. 12)は、長さ $n$ の語について $O(n\log n)$ の時間で判定する手続きを与えている。
  • 有限表示をもたない. $G$ は有限表示をもたない(GP06 p. 15)。有限表示をもつ中間増大の群が存在するかは GP06(2006 年)の時点で未解決の問題とされている。
    数値で確かめた値として、$\beta_S(n)$ は $n=0,1,\dots,8$ で $1,5,11,23,40,68,108,176,271$ である(第 14 段への作用で元を区別して数えた値。検算 check.py)。

使いどころ

  • 群論の反例の供給源. Burnside 問題・Milnor の問題・従順性の階層を一つの群で分ける。どれも、有限の木の上の再帰という具体的な定義から証明できる。
  • 自己相似群. lem-gg-psi の形の再帰で定まる群は自己相似群(オートマトン群)とよばれ、Grigorchuk群はその代表例である。成分への分解で長さが減ることを使う帰納法は、この種の群の基本的な道具になる。
  • 増大度の理論. 増大度と代数構造の関係(幾何学的群論 の Gromov の定理、Titsの二者択一 の増大度の二分法)が、一般の有限生成群ではどこまで成り立たないかを示す。

関連項目

参考文献

[1]
R. Grigorchuk and I. Pak, Groups of intermediate growth: an introduction for beginners, arXiv:math/0607384, 2006, p. 1:Milnor の問題と最初の構成、p. 6:生成元の直接の記述 (*)、p. 7:Exercise 4.4、p. 8:Lemma 5.3・Corollaries 5.4・5.5、p. 9:Proposition 6.1・Lemmas 6.2・6.3、p. 10:Corollary 6.5、p. 12:Exercise 7.5・Theorem 8.2、p. 13:Lemma 9.1・Proposition 9.2、p. 15:有限表示をもたないこと、p. 16:文献 [3]・[4](構成の年)

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