対称群の生成系を構成する
本編(note) で使用する生成系の構成法が正しく機能することを証明する.
5次対称群を例に取る. 部分群$\langle\begin{pmatrix}1&4&2&5&3\end{pmatrix}\rangle$に対して,
\begin{eqnarray}
\langle\begin{pmatrix}1&4&2&5&3\end{pmatrix}\rangle&\longrightarrow&\langle\begin{pmatrix}1&4&2\end{pmatrix},\begin{pmatrix}2&5&3\end{pmatrix}\rangle\\
&\longrightarrow&\langle\begin{pmatrix}1&4&2\end{pmatrix},\begin{pmatrix}2&5&3\end{pmatrix},\begin{pmatrix}2&5\end{pmatrix}\rangle
\end{eqnarray}
という操作の列が考えられ, 得られた生成系$\langle\begin{pmatrix}1&4&2\end{pmatrix},\begin{pmatrix}2&5&3\end{pmatrix},\begin{pmatrix}2&5\end{pmatrix}\rangle$は生成元として互換を含んでいるため$S_5$と等しいことを主張している.
証明の準備としていくつかの補題を示す.
任意の置換は有限個の互換の積で表せるのだから, 任意の$i,j$で$\begin{pmatrix}a_{i}&a_{j}\end{pmatrix}$が生成できることを示せばよい.
$1\leq i< n$と$i< j$について, $i$と$j$の差で帰納法を用いることにより証明する.
$j-i=1$のとき, $\begin{pmatrix}a_{i}&a_{j}\end{pmatrix}$は$\begin{pmatrix}a_{i}&a_{i+1}\end{pmatrix}$として既に生成系の中に存在する.
$j-i=k$のとき$\begin{pmatrix}a_{i}&a_{j}\end{pmatrix}$が与えられた生成元の積で表せたとすると,
$j-i=k+1$のとき,
\begin{eqnarray}
\begin{pmatrix}a_{i}&a_{j}\end{pmatrix}=\begin{pmatrix}a_{i}&a_{i+k+1}\end{pmatrix}=\begin{pmatrix}a_{i}&a_{i+1}\end{pmatrix}\begin{pmatrix}a_{i+1}&a_{i+k+1}\end{pmatrix}\begin{pmatrix}a_{i}&a_{i+1}\end{pmatrix}
\end{eqnarray}
$\begin{pmatrix}a_{i+1}&a_{i+k+1}\end{pmatrix}$は仮定から与えられた生成元の積で表せるため, $\begin{pmatrix}a_{i}&a_{i+k+1}\end{pmatrix}$も生成系に含まれる.
よって, 任意の互換が生成できるため, $\begin{pmatrix}a_{1}&a_{2}\end{pmatrix},\begin{pmatrix}a_{2}&a_{3}\end{pmatrix},\cdots,\begin{pmatrix}a_{n-1}&a_{n}\end{pmatrix}$は$S_n$全体を生成する.
$p\neq i$を取り,
・$1\leq p\leq n-i-1$のとき,
\begin{eqnarray}
{\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}}^{p}\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}{\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}}^{-p}=\begin{pmatrix}a_{i+p}&a_{i+p+1}\end{pmatrix}
\end{eqnarray}
であるから$p$を$1,2,\cdots,n-i-1$と動かせば$\begin{pmatrix}a_{i+1}&a_{i+2}\end{pmatrix},\begin{pmatrix}a_{i+2}&a_{i+3}\end{pmatrix},\cdots,\begin{pmatrix}a_{n-1}&a_{n}\end{pmatrix}$が得られる.
・$n-i+1\leq p\leq n-1$のとき,
\begin{eqnarray}
{\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}}^{p}\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}{\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}}^{-p}=\begin{pmatrix}a_{i+p-n}&a_{i+p-n+1}\end{pmatrix}
\end{eqnarray}
であるから$p$を$n-i+1,n-i+2,\cdots,n-1$と動かせば$\begin{pmatrix}a_{1}&a_{2}\end{pmatrix},\begin{pmatrix}a_{2}&a_{3}\end{pmatrix},\cdots,\begin{pmatrix}a_{i-1}&a_{i}\end{pmatrix}$が得られる.
以上より, $\begin{pmatrix}a_{1}&a_{2}\end{pmatrix},\begin{pmatrix}a_{2}&a_{3}\end{pmatrix},\cdots,\begin{pmatrix}a_{n-1}&a_{n}\end{pmatrix}$が得られ, 補題1からこれらの生成系は$S_n$に等しいため, $\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}$と$\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}\hspace{2mm}(1\leq i< n)$は$S_n$全体を生成する.
以上の補題から最初の定理が示される.
1. ある生成元の一部を切り抜いて, 生成系に加えることができる. 即ち, 生成元$\begin{pmatrix}a_i&a_{i+1}&\cdots&a_{j}\end{pmatrix}\hspace{2mm}(0< j-i< n)$を持つ生成系$S$に対して, $i< k< l< j$として$\begin{pmatrix}a_k&a_{k+1}&\cdots&a_{l}\end{pmatrix}$を生成系に加え,
\begin{eqnarray} \langle S,\begin{pmatrix}a_k&a_{k+1}&\cdots&a_{l}\end{pmatrix} \rangle \end{eqnarray}
とできる. ただし, $\begin{eqnarray}\langle S,\begin{pmatrix}a_k&a_{k+1}&\cdots&a_{l}\end{pmatrix}\rangle\end{eqnarray}$は$\begin{eqnarray}S=\langle\sigma_1,\sigma_2,\cdots,\sigma_m\rangle\end{eqnarray}$に対して$\begin{eqnarray}\langle \sigma_1,\sigma_2,\cdots,\sigma_m,\begin{pmatrix}a_k&a_{k+1}&\cdots&a_{l}\end{pmatrix}\rangle\end{eqnarray}$を表す.
2. ある生成元を任意の位置で切り取ることができる. 即ち, 生成元$\sigma=\begin{pmatrix}a_i&a_{i+1}&\cdots&a_{j}\end{pmatrix}\hspace{2mm}(0< j-i< n)$を持つ生成系$\begin{eqnarray}S=\langle\sigma_1,\sigma_2,\cdots,\sigma,\cdots\sigma_m\rangle\end{eqnarray}$に対して,
\begin{eqnarray} \langle\sigma_1,\sigma_2,\cdots,\begin{pmatrix}a_i&a_{i+1}&\cdots&a_t\end{pmatrix},\begin{pmatrix}a_t&a_{t+1}&\cdots&a_j\end{pmatrix},\cdots\sigma_m\rangle\hspace{2mm}(i< t< j) \end{eqnarray}
とできる.
$S_n$における長さ$n$の巡回置換$\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}$の生成系$\begin{eqnarray}\langle\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}\rangle\end{eqnarray}$から上記の操作1または2を順繰りに施し, 生成元に互換が現れれば, その生成系は$S_n$と等しい.
以下では操作1を切り抜き, 操作2を切り取り, 切り抜きと切り取りによって得られた互換を生成元として含む生成系を終系と呼ぶ. また, 巡回置換$\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}$を順序対$\langle a_1,a_2,\cdots,a_n\rangle$と見做すと, 切り抜きと切り取りの前後で順序関係は保存され, $a_i,a_{i+1}$がともに含まれる終系の置換を順序対と見做したとき, $a_i< a_k< a_{i+1}$を満たす$a_k$は存在しないものとする.
切り取りと切り抜きの定義から, 終系において, 任意の$a_i$を含む置換が必ず存在し, $i\neq 1,n$かつ$a_i$がその置換において端に位置するのなら, $a_i$を含む置換が2つ以上存在する. ただし, $a_i$が置換の端に位置するとは, $a_i$を含む置換を順序対と見做した際に, $a_k< a_i$または$a_i< a_k$なる$a_k$が存在しないということである. 以上のことから, 終系における互換は$\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}$の形をしており, $n\geq 3$より$i,i+1$が同時に$1$または$n$にならないため, $a_i,a_{i+1}$の少なくとも一方は$\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}$以外の置換に含まれていることが分かる.
ここで, $a_i$が他の置換$\sigma$に含まれているとする.
(1) $a_i$が$\sigma$の端に位置しているとき
$\sigma=\begin{pmatrix}a_k&a_{k+1}&\cdots&a_i\end{pmatrix}$として,
\begin{eqnarray}
{\begin{pmatrix}a_k&a_{k+1}&\cdots&a_i\end{pmatrix}}^{q}\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}{\begin{pmatrix}a_k&a_{k+1}&\cdots&a_i\end{pmatrix}}^{-q}=\begin{pmatrix}a_{k+q-1}&a_{i+1}\end{pmatrix}
\end{eqnarray}
で$q$を$1,2,\cdots,i-k$と動かすと$\begin{pmatrix}a_k&a_{i+1}\end{pmatrix},\begin{pmatrix}a_{k+1}&a_{i+1}\end{pmatrix},\cdots,\begin{pmatrix}a_{i-1}&a_{i+1}\end{pmatrix}$が得られる. さらに$\begin{pmatrix}a_{k+q-1}&a_{i+1}\end{pmatrix}$と$\begin{pmatrix}a_{k+q}&a_{i+1}\end{pmatrix}$から
\begin{eqnarray}
\begin{pmatrix}a_{k+q-1}&a_{i+1}\end{pmatrix}\begin{pmatrix}a_{k+q}&a_{i+1}\end{pmatrix}\begin{pmatrix}a_{k+q-1}&a_{i+1}\end{pmatrix}=\begin{pmatrix}a_{k+q-1}&a_{k+q}\end{pmatrix}
\end{eqnarray}
のように隣接互換が得られる.
(2) $a_i$が$\sigma$の端に位置していないとき
$\sigma=\begin{pmatrix}a_k&a_{k+1}&\cdots&a_l\end{pmatrix}$とすると, $a_{i+1}$も$\sigma$に含まれているため, 補題2から$\begin{pmatrix}a_i&a_{i+1}\end{pmatrix}$と$\sigma$の積で隣接互換$\begin{pmatrix}a_k&a_{k+1}\end{pmatrix},\begin{pmatrix}a_{k+1}&a_{k+2}\end{pmatrix},\cdots,\begin{pmatrix}a_{l-1}&a_{l}\end{pmatrix}$を表すことができる.
この議論は$a_{i+1}$が他の置換に含まれているとしても同様に進み, (1),(2)の操作で得られた隣接互換についてさらに(1),(2)の操作を行うといった具合で, 終系においては, 繰り返し巡回置換を隣接互換により分解していくことができるため, 補題1から, 終系は$S_n$に等しいと言える.
