Schreier–Simsのアルゴリズム(Schreier–Sims algorithm)とは、いくつかの置換が生成する置換群について、点の固定部分群の列と各段の軌道の代表元の表を作り、群の位数と置換の所属の判定を可能にする手順である。基底と強生成系を求めるもので、Schreier の補題により固定部分群の生成元を代表元から作り、それを篩にかけて欠けた生成元を補う。Knuth の定式化では正しさは表が積で閉じることから示され、次数 $n$、生成元 $m$ 個の群について $O(n^5\log n+mn^2)$ 回の基本操作で終わる。
前提知識: 対称群, 群の作用, 剰余類, Lagrangeの定理
Schreier–Simsのアルゴリズム(Schreier–Sims algorithm)は、$n$ 個の点の 置換 をいくつか与えたとき、それらが生成する置換群 $G$ の「点の固定部分群の列」と各段の代表元の表を作る手順である。表ができると、$G$ の位数は各段の表の大きさの積として読め、任意の置換が $G$ に属するかは、表の代表元で 1 点ずつ戻していく操作で判定できる。Sims が 1967 年の会議で概略を示し、1971 年に詳しく述べた(Knu91 §9)。名前の Schreier は、部分群の生成元を剰余類の代表元から作る Schreier の補題(lem-ss-schreier)による。
$G$ の元は最大で $n!$ 個あるので、元を並べる方法は $n$ が少し大きくなると使えない。この手順は、生成元の個数を $m$ とすると $n$ と $m$ の多項式の時間で終わる。Sims のもとの記述からは最悪の場合の多項式の上界は明らかでなく、Furst・Hopcroft・Luks が 1980 年に $O(n^6)$ の上界を与えた(Knu91 §9)。
この記事では、基底と強生成系(def-ss-bsgs)と、表による位数と所属の判定(prop-ss-sift)を述べ、Schreier の補題から強生成系の判定法(thm-ss-criterion)を導く。主定理として、Knuth の形の手順(def-ss-algorithm)が正しい表を作ること(thm-ss-correct)と、多項式時間で終わること(thm-ss-time)を証明する。
以下 $\Omega=\{1,\dots,n\}$ とし、置換は右から作用させる:点 $i$ の $g$ による像を $i^g$ と書き、積 $gh$ は「$g$ のあと $h$」、すなわち $i^{gh}=(i^g)^h$ とする。$S_n$ を $\Omega$ の 対称群、$G\le S_n$ とする。点 $\beta$ の固定部分群を $G_\beta=\{g\in G\mid\beta^g=\beta\}$、軌道を $\beta^G=\{\beta^g\mid g\in G\}$ と書く。軌道の点と右剰余類は $G_\beta g\mapsto\beta^g$ で 1 対 1 に対応するので、$[G:G_\beta]=\lvert\beta^G\rvert$ である(群の作用)。
$G\le S_n$ とする。
$G^{(i+1)}$ は $G^{(i)}$ の中での点 $\beta_i$ の固定部分群なので、$[G^{(i)}:G^{(i+1)}]=\lvert\Delta^{(i)}\rvert$ で、$u^{(i)}_\delta$($\delta\in\Delta^{(i)}$)は $G^{(i+1)}$ の右剰余類の代表元である。
$B$ を $G$ の基底とし、各段の代表元が与えられているとする。
1:$g\in G^{(i)}$ について $\delta:=\beta_i^g\in\Delta^{(i)}$ とおくと、$\beta_i^{g(u^{(i)}_\delta)^{-1}}=\beta_i$ なので $g(u^{(i)}_\delta)^{-1}\in G^{(i+1)}$ である。これを $i=1,\dots,k$ と繰り返すと $G^{(k+1)}=1$ に着き、表示が得られる。一意性は、$\delta_1=\beta_1^g$ が $g$ で決まり($u^{(i)}$ は $i\ge2$ なら $\beta_1$ を固定する)、そのあと $G^{(2)}$ で同じ議論をすることによる。
2:$\pi\in G$ なら、1 の証明の操作そのもので、各段で $\delta\in\Delta^{(i)}$ であり、最後に $1$ が残る。逆に最後まで進んで $\pi'$ が残ったとすると $\pi=\pi'u^{(k)}\cdots u^{(1)}$ の形で、$\pi'$ は $\beta_1,\dots,\beta_k$ を固定する。$\pi'=1$ なら $\pi\in G$ である。$\pi'\ne1$ なら、$\pi'\in G$ とすると基底の定義に反するので $\pi'\notin G$、よって $\pi\notin G$ である。$\square$
有限群 $H$ が集合 $Y$ で生成され、$K\le H$ とする。$K$ の右剰余類の代表元の集合 $R$ を $1\in R$ となるように選び、$h\in H$ について $Kh$ に属する $R$ の元を $\overline{h}$ と書く。このとき $K$ は Schreier 生成元
$$
r\,y\,\bigl(\overline{ry}\bigr)^{-1}\qquad(r\in R,\ y\in Y)
$$
で生成される。
$K\overline{ry}=Kry$ なので Schreier 生成元は $K$ に入る。逆に $h\in K$ とする。$H$ は有限なので $y^{-1}=y^{\operatorname{ord}y-1}$ であり、$h=y_1\cdots y_m$($y_j\in Y$)と逆元なしで書ける。$r_0:=1$、$r_j:=\overline{r_{j-1}y_j}$ とおくと、$Kr_j=Kr_{j-1}y_j=\cdots=Ky_1\cdots y_j$ なので、$r_m=\overline{h}=1$ である。よって
$$
h=\bigl(r_0y_1r_1^{-1}\bigr)\bigl(r_1y_2r_2^{-1}\bigr)\cdots\bigl(r_{m-1}y_mr_m^{-1}\bigr)
$$
は Schreier 生成元の積である。$\square$
自由群の部分群についての同じ構成は、Nielsen–Schreierの定理 の命題「Schreier 生成元は部分群を生成する」にある。置換群で $K=H_\beta$ のときは、右剰余類と軌道の点が対応するので、$R$ として軌道の各点 $\delta$ に $\beta^{u_\delta}=\delta$ となる $u_\delta$ をとれば、Schreier 生成元は $u_\delta\,y\,u_{\delta^y}^{-1}$ になる。
$X\subseteq S_n$、$G=\langle X\rangle$ とし、点の列 $B=(\beta_1,\dots,\beta_k)$ をとる。$X^{(i)}$ を $\beta_1,\dots,\beta_{i-1}$ をすべて固定する $X$ の元の集合とし、$H^{(i)}:=\langle X^{(i)}\rangle$($H^{(1)}=G$、$H^{(k+1)}:=1$)とおく。このとき、次は同値である。
つねに $H^{(i+1)}\le(H^{(i)})_{\beta_i}$ である($X^{(i+1)}$ の元は $\beta_i$ を固定する)。
1 ⇒ 2:$G^{(i)}$ は $\beta_1,\dots,\beta_{i-1}$ を固定する $G$ の元の全体なので、$X\cap G^{(i)}=X^{(i)}$ である。強生成系の定義から $H^{(i)}=G^{(i)}$ で、$(H^{(i)})_{\beta_i}=G^{(i+1)}=H^{(i+1)}$($i=k$ では基底の定義から $1$)である。
2 ⇒ 1:$i$ についての帰納法で $H^{(i)}=G^{(i)}$ を示す。$i=1$ では両辺が $G$ である。$H^{(i)}=G^{(i)}$ なら $G^{(i+1)}=(G^{(i)})_{\beta_i}=(H^{(i)})_{\beta_i}=H^{(i+1)}$ である。$i=k+1$ で $G^{(k+1)}=1$ なので $B$ は基底で、$X\cap G^{(i)}=X^{(i)}$ が $G^{(i)}$ を生成する。
2 ⇔ 3:lem-ss-schreier を $H=H^{(i)}$、$Y=X^{(i)}$、$K=(H^{(i)})_{\beta_i}$ に当てると、$K$ は Schreier 生成元で生成される。それらがすべて $H^{(i+1)}$ に入れば $K\le H^{(i+1)}$ で、逆の包含と合わせて 2 が成り立つ。逆に 2 なら Schreier 生成元は $K=H^{(i+1)}$ に入る。$\square$
3 の確かめは、$i=k$ から $i=1$ へ下から順に行えば、$i+1$ 段より下がすでに強生成系になっているので、$H^{(i+1)}$ への所属を prop-ss-sift の篩で判定できる。篩で $1$ にならない置換が残れば、それを $X$ に加えて $H^{(i+1)}$ を大きくし、やり直す。これが Schreier–Sims のアルゴリズムの骨組みである。
以下、基底を $(n,n-1,\dots,2)$ に固定した Knuth の定式化(Knu91 §1–§2)で、手順と正しさを述べる。$S_{(k)}$ を $k+1,\dots,n$ をすべて固定する置換の全体($S_k$ と同一視できる)とする。
2 の同値は、$\Gamma(k)=\Gamma(k-1)\Sigma(k)$ で、$\Gamma(k-1)$ の元が $k$ を固定するので $\gamma\sigma_{kj'}$ が $k$ を $j'$ に写すことによる。$B_k$ で試す $\sigma_{kj}\tau\sigma_{kj'}^{-1}$($j'=k^{\sigma_{kj}\tau}$)は、$\Sigma(k)$ を代表元とする Schreier 生成元にほかならない(lem-ss-schreier)。
$X\subseteq S_n$ を有限集合、$G=\langle X\rangle$ とする。def-ss-algorithm の全体の手順は有限回で終わり、終わったとき次が成り立つ。
不変な性質。手順のどの時点でも、(a) $\sigma_{kj}\in\langle T(k)\rangle$、(b) $T(k-1)\subseteq\langle T(k)\rangle$ が成り立つ。$\sigma_{kj}$ が置かれるのは $B_k(\tau)$ の中で、$\tau=\sigma\tau'$($\sigma\in\Sigma(k)$、$\tau'\in T(k)$)は帰納的に $\langle T(k)\rangle$ に入る。$A_{k-1}$ に渡す $\tau\sigma_{kj}^{-1}$ も $\langle T(k)\rangle$ に入り、$k^{\tau\sigma_{kj}^{-1}}=k$ なので $S_{(k-1)}$ に入る。(a)(b) と $k$ についての帰納法から $\Gamma(k)=\Gamma(k-1)\Sigma(k)\subseteq\langle T(k)\rangle$ である。
手順の働き。$k$ についての帰納法で次を示す:表が $k$ 次まで整っているときに $A_k(\pi)$ を呼ぶと、終わったとき表は $k$ 次まで整っていて $\pi\in\Gamma(k)$ である。$B_k(\tau)$($\tau\in\langle T(k)\rangle$)を $k-1$ 次まで整った表で呼ぶと、終わったとき表は $k-1$ 次まで整っていて $\tau\in\Gamma(k)$ である。
$B_k$:$\sigma_{kj}:=\tau$ と置いたなら $\tau=1\cdot\sigma_{kj}\in\Gamma(k)$。$\tau\sigma_{kj}^{-1}\in\Gamma(k-1)$ なら $\tau\in\Gamma(k-1)\Sigma(k)=\Gamma(k)$。$A_{k-1}(\tau\sigma_{kj}^{-1})$ を行ったなら、帰納法の仮定から表は $k-1$ 次まで整い、$\tau\sigma_{kj}^{-1}\in\Gamma(k-1)$ となるので同じである。$A_k$ の中で動くのは $k$ 段以下だけである。
$A_k$:対の処理が終わった時点で、表は $k-1$ 次まで整っていて、すべての $\sigma\in\Sigma(k)$、$\tau\in T(k)$ について $\sigma\tau\in\Gamma(k)$ である(集合は増えるだけなので、一度入った元は入ったままである)。$\Gamma(k)$ が積で閉じることを示す。$\gamma\sigma\in\Gamma(k)$($\gamma\in\Gamma(k-1)$、$\sigma\in\Sigma(k)$)と $\tau\in\Gamma(k)\subseteq\langle T(k)\rangle$ をとり、有限群なので $\tau=\tau_1\cdots\tau_r$($\tau_i\in T(k)$)と書く。$\sigma\tau_1\in\Gamma(k)$ なので $\sigma\tau_1=\gamma_1\sigma_1$($\gamma_1\in\Gamma(k-1)$、$\sigma_1\in\Sigma(k)$)と書け、同様に $\sigma_1\tau_2=\gamma_2\sigma_2$、…と続けると
$$
\gamma\sigma\tau=(\gamma\gamma_1\cdots\gamma_r)\,\sigma_r
$$
となる。$\Gamma(k-1)$ は群なので右辺は $\Gamma(k-1)\Sigma(k)=\Gamma(k)$ に入る。よって有限集合 $\Gamma(k)$ は積で閉じた部分群で、$\tau\in T(k)$ について $\tau=1\cdot\tau\in\Gamma(k)$ だから $\langle T(k)\rangle\subseteq\Gamma(k)$ となり、上の包含と合わせて $\Gamma(k)=\langle T(k)\rangle$ である。
停止。$A_k(\pi)$ を呼ぶたびに $\pi\notin\Gamma(k)=\langle T(k)\rangle$ を加えるので、$\langle T(k)\rangle$ は真に大きくなる。$S_{(k)}$ の部分群の真の増大列の長さは有限なので $A_k$ の呼び出しは有限回で、各 $A_k$ の対の処理も $s(k)\le k$ と $t(k)$ で抑えられる。
結論。終わったとき、飛ばした生成元は $\Gamma(n)$ に入っていたので $G\subseteq\Gamma(n)=\langle T(n)\rangle\subseteq G$ である。$\gamma=\tau_1\cdots\tau_n\in\Gamma(n)$($\tau_i\in\Sigma(i)$)では $n^\gamma=n^{\tau_n}$ なので $\tau_n$ は $\gamma$ で決まり、帰納的に表示は一意である。よって $\lvert G\rvert=\prod s(k)$ で、$g\in G\cap S_{(k)}$ では $\tau_n=\cdots=\tau_{k+1}=1$ となるので $G\cap S_{(k)}=\Gamma(k)$ である。所属の判定の正しさは $\Gamma(n)=G$ と def-ss-algorithm の 2 の同値による。$\square$
置換の積と逆元を $O(n)$ 回の基本操作で計算するとき、$m$ 個の生成元をもつ $G\le S_n$ について、全体の手順は $O(n^5\log n+mn^2)$ 回の基本操作で終わる。
$S_{(k)}$ の部分群の真の増大列 $H_0< H_1<\cdots< H_t$ では、Lagrangeの定理 により $\lvert H_{i}\rvert\ge2\lvert H_{i-1}\rvert$ なので $2^t\le k!$、すなわち $t\le\log_2k!\le k\log_2k$ である。$A_k$ の呼び出しごとに $\langle T(k)\rangle$ は真に大きくなるので $t(k)\le k\log_2k$ である。各対は 1 度しか扱わないので、$B_k$ の呼び出しは $s(k)t(k)\le k^2\log_2k$ 回である。
$B_k$ 1 回の手間は、積 $\sigma\tau$ と $\tau\sigma_{kj}^{-1}$ の計算に $O(k)$、$\Gamma(k-1)$ への所属の判定に、$k-1$ 段のそれぞれで積 1 回、合わせて $O(k^2)$ である($A_{k-1}$ の中の手間はその段の勘定に入れる)。よって第 $k$ 段の手間は $O(k^4\log k)$ で、$k\le n$ について足して $O(n^5\log n)$ である。生成元を 1 つずつ $\Gamma(n)$ に入るか判定する手間が $O(mn^2)$ である。$\square$
Babai は $S_k$ の部分群の真の増大列の長さが $2k-3$ 以下($k\ge2$)であることを示しており、これを使うと $t(k)=O(k)$ となって上界は $O(n^5+mn^2)$ になる(Knu91 §4。この記事では証明しない)。$G$ の位数 $g$ を使ったより細かい上界も同 §8 にある。
正方形の頂点 $1,2,3,4$ に働く $G=\langle r,f\rangle$、$r=(1\,2\,3\,4)$、$f=(1\,3)$ を考える。$A_4(r)$ は $4^{r}=1$ から $\sigma_{41}:=r$ を置き、続く対 $(\sigma_{41},r),(\sigma_{42},r)$ から $\sigma_{42}:=r^2$、$\sigma_{43}:=r^3$ を置く。$f$ は $4$ を固定し、$f\notin\Gamma(3)=\{1\}$ なので $A_4(f)$ の中で $A_3(f)$ が呼ばれ、$\sigma_{31}:=f$ となる。終わったとき
$$
s(4)=4,\quad s(3)=2,\quad s(2)=s(1)=1,\qquad\lvert G\rvert=8
$$
で、$T(4)=\{r,f\}$、$T(3)=\{f\}$ である。$G\cap S_{(3)}=\{1,(1\,3)\}$ は対角線 $2$–$4$ についての折り返しである。
$G=S_3=\langle r,f\rangle$、$r=(1\,2\,3)$、$f=(1\,3)$ とし、基底を $(3,2)$ とする。$r$ も $f$ も $3$ を動かすので $X^{(2)}=\emptyset$、$H^{(2)}=1$ だが、$G_3=\{1,(1\,2)\}$ なので thm-ss-criterion の 2 が成り立たず、$\{r,f\}$ は強生成系でない。手順では、$\sigma_{31}=r$、$\sigma_{32}=r^2$ を置いたあと、$f$ を篩にかけると $f\sigma_{31}^{-1}=(1\,3)(1\,3\,2)=(1\,2)$ が残り($1\mapsto3\mapsto2$、$2\mapsto1$)、これが $T(2)$ に加わって $\sigma_{21}=(1\,2)$ となる。Schreier 生成元が、生成系に欠けていた $G_3$ の生成元を補ったのである。$\lvert G\rvert=3\cdot2\cdot1=6$ である。
ex-ss-d4 の $G$ で、点の列 $(1,3)$ は基底でない。$r^2=(1\,3)(2\,4)$ なので $(2\,4)=r^2f$ は $G$ の元で、$1$ と $3$ を固定するからである。基底は $(1,2)$ のように選び直す必要がある。$(1,3)$ を基底と思って prop-ss-sift を使うと、位数は $\lvert1^G\rvert\cdot\lvert3^{G_1}\rvert=4\cdot1=4$ と読めてしまい、$G$ の元 $(2\,4)$ は篩で $1$ にならないので $G$ に属さないと誤って判定される。
$n=14$ で、巡回置換の積 $g=(1\,2\,3\,4\,5\,6\,7\,14)(8\,9\,10\,13)(11\,12)$ が生成する位数 $8$ の巡回群では、表は $s(14)=8$ のほかすべて $1$ になる。点 $12$ と $14$ の番号を入れ替えた共役な置換では、$s(14)=s(13)=s(12)=2$ と 3 段に分かれる(Knu91 §5)。位数はどちらも $8$ だが、所属の判定の手間は変わる。
| 主張 | 反例 | 満たされない条件 |
|---|---|---|
| 生成系はどの基底についても強生成系である | $S_3=\langle(1\,2\,3),(1\,3)\rangle$(ex-ss-not-strong) | $X\cap G^{(i)}$ が $G^{(i)}$ を生成する |
| 置換群の点の列ならどれでも基底になる | $D_4$ と $(1,3)$(ex-ss-not-base) | 列の各点を固定する元は単位元だけ |
| 表の段の大きさは群だけで決まる | ex-ss-labels | 点の番号(基底の選び方)に依る |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する