ピンポン補題(ping-pong lemma)とは、集合 $X$ の全単射 $g_1,g_2$ と空でない交わらない部分集合 $X_1,X_2$ について、すべての整数 $k\ne0$ で $g_1^{\,k}(X_2)\subset X_1$、$g_2^{\,k}(X_1)\subset X_2$ なら、$g_1,g_2$ は階数 2 の自由群を自由に生成するという補題である。部分群の族の形では自由積の判定になる(2 つの位数 2 の群だけの場合を除く)。交互の語は点をもとの場所に戻せないことが理由である。行列群、Möbius 変換、木の自己同型で自由部分群を作る標準の道具で、Tits の二者択一の証明の鍵である。
ピンポン補題(ping-pong lemma、table-tennis lemma)は、集合に作用する変換の組が自由に生成することを、作用の打ち返しの様子から判定する補題である。F. Klein の判定法とも呼ばれる(Har00)。交わらない 2 つの集合 $X_1,X_2$ があり、$g_1$ の $0$ でない冪がどれも $X_2$ を $X_1$ の中へ、$g_2$ の $0$ でない冪がどれも $X_1$ を $X_2$ の中へ打ち返すなら、交互の語は点をもとの場所に戻せない。よって $g_1,g_2$ の間には関係式がない。
群を定義関係で調べるのが難しいときでも、作用する空間と集合の組を見つけるだけで自由性が示せる。行列群、双曲幾何、木への作用のどこでも使える。行列の群が自由部分群を含むという Titsの二者択一 の証明の鍵である(J. Tits の 1972 年の論文 Tit72)。
この記事では、自由積の形を主張として証明し、Titsの二者択一 の補題「2 元のピンポン補題」と同じ 2 元の形(記号 $X,g_1,g_2,X_1,X_2$ も同じ)をその系として得る。行列 $\begin{pmatrix}1&r\\0&1\end{pmatrix}$、$\begin{pmatrix}1&0\\r&1\end{pmatrix}$ の $\lvert r\rvert\ge2$ での自由性そのものは同記事の例「整数行列の自由部分群」に任せ、ここでは $r$ による変化を調べる。
| 結果 | 内容 | この記事での扱い |
|---|---|---|
| thm-ppl-main | 自由積の判定 | 証明する |
| cor-ppl-two | 2 元の形 | 証明する |
| prop-ppl-schottky | 4 つの集合の形(Schottky の形) | 証明する |
| prop-ppl-semigroup | 半群の形 | 証明する |
| prop-ppl-hyperbolic | 双曲型の元の大きな冪 | 証明する |
| prop-ppl-tree | 木の双曲的自己同型 | 証明する |
| prop-ppl-values | $r$ の値による自由性 | 証明する |
| thm-ppl-projective | 射影空間の形 | 主張と所在 |
$\operatorname{Bij}(X)$ を集合 $X$ の全単射の群とする。
$I$ を $2$ 個以上の元をもつ添字集合、$\Gamma_i$($i\in I$)を $\operatorname{Bij}(X)$ の部分群、$X_i\subset X$($i\in I$)を空でない互いに交わらない部分集合とし、
$$
g(X_j)\subset X_i\qquad(i\ne j,\ g\in\Gamma_i\setminus\{1\})
$$
が成り立つとする。さらに、$I$ が $3$ 個以上の元をもつか、ある $\Gamma_i$ の位数が $3$ 以上であるとする。このとき包含写像から定まる準同型 $\varphi\colon\ast_{i\in I}\Gamma_i\to\operatorname{Bij}(X)$ は単射である。
自由積の単位元でない元は、簡約語 $w=g_1g_2\cdots g_s$($s\ge1$、$g_k\in\Gamma_{i_k}\setminus\{1\}$、$i_k\ne i_{k+1}$)としてただ 1 通りに書ける(自由積 の定理「簡約語の集合は群をなす」)。$\varphi(w)\ne\mathrm{id}$ を示す。
$i_1,i_s$ のどちらとも異なる $j\in I$ がある場合. $x\in X_j$ をとる。$j\ne i_s$ なので $g_s(x)\in X_{i_s}$ である。$i_{k}\ne i_{k+1}$ なので順に $g_k(X_{i_{k+1}})\subset X_{i_k}$ が使え、$\varphi(w)(x)\in X_{i_1}$ となる。$j\ne i_1$ で $X_j\cap X_{i_1}=\emptyset$ なので $\varphi(w)(x)\ne x$ である。
そのような $j$ がない場合. $I$ は $2$ 個以上の元をもつので、$i_1=i_s$ ならそのような $j$ がある。よって $i_1\ne i_s$ で $I=\{i_1,i_s\}$ である。仮定から $\Gamma_{i_1}$ か $\Gamma_{i_s}$ の位数が $3$ 以上である。$w$ を $w^{-1}$ に替えると両端が入れ替わるので、$\Gamma_{i_1}$ の位数が $3$ 以上としてよい。$c\in\Gamma_{i_1}\setminus\{1,g_1^{-1}\}$ をとると、
$$
w':=cwc^{-1}=(cg_1)g_2\cdots g_s\,c^{-1}
$$
は両端が $\Gamma_{i_1}$ の元の簡約語である($cg_1\ne1$、$c^{-1}\ne1$)。前段で $j=i_s$ として $\varphi(w')\ne\mathrm{id}$ であり、$\varphi(w)$ はその共役なので $\mathrm{id}$ でない。$\square$
位数の仮定は外せない(ex-ppl-counter の 1 行目)。$I=\{1,2\}$ で位数がともに $2$ のとき、語 $ab$ は $X_1$ を $X_1$ の中へ写すだけで、点を動かすとは限らない。
$X$ を集合、$g_1,g_2$ を $X$ の全単射、$X_1,X_2\subset X$ を空でない交わらない部分集合とし、すべての整数 $k\ne0$ について
$$
g_1^{\,k}(X_2)\subset X_1,\qquad g_2^{\,k}(X_1)\subset X_2
$$
が成り立つとする。このとき $g_1,g_2$ は階数 $2$ の自由群を自由に生成する。
$k\ne0$ のとき、$g_1^{\,k}$ は空でない $X_2$ を交わらない $X_1$ の中へ写すので $\mathrm{id}$ でない。よって $\Gamma_1:=\langle g_1\rangle$ は無限巡回群で、$\Gamma_2:=\langle g_2\rangle$ も同様である。thm-ppl-main により $\varphi\colon\mathbb{Z}\ast\mathbb{Z}\to\operatorname{Bij}(X)$ は単射である。$\mathbb{Z}\ast\mathbb{Z}$ は階数 $2$ の 自由群 である。$\square$
階数 $2$ の自由群 $F_2$ は、既約語の集合への左からの積で、$X_1$ を $a^{\pm1}$ で始まる語、$X_2$ を $b^{\pm1}$ で始まる語とすれば補題の仮定を満たす。したがって「自由である」ことは「仮定を満たす作用がある」ことと同値である。難しいのは、与えられた行列などの自然な作用の上で集合を見つけることである。
同じ系統の主張は DK17 §7.6(pp. 224–227)にある。そこでの証明も語の長さの帰納法だが、仮定の立て方が異なるので、この記事では上の形で述べて証明した。
応用では、生成元とその逆元に別々の集合を割り当てることが多い。
$n\ge2$ とし、$g_1,\dots,g_n\in\operatorname{Bij}(X)$、$X_i^+,X_i^-$($1\le i\le n$)を空でない互いに交わらない $2n$ 個の集合とする。各 $i$ で
$$
g_i(X\setminus X_i^-)\subset X_i^+
$$
であるとする(これは $g_i^{-1}(X\setminus X_i^+)\subset X_i^-$ と同値である)。このとき $g_1,\dots,g_n$ は階数 $n$ の自由群を自由に生成する。
同値性:$g(A)\subset B$ と $g^{-1}(X\setminus B)\subset X\setminus A$ は同値であり、$A=X\setminus X_i^-$、$B=X_i^+$ とおけばよい。
$X_i:=X_i^+\cup X_i^-$ とおく。$X_i^+\subset X\setminus X_i^-$ なので、$k\ge1$ について帰納的に $g_i^{\,k}(X\setminus X_i^-)\subset X_i^+$ である。同様に $g_i^{-k}(X\setminus X_i^+)\subset X_i^-$ である。$j\ne i$ なら $X_j$ は $X\setminus X_i^-$ と $X\setminus X_i^+$ の両方に含まれるので、$k\ne0$ で $g_i^{\,k}(X_j)\subset X_i$ である。$X_j$ は空でなく $X_i$ と交わらないので $g_i^{\,k}\ne\mathrm{id}$ で、$\Gamma_i=\langle g_i\rangle$ は無限巡回群である。thm-ppl-main により主張が従う。$\square$
$X$ をリーマン球面 $\widehat{\mathbb{C}}$ とし、互いに交わらない閉円板 $D_i^\pm$ と、$D_i^-$ の外を $D_i^+$ の内部へ写す Möbius 変換 $g_i$ をとると($X_i^-=D_i^-$、$X_i^+$ を $D_i^+$ の内部とする)、prop-ppl-schottky から $g_1,\dots,g_n$ は自由に生成する。これが Schottky の構成(Schottky群)で、Klein群 の基本の例である。
上半平面 $\mathbb{H}^2$ に作用する $g_1(z)=z+2$、$g_2(z)=z/(2z+1)$ を考える。
$$
X_1^-=\{\mathrm{Re}\,z< -1\},\quad X_1^+=\{\mathrm{Re}\,z\ge1\},\quad X_2^-=\{\lvert z+\tfrac12\rvert< \tfrac12\},\quad X_2^+=\{\lvert z-\tfrac12\rvert\le\tfrac12\}
$$
とおく(すべて $\mathbb{H}^2$ の中の集合)。これらは互いに交わらない。閉じた側の境界が接する $0,\pm1$ は実軸の上にあり、$\mathbb{H}^2$ に入らないからである。$g_1(X\setminus X_1^-)=X_1^+$ は明らかである。$g_2$ は $-1,0,\infty$ を $1,0,\tfrac12$ へ写すので、$-1,0$ を結ぶ半円を $1,0$ を結ぶ半円へ写し、その外側を内側へ写す。よって $g_2(X\setminus X_2^-)=X_2^+$ である。prop-ppl-schottky により $g_1,g_2$ は自由に生成する。4 つの集合の補集合は頂点 $\infty,-1,0,1$ の理想四角形(辺の一部を含む)で、これを貼ると 3 点抜き球面になる(発展写像 の例「3 点抜き球面」)。
図: 上半平面の左右の縦の帯と、原点で接する 2 つの半円板。平行移動は左の帯の外を右の帯へ写し、もう一方の変換は左の半円板の外を右の半円板へ写す
$g,h\in\mathrm{PSL}(2,\mathbb{R})$ を双曲型(跡の絶対値が $2$ より大きい)とし、$\mathbb{RP}^1$ の上の固定点の計 $4$ 個が相異なるとする。このとき $N$ があって、$m\ge N$ なら $g^m,h^m$ は階数 $2$ の自由群を自由に生成する。
$g$ の吸引的・反発的な固定点を $a_+,a_-$、$h$ のそれを $b_+,b_-$ とし、これらの互いに交わらない開区間の近傍 $A_\pm,B_\pm$ をとる。$g$ は共役で $x\mapsto\lambda x$($\lambda>1$、$a_+=\infty$、$a_-=0$)となるので、$a_-$ の近傍の外は $g^m$ で一様に $a_+$ の近くへ移る。よって $N$ があって $m\ge N$ で $g^m(\mathbb{RP}^1\setminus A_-)\subset A_+$ である。$h$ についても同様である。prop-ppl-schottky を $X=\mathbb{RP}^1$ に使う。$\mathrm{PSL}(2,\mathbb{R})$ は $\mathbb{RP}^1$ に効果的に作用するので、自由性は $\mathrm{PSL}(2,\mathbb{R})$ の中で成り立つ。$\square$
$\mathrm{SL}(2,\mathbb{R})$ の持ち上げも自由に生成する。$F_2\to\mathrm{SL}(2,\mathbb{R})\to\mathrm{PSL}(2,\mathbb{R})$ の合成が単射だからである。
高次元の形は次のとおりである。局所体 $\mathbb{K}$ の上の $g\in\mathrm{GL}(n,\mathbb{K})$ が 近接的 とは、絶対値が最大の固有値が重複なく 1 つだけのことをいう。このとき固有直線の点 $A_g\in\mathbb{KP}^{n-1}$ と、残りの一般固有空間の和の超平面 $E_g$ が定まる。
$g,h\in\mathrm{GL}(n,\mathbb{K})$ とする。$g^{\pm1},h^{\pm1}$ がすべて近接的で、すべての符号について $A_{g^{\pm1}}\notin E_{h^{\pm1}}$、$A_{h^{\pm1}}\notin E_{g^{\pm1}}$ なら、$N$ があって、$m\ge N$ で $g^m,h^m$ は階数 $2$ の自由群を自由に生成する。
DK17 Lemma 7.68(p. 228)である。証明の形は prop-ppl-hyperbolic と同じで、大きな冪が $E_g$ の近傍の外を $A_g$ の近くへ縮めることによる。この記事では証明しない。Titsの二者択一 の証明の最後の段は、この仮定を満たす $g,h$ を線形群の中に作ることである。
自由な半群だけなら、逆元を使わずに判定できる。
$f_1,f_2\colon X\to X$ を単射、$A\subset X$ を空でない部分集合とし、$f_1(A),f_2(A)$ は $A$ の交わらない部分集合であるとする。このとき $f_1,f_2$ は自己写像の半群の中で階数 $2$ の自由半群を生成する。すなわち、文字 $f_1,f_2$ の相異なる空でない語は相異なる写像を与える。
相異なる語 $w,w'$ が同じ写像を与えるとする。$f_i$ は単射なので、共通の接頭辞を左から消しても等しさは保たれる。消した後の語を $u,u'$ とすると、これらは相異なり(空の語は恒等写像とする)、どちらも空でないか一方だけが空である。
どちらも空でないとき、先頭の文字は異なるので $u(A)\subset f_1(A)$、$u'(A)\subset f_2(A)$(または逆)であり、$u(A)$ は空でないので $u=u'$ に反する。
$u'$ だけが空のとき、$u=\mathrm{id}$ で、先頭の文字を $f_i$ とすると $A=u(A)\subset f_i(A)\subset A$ である。よって $f_i(A)=A$ だが、もう一方の $f_{i'}(A)$ は $A$ の空でない部分集合で $f_i(A)$ と交わらないので矛盾である。$\square$
$X=\mathbb{R}$、$A=[0,1]$、$f_1(x)=x/3$、$f_2(x)=x/3+2/3$ とすると、$f_1(A)=[0,\tfrac13]$、$f_2(A)=[\tfrac23,1]$ で prop-ppl-semigroup の仮定を満たす。長さ $k$ の語の像は Cantor 集合の構成の第 $k$ 段の $2^k$ 個の区間である。一方、$f_1,f_2$ の生成する群は自由でない。$t:=f_1^{-1}f_2$ は平行移動 $x\mapsto x+2$、$f_1tf_1^{-1}$ は $x\mapsto x+2/3$ で、これらは可換なので、自由群の単位元でない語が $\mathrm{id}$ に写る。アフィン変換の群は 可解群 である。
$T$ を 木 とする。自己同型 $g$ が 双曲的 とは、$g$ で保たれる直線(軸)$A_g$ があって、$g$ がその上を $0$ でない距離だけ平行移動することをいう。$\pi_g$ を頂点から $A_g$ への最近点射影とする。$g$ は $A_g$ を保つので $\pi_g(gv)=g\pi_g(v)$ である。
$g,h$ を木 $T$ の双曲的自己同型とし、軸 $A_g,A_h$ が交わらないとする。このとき $g,h$ は階数 $2$ の自由群を自由に生成する。
$A_g$ と $A_h$ を結ぶ最短の道の端点を $a\in A_g$、$b\in A_h$ とする。$X$ を頂点の集合、$X_1:=\{v\mid\pi_g(v)\ne a\}$、$X_2:=\{v\mid\pi_h(v)\ne b\}$ とおく。$A_g$ の $a$ 以外の点は $X_1$ に入るので空でなく、$X_2$ も同様である。
$v\in X_2$ とする。$v$ から $\pi_h(v)$ へ行き、$A_h$ に沿って $b$ へ行き(この部分は $\pi_h(v)\ne b$ なので長さが正)、結ぶ道で $a$ へ行く道は折り返しをもたないので、木の中の測地線である。その最後の辺は $A_g$ に入らないので、$\pi_g(v)=a$ である。よって $X_2\cap X_1=\emptyset$ である。さらに $k\ne0$ なら $\pi_g(g^kv)=g^ka\ne a$ なので $g^k(X_2)\subset X_1$ である。対称に $h^k(X_1)\subset X_2$ である。cor-ppl-two により主張が従う。$\square$
$\mathrm{PSL}(2,\mathbb{Z})$ の構造もこの種の議論で分かる。正の無理数を $X_1$、負の無理数を $X_2$ とし、位数 $3$ の元とその平方が $X_1$ を $X_2$ へ、位数 $2$ の元が $X_2$ を $X_1$ へ打ち返すので、thm-ppl-main から $C_2\ast C_3$ の埋め込みが得られる(位数 $3$ の群があるので位数の仮定が満たされる)。実際の計算と全射性は モジュラー群 の定理「$\operatorname{PSL}_2(\mathbb{Z})$ は自由積」にある。
$r\in\mathbb{R}$ について $g_1=\begin{pmatrix}1&r\\0&1\end{pmatrix}$、$g_2=\begin{pmatrix}1&0\\r&1\end{pmatrix}$ とする。$\lvert r\rvert\ge2$ なら自由に生成する(Titsの二者択一 の例「整数行列の自由部分群」)。$\lvert r\rvert< 2$ では同じ集合での評価が成り立たず、結論は $r$ の値に強く依存する。
1:$M:=g_1g_2^{-1}=\begin{pmatrix}1-r^2&r\\-r&1\end{pmatrix}$ は行列式 $1$、跡 $2-r^2=2\cos(2\pi k/n)$ である。$0< 2\pi k/n< \pi$ なので固有値 $e^{\pm2\pi ik/n}$ は相異なり、$M$ は対角化できて $M^n=I$ である。$(ab^{-1})^n$ は $F_2$ の単位元でないので、自由に生成しない。稠密性は有理数 $k/n$ が $(0,1/2)$ で稠密なことと $\sin$ の連続性による。
2:既約語 $w\ne1$ に対し、$g_1,g_2$ を代入した行列の成分は $r$ の整数係数の多項式である($g_i^{-1}$ の成分も $-r$ と $0,1$ だからである)。$r=2$ で $w$ は単位行列に写らないので、この行列から $I$ を引いたものは $0$ でない成分をもち、$r$ の $0$ でない整数係数多項式になる。超越数はその根でない。既約語は可算個で、各語の根は有限個なので、自由に生成しない $r$ は高々可算個である。$\square$
$r=1$ は $k/n=1/6$、$r=\sqrt2$ は $k/n=1/4$ にあたる。1 の形にない自由でない $r$ もある($r=3/2$。Titsの二者択一 にある長さ 20 の語。1 の形なら跡 $2-r^2=2\cos(2\pi k/n)$ は代数的整数だが、$r=3/2$ では $-\tfrac14$ である)。$(0,2)$ の中で、自由にならない値は 1 により稠密で、自由になる値も超越数を含むので稠密である。
| 外す仮定・強める結論 | 例 | 成り立たない結論 |
|---|---|---|
| $\lvert I\rvert\ge3$ または位数 $3$ 以上(thm-ppl-main) | $X=\{1,2\}$、$\Gamma_1=\Gamma_2=\langle(1\,2)\rangle$ | $\varphi$ は単射 |
| $X_i$ が交わらない(thm-ppl-main) | $X=X_1=X_2=\mathbb{R}$、$g_1(x)=x+1$、$g_2(x)=x+2$ | $\varphi$ は単射 |
| $n\ge2$(prop-ppl-schottky) | $n=1$、$X=\{1,2\}$、$X_1^+=\{1\}$、$X_1^-=\{2\}$、$g_1=\mathrm{id}$ | 階数 $1$ の自由群を生成 |
| 固定点が相異なる(prop-ppl-hyperbolic) | 上三角の双曲型の元 $g,h$(固定点 $\infty$ を共有) | $g^m,h^m$ は自由に生成 |
| 軸が交わらない(prop-ppl-tree) | 同じ軸の $g=$ 平行移動 $1$、$h=$ 平行移動 $2$($T=\mathbb{R}$ の整数点の直線) | 自由に生成 |
| 半群から群へ結論を強める(prop-ppl-semigroup) | ex-ppl-cantor | 群として自由に生成 |
1 行目:$X_1=\{1\}$、$X_2=\{2\}$ とすると、$a=(1\,2)\in\Gamma_1$、$b=(1\,2)\in\Gamma_2$ について $a(X_2)=X_1$、$b(X_1)=X_2$ で、仮定のうち位数の条件だけが外れている。$\Gamma_1\ast\Gamma_2$ の元 $ab\ne1$ は $\varphi(ab)=\mathrm{id}$ に写る。
2 行目:$g_i^{\,k}(X)=X$ なので包含は成り立つが、$g_1,g_2$ は可換で、交換子が $\mathrm{id}$ に写る。
3 行目:$g_1(X\setminus X_1^-)=\{1\}=X_1^+$ で他の仮定は満たされるが、$g_1$ の位数は $1$ である。
4 行目:上三角行列の群は 可解群 で、Titsの二者択一 の命題「2 つの場合は排他的」により $F_2$ を含まない。$\infty$ の 1 点だけを共有していても、すべての $m$ で $g^m,h^m$ は自由に生成しない。
5 行目:$T$ は頂点を整数とする直線で、$g,h$ は整数の平行移動なので可換である。
6 行目:ex-ppl-cantor で確かめたとおりである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する