ランプライター群(lamplighter group)とは、花輪積 $C_2\wr\mathbb Z=\bigl(\bigoplus_{\mathbb Z}C_2\bigr)\rtimes\mathbb Z$ のことで、$\mathbb Z$ の各点の電球の点灯状態(有限個だけ点灯)と点灯係の位置の組を元とする。電球の切り替え $a$ と点灯係の移動 $t$ の 2 元で生成される可解群(したがって従順群)だが、増大度は指数的であり、関係式 $a^2$ と $[a,t^kat^{-k}]$($k\ge1$)による無限個の関係式の表示をもち、有限表示ではない。生成系 $\{a,t\}$ に関する語の長さは、点灯している電球の個数と、それらをすべて訪れる点灯係の最短の歩みの長さの和で与えられる。剰余有限群でもある。
ランプライター群(lamplighter group)とは、花輪積 $C_2\wr\mathbb Z=\bigl(\bigoplus_{\mathbb Z}C_2\bigr)\rtimes\mathbb Z$ のことである。$\mathbb Z$ の各点に電球が 1 つずつあり、有限個だけが点いている状態と、点灯係の位置の組を元とみなす。点灯係は 1 歩動くか、いる所の電球を切り替えるかのどちらかしかできない。
2 つの元で生成される小さな群だが、幾何学的群論のいくつもの「直観に反する例」の置き場になっている。可解(したがって従順)なのに増大度は指数的であり、有限生成なのに有限表示でない。この記事では、正規形と表示、語の長さの公式、従順性、指数的な増大、有限表示でないこと、剰余有限性を証明する。花輪積 の命題「ランプライター群の生成元と可解性」は前提として引き、写さない。
| 結果 | 内容 | この記事での扱い |
|---|---|---|
| prop-lamp-presentation | 正規形と無限個の関係式による表示 | 証明する |
| thm-lamp-length | 生成系 $\{a,t\}$ に関する語の長さの公式 | 証明する |
| cor-lamp-growth | 増大度は指数的 | 証明する |
| thm-lamp-folner | Følner 集合の具体形と従順性 | 証明する |
| thm-lamp-not-fp | 有限表示でない | 証明する |
| prop-lamp-rf | 剰余有限 | 証明する |
$C_2=\mathbb Z/2$ を加法で書く。台が有限の関数 $f\colon\mathbb Z\to C_2$ の全体を $B$ とし(点いている電球の集合 $\operatorname{supp}f$ と同じこと)、$m\in\mathbb Z$ による平行移動を $(m\cdot f)(x)=f(x-m)$ と書く。$\delta_k\in B$ は $k$ でだけ $1$ の関数である。
集合 $L=B\times\mathbb Z$ に積
$$
(f,m)(g,n)=(f+m\cdot g,\ m+n)
$$
を入れた群を ランプライター群 といい、$C_2\wr\mathbb Z$ と書く。単位元は $(0,0)$、逆元は $(f,m)^{-1}=(-(-m)\cdot f,\,-m)=((-m)\cdot f,\,-m)$ である。$a=(\delta_0,0)$、$t=(0,1)$ とおく。
これは 花輪積 の制限花輪積 $C_2\wr\mathbb Z$ を、$\mathbb Z$ の左正則作用で具体的に書いたものである(DK17 Definition 5.32、p. 131 はこの群をランプライター群と呼ぶ)。積の公式から、右から $a$ や $t$ を掛ける操作は
$$
(f,m)\,a=(f+\delta_m,\ m),\qquad (f,m)\,t=(f,\ m+1)
$$
である。すなわち $a$ は「点灯係のいる所 $m$ の電球を切り替える」、$t^{\pm1}$ は「点灯係を $\pm1$ 歩動かす」。左から掛けると $a(f,m)=(\delta_0+f,m)$、$t(f,m)=(1\cdot f,m+1)$ で、こちらは原点の電球の切り替えと、全体の平行移動である。
$a_k:=t^kat^{-k}=(\delta_k,0)$ である(花輪積 の命題「ランプライター群の生成元と可解性」の証明と同じ計算)。
1:$(f,0)(0,m)=(f,m)$ で、$(f,0)=\sum_{k\in\operatorname{supp}f}(\delta_k,0)$ は $a_k$ の積である。$(f,m)$ から $S=\operatorname{supp}f$ と $m$ が読めるので、書き方は一通りである。
2:右辺の群を $P$ とし、$P$ の中で $\alpha_k:=t^kat^{-k}$ とおく。$\alpha_k^2=t^ka^2t^{-k}=1$ である。$j< k$ について $[\alpha_j,\alpha_k]=t^j[a,\alpha_{k-j}]t^{-j}=1$ なので、$\alpha_k$ たちは互いに可換である。$a\mapsto(\delta_0,0)$、$t\mapsto(0,1)$ は関係式を保つ($L$ で $a^2=1$ で、$a_0$ と $a_k$ は底群 $B$ の元なので可換)ので、全射準同型 $\pi\colon P\to L$ が定まる(花輪積 の命題「ランプライター群の生成元と可解性」の 1 により $a,t$ は $L$ を生成する)。
$A:=\langle\alpha_k\mid k\in\mathbb Z\rangle\subset P$ は可換で、$t\alpha_kt^{-1}=\alpha_{k+1}$、$a=\alpha_0$ なので $t^{\pm1}$ と $a$ で正規化される。よって $A$ は $P$ の正規部分群で、$P=A\langle t\rangle$ である。したがって $P$ の各元は $\bigl(\prod_{k\in S}\alpha_k\bigr)t^m$($S$ は有限集合)の形に書ける($\alpha_k^2=1$ で指数を $0,1$ にそろえる)。この元の $\pi$ による像は $(\sum_{k\in S}\delta_k,m)$ で、これが単位元なら $m=0$、$S=\emptyset$ なので、元自身が $1$ である。よって $\pi$ は単射である。$\square$
群の表示 の言葉でいえば、$L$ は 2 個の生成元と 無限個 の関係式で表示される。この無限個がどうしても減らせないことを thm-lamp-not-fp で示す。
生成系 $\{a,t\}$ に関する語の長さを $\lvert g\rvert$ とする。すなわち $g$ を $a^{\pm1},t^{\pm1}$ の積で書くときの最小の文字数である($a^{-1}=a$)。$e$ を中心とする半径 $r$ の球を $\mathcal B(r)=\{g\in L\mid\lvert g\rvert\le r\}$ と書く。
$(f,m)\in L$ について、$\ell=\min(\operatorname{supp}f\cup\{0,m\})$、$r=\max(\operatorname{supp}f\cup\{0,m\})$ とおく。このとき
$$
\lvert(f,m)\rvert=\lvert\operatorname{supp}f\rvert+2(r-\ell)-\lvert m\rvert .
$$
右辺の第 2 項以下は、「$0$ から出発し、区間 $[\ell,r]$ の両端を訪れて $m$ で止まる」歩みの最短の長さである。点灯係は、点いている電球をすべて訪れて 1 回ずつ切り替え、$m$ で止まればよい。
読み方. 語 $w=s_1\cdots s_N$($s_j\in\{a,t,t^{-1}\}$)を左から読み、$e$ から始めて右から $s_1,s_2,\dots$ を掛けていく。右からの積の公式により、点灯係の位置 $p_j\in\mathbb Z$($p_0=0$)は $s_j=t^{\pm1}$ のとき $\pm1$ 動き、$s_j=a$ のとき動かずに位置 $p_{j-1}$ の電球を切り替える。$w$ の表す元を $(f,m)$ とすると、$m=p_N$ で、$f(x)=1$ となるのは位置 $x$ での切り替えの回数が奇数のときである。
下からの評価. 点いている電球 $x\in\operatorname{supp}f$ では少なくとも 1 回切り替えるので、$a$ の個数は $\lvert\operatorname{supp}f\rvert$ 以上で、点灯係は $x$ を訪れる。点灯係は $0$ から出て $m$ で止まるので、$\ell$ と $r$ を両方訪れる。$\ell$ を先に訪れるなら、$t^{\pm1}$ の個数は少なくとも
$$
\lvert0-\ell\rvert+(r-\ell)+\lvert r-m\rvert=2r-2\ell-m
$$
であり($\ell\le0\le r$、$\ell\le m\le r$ を使う)、$r$ を先に訪れるなら少なくとも $r+(r-\ell)+(m-\ell)=2r-2\ell+m$ である。どちらの場合も $2(r-\ell)-\lvert m\rvert$ 以上である。
上からの評価. $m\ge0$ とする。点灯係を $0$ から $\ell$ まで左へ、次に $r$ まで右へ、最後に $m$ まで左へ動かし、$\operatorname{supp}f$ の各点を初めて通るときにだけ $a$ を 1 回入れる。$[\ell,r]$ の点はすべて通るので、できる語は $(f,m)$ を表し、文字数は $\lvert\operatorname{supp}f\rvert+(-\ell)+(r-\ell)+(r-m)=\lvert\operatorname{supp}f\rvert+2(r-\ell)-m$ である。$m< 0$ なら、先に $r$ まで右へ、次に $\ell$ まで左へ、最後に $m$ まで右へ動かせば、同じく $\lvert\operatorname{supp}f\rvert+2(r-\ell)+m$ 文字で済む。$\square$
群の 増大度 は、球の大きさ $\lvert\mathcal B(r)\rvert$ が $r$ についてどれだけ速く増えるかで測る。$\lim_{r\to\infty}\lvert\mathcal B(r)\rvert^{1/r}>1$ のとき増大度が 指数的 であるという(極限の存在と生成系によらないことは DK17 §8.7、Definition 8.76、p. 279)。
$k\ge1$ について $\lvert\mathcal B(2k)\rvert\ge2^k$ である。とくに $\lim_r\lvert\mathcal B(r)\rvert^{1/r}\ge\sqrt2$ で、$L$ の増大度は指数的である。
$\operatorname{supp}f\subset\{0,1,\dots,k-1\}$ となる $2^k$ 個の $f$ について、$(f,k)$ を考える。$\ell=0$、$r=k$ なので thm-lamp-length から $\lvert(f,k)\rvert=\lvert\operatorname{supp}f\rvert+2k-k\le2k$ である。これらは相異なるので $\lvert\mathcal B(2k)\rvert\ge2^k$ で、$\lvert\mathcal B(2k)\rvert^{1/(2k)}\ge\sqrt2$ である。$\square$
thm-lamp-length の公式と、生成系 $\{a,t,t^{-1}\}$ についての幅優先探索とで、半径 $r$ の球面(長さがちょうど $r$ の元)の個数を $r=0,1,\dots,10$ について数えると $1,3,6,12,22,40,71,123,212,360,607$ になり、両者は一致する(検算)。隣り合う項の比は $r=10$ で $607/360\approx1.69$ である。上の系の $\sqrt2\approx1.414$ は、粗いが証明の短い下界である。
従順群 の定義「Følner 条件」は、どの有限集合 $S$ と $\varepsilon>0$ についても、$\lvert sF\triangle F\rvert\le\varepsilon\lvert F\rvert$($s\in S$)となる空でない有限集合 $F$ があることであった。$L$ は可解なので、従順群 の系「アーベル群と可解群」によりすでに従順だが、ここでは Følner 集合を具体的に作る。
$n\ge0$ について
$$
F_n=\bigl\{(g,k)\in L\ \big|\ \lvert k\rvert\le n,\ \operatorname{supp}g\subset[k-n,\,k+n]\bigr\}
$$
とおく。$\lvert F_n\rvert=(2n+1)\,2^{2n+1}$ で、
$$
aF_n=F_n,\qquad \frac{\lvert t^{\pm1}F_n\triangle F_n\rvert}{\lvert F_n\rvert}=\frac2{2n+1}.
$$
さらに語の長さが $\lvert s\rvert$ の元 $s$ について $\lvert sF_n\triangle F_n\rvert\le\frac{2\lvert s\rvert}{2n+1}\lvert F_n\rvert$ である。したがって $L$ は Følner 条件を満たし、従順である。
$F_n$ は「点灯係の位置 $k$ が $[-n,n]$ にあり、点いている電球が点灯係から距離 $n$ 以内にある」状態の全体である。$k$ の選び方が $2n+1$ 通り、電球の点け方が $2^{2n+1}$ 通りである。
$a(g,k)=(\delta_0+g,k)$ で、$\lvert k\rvert\le n$ から $0\in[k-n,k+n]$ なので、$\delta_0+g$ の台も窓に入る。よって $aF_n\subset F_n$ で、$a^2=1$ から等号である。
$t(g,k)=(1\cdot g,\,k+1)$ で、$\operatorname{supp}(1\cdot g)=\operatorname{supp}g+1\subset[(k+1)-n,(k+1)+n]$ である。よって $t(g,k)\in F_n$ となるのはちょうど $k\ne n$ のときで、$\lvert tF_n\setminus F_n\rvert=2^{2n+1}$ である。$\lvert tF_n\rvert=\lvert F_n\rvert$ なので $\lvert F_n\setminus tF_n\rvert$ も $2^{2n+1}$ で、$\lvert tF_n\triangle F_n\rvert=2\cdot2^{2n+1}$ である。$t^{-1}$ も同じである。
一般の $s=s_1s_2\cdots s_N$($s_j\in\{a,t,t^{-1}\}$、$N=\lvert s\rvert$)では、左からの積が対称差の大きさを保つことと三角不等式から
$$
\lvert s_1s'F\triangle F\rvert\le\lvert s_1s'F\triangle s_1F\rvert+\lvert s_1F\triangle F\rvert=\lvert s'F\triangle F\rvert+\lvert s_1F\triangle F\rvert
$$
($s'=s_2\cdots s_N$)なので、帰納法で $\lvert sF_n\triangle F_n\rvert\le N\cdot2\cdot2^{2n+1}=\frac{2N}{2n+1}\lvert F_n\rvert$ である。有限集合 $S$ と $\varepsilon$ に対し $n$ を $\frac{2\max_{s\in S}\lvert s\rvert}{2n+1}\le\varepsilon$ にとればよい。従順性は 従順群 の定理「Følner 条件を満たす群は従順」による。$\square$
素朴な候補「点灯係が $[-n,n]$ にいて、電球が $[-n,n]$ の中だけで点いている」状態の集合は、右から の積についての Følner 集合であり、左からの $t$ では全体が平行移動されて半分以上が外に出る。実際、この素朴な集合を $N_n$ とすると $t(g,k)=(1\cdot g,k+1)$ が $N_n$ に残るのは $k\ne n$ かつ $g(n)=0$ のときだけなので、$\lvert tN_n\setminus N_n\rvert/\lvert N_n\rvert=1-\frac{2n}{2n+1}\cdot\frac12=\frac{n+1}{2n+1}>\frac12$ である。上の $F_n$ はその集合の逆元の全体である($(f,m)^{-1}=((-m)\cdot f,-m)$)。
指数的な増大との対比. 自由群 $F_2$ も増大度は指数的だが、従順でない(従順群 の定理「自由群は従順でない」)。$L$ は、増大度が指数的でも従順でありうることを示す最も簡単な例である。$F_n$ の大きさは半径 $n$ の球と同じく指数的に増えるが、境界はその $2/(2n+1)$ の割合にとどまる。
群 $G$ が 有限表示 であるとは、有限個の生成元と有限個の関係式による表示 $\langle X\mid R\rangle$ をもつことをいう。まず、この性質は有限生成系の選び方によらず、しかも与えられた表示の関係式から有限個を選べばよいことを確かめる。
$X$ を有限集合、$R\subset F(X)$(自由群)とし、$G=\langle X\mid R\rangle$ が有限表示であるとする。このとき有限集合 $R_0\subset R$ で、$G=\langle X\mid R_0\rangle$(自然な全射 $\langle X\mid R_0\rangle\to G$ が同型)となるものがある。
$G=\langle Y\mid T\rangle$ を有限の表示とし、$\varphi\colon F(Y)\to G$、$\pi\colon F(X)\to G$ を自然な全射とする。$K=\ker\pi$ は $R$ の正規閉包である。各 $y\in Y$ について $\pi(u_y)=\varphi(y)$ となる語 $u_y\in F(X)$、各 $x\in X$ について $\varphi(v_x)=\pi(x)$ となる語 $v_x\in F(Y)$ を選ぶ。準同型 $\theta\colon F(Y)\to F(X)$ を $y\mapsto u_y$ で定め、
$$
Q=\{\theta(s)\mid s\in T\}\cup\{x^{-1}\theta(v_x)\mid x\in X\}\subset F(X)
$$
とおく。$\pi\theta=\varphi$ なので $Q\subset K$ である。$N$ を $Q$ の正規閉包とする。$\theta$ は $T$ を $N$ に送るので、準同型 $\bar\theta\colon G\to F(X)/N$、$\varphi(y)\mapsto u_yN$ が定まる。$\pi$ から誘導される $\bar\pi\colon F(X)/N\to G$ について、$\bar\theta\bar\pi(xN)=\bar\theta(\varphi(v_x))=\theta(v_x)N=xN$ なので $\bar\theta\bar\pi$ は恒等写像で、$\bar\pi$ は単射である。よって $K=N$ である。
$Q$ は有限集合で、その各元は $K$ の元なので $R$ の元の共役の有限個の積で書ける。そこに現れる $R$ の元を集めた有限集合を $R_0$ とすると、$Q$ は $R_0$ の正規閉包に含まれ、$K=N\subset\langle\!\langle R_0\rangle\!\rangle\subset K$ である。$\square$
ランプライター群 $L$ は有限表示でない。
$L$ が有限表示であるとする。prop-lamp-presentation の表示に lem-lamp-finite-relators を当てると、ある $n\ge1$ について
$$
P_n=\bigl\langle a,t\ \big|\ a^2,\ [a,t^kat^{-k}]\ (1\le k\le n)\bigr\rangle\longrightarrow L
$$
が同型になる。とくに $P_n$ で $[a,t^{n+1}at^{-(n+1)}]=1$ である。これに反する群を作る。
段 1(Coxeter 群). 生成元 $b_k$($k\in\mathbb Z$)と関係式 $b_k^2=1$、$(b_ib_j)^2=1$($1\le\lvert i-j\rvert\le n$)で定まる群を $W$ とする(Coxeter群 の一種)。$b_k\mapsto b_{k+1}$ は関係式を関係式に移すので自己準同型 $\sigma$ を定め、$b_k\mapsto b_{k-1}$ がその逆なので自己同型である。半直積 $\Gamma=W\rtimes_\sigma\mathbb Z$ をとり、$\mathbb Z$ の生成元を $\tau$ と書く($\tau b_k\tau^{-1}=b_{k+1}$)。
段 2($P_n$ から $\Gamma$ へ). $a\mapsto b_0$、$t\mapsto\tau$ とすると、$a^2\mapsto b_0^2=1$、$[a,t^kat^{-k}]\mapsto b_0b_kb_0^{-1}b_k^{-1}=(b_0b_k)^2=1$($1\le k\le n$)なので、準同型 $P_n\to\Gamma$ が定まる。$[a,t^{n+1}at^{-(n+1)}]$ の像は $(b_0b_{n+1})^2$ である。
段 3(像は単位元でない). 準同型 $\psi\colon W\to S_3$ を $b_0\mapsto(1\,2)$、$b_{n+1}\mapsto(2\,3)$、ほかの $b_k\mapsto\mathrm{id}$ で定める。関係式 $(b_ib_j)^2$($1\le\lvert i-j\rvert\le n$)では $\{i,j\}=\{0,n+1\}$ にならないので、$b_i,b_j$ の少なくとも一方の像は $\mathrm{id}$ で、像は互換か $\mathrm{id}$ の平方、すなわち $\mathrm{id}$ になる。$b_k^2$ も同様である。よって $\psi$ は well-defined で、$\psi((b_0b_{n+1})^2)=((1\,2)(2\,3))^2=(1\,2\,3)^2\ne\mathrm{id}$ である。
したがって $P_n$ で $[a,t^{n+1}at^{-(n+1)}]\ne1$ となり、矛盾する。$\square$
証明が示しているのは、$P_n$ では「距離 $n+1$ 離れた電球の切り替えが可換」が従わないことである。関係式を有限個に切ると、遠い電球どうしの可換性が失われる。
$N\ge1$ について、$\bar f(j)=\sum_{x\equiv j\ (\mathrm{mod}\ N)}f(x)$ とおくと、
$$
\rho_N\colon L\to C_2\wr C_N,\qquad (f,m)\mapsto(\bar f,\ m\bmod N)
$$
は準同型である(右辺は $C_N=\mathbb Z/N$ の上の関数と $C_N$ の、同じ積の公式による半直積で、位数 $2^NN$)。単位元でない $g\in L$ には $\rho_N(g)\ne1$ となる $N$ がある。したがって $L$ は 剰余有限群 である。
$\overline{m\cdot g}=(m\bmod N)\cdot\bar g$ は和の添字をずらすだけで確かめられる。よって $\rho_N((f,m)(g,n))=(\bar f+\overline{m\cdot g},\,m+n)=\rho_N(f,m)\,\rho_N(g,n)$ である。
$g=(f,m)\ne1$ とする。$m\ne0$ なら $N=\lvert m\rvert+1$ にとれば $m\not\equiv0$ である。$m=0$ なら $f\ne0$ で、$N$ を $\operatorname{supp}f$ の幅 $\max\operatorname{supp}f-\min\operatorname{supp}f$ より大きくとると、$\operatorname{supp}f$ の点は $N$ を法として相異なるので、$f$ を巻きつけた $\bar f$ は $\operatorname{supp}f$ の点の剰余で値 $1$ をとり、$0$ でない。$\square$
$\rho_N$ は、電球を $N$ 個の円周に並べた「有限のランプライター群」への商である。$C_2\wr C_N$ はブロック系をもつ置換群として 花輪積 の記事に現れる型の有限群である。
ランプライター群は、群論で自然に期待される含意が成り立たない例として使われる。
| 期待される含意 | 成り立たない理由 | 根拠 |
|---|---|---|
| 有限生成の可解群は有限表示 | $L$ は 2 元生成の可解群で有限表示でない | thm-lamp-not-fp |
| 従順な群の増大度は指数的でない | $L$ は従順で増大度は指数的 | thm-lamp-folner、cor-lamp-growth |
| 有限生成の群の部分群は有限生成 | $L$ の交換子部分群は有限生成でない | 花輪積 の記事、DK17 p. 492 |
| 無限個の関係式による表示は、十分先で切れば同じ群を表す | どの $n$ でも $P_n\to L$ は同型でない | prf-lamp-not-fp の段 3 |
| 右から Følner なら左からも Følner | 素朴な集合 $N_n$ は右からの積でしか Følner でない | thm-lamp-folner の後の注意 |
$n=1$ とする。$P_1=\langle a,t\mid a^2,[a,tat^{-1}]\rangle$ では $a$ と $t^2at^{-2}$ は可換でない。実際、prf-lamp-not-fp の $\psi$ は $b_0\mapsto(1\,2)$、$b_2\mapsto(2\,3)$ で、$a$ と $t^2at^{-2}$ の積の像は位数 $3$ の巡回置換である。したがって $P_1$ での $a\cdot t^2at^{-2}$ の位数は $2$ ではない(無限か $3$ の倍数)。$L$ ではこの元は $(\delta_0+\delta_2,0)$ で位数 $2$ なので、自然な全射 $P_1\to L$ はこの元の位数を変える。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する