ルービックキューブの群論的構造：半直積と wreath product

前回までの記事で、ルービックキューブ群の位数が $43,252,003,274,489,856,000$ であることを導出した。本記事では、この群の内部構造を半直積と wreath product（花冠積）の言葉で精密に記述する。位数を数えるだけでは見えない、群の「骨格」を明らかにするのが目標だ。

直積と半直積の復習

2 つの群 $N$ と $H$ が与えられたとき、直積 $N\times H$ は元の組 $(n,h)$ に成分ごとの積

$$(n_1,h_1)(n_2,h_2)=(n_1{n}_2,h_1{h}_2)$$

を入れる構成だ。$N$ と $H$ は互いに干渉しない。

半直積 $N{⋊}_{\phi }H$ はこれを一般化する。準同型 $\phi :H\to \text{Aut}(N)$ が与えられたとき、積を

$$(n_1,h_1)(n_2,h_2)=(n_1\cdot \phi (h_1)(n_2),h_1{h}_2)$$

と定める。$H$ が $N$ の元を「並べ替える」ことが許される点が直積との本質的な違いだ。

ルービックキューブ群では、置換（位置の入れ替え）が向き（ツイスト・フリップ）に作用する。これはまさに半直積の構造だ。

コーナー群の構造

コーナーの状態は、位置置換 $\sigma \in S_8$ と向きベクトル $\mathbf{x}=(x_1,\dots ,x_8)\in {\mathbb{Z}}_3^8$ の組 $(\mathbf{x},\sigma )$ で表される。ただしツイスト制約 $\sum x_i\equiv 0(\mathrm{mod}3)$ があるから、実際には $\mathbf{x}\in ({\mathbb{Z}}_3{)}^7$（最後の成分は他から決まる）と考えてよい。

2 つのコーナー操作 $({\mathbf{x}}_1,{\sigma }_1)$ と $({\mathbf{x}}_2,{\sigma }_2)$ の積は

$$({\mathbf{x}}_1,{\sigma }_1)({\mathbf{x}}_2,{\sigma }_2)=({\mathbf{x}}_1+{\sigma }_1({\mathbf{x}}_2),{\sigma }_1{\sigma }_2)$$

で与えられる。ここで ${\sigma }_1({\mathbf{x}}_2)$ とは、ベクトル ${\mathbf{x}}_2$ の成分を置換 ${\sigma }_1$ で並べ替える操作だ。具体的には、${\sigma }_1({\mathbf{x}}_2)$ の第 $i$ 成分は $({\mathbf{x}}_2{)}_{{\sigma }_1^{-1}(i)}$ である。

この積の構造は、$\phi :S_8\to \text{Aut}(({\mathbb{Z}}_3{)}^7)$ を「成分の並べ替え」として定めた半直積そのものだ。

$$C=({\mathbb{Z}}_3{)}^7{⋊}_{\phi }{S}_8$$

具体例で確認する。 R 操作のコーナーへの作用を考えよう。R はコーナー置換 $(1485)$ とツイスト変化 $(+1,0,0,+2,+2,0,0,+1)$ を引き起こす。次に U 操作を施すと、コーナー置換 $(1234)$ でツイスト変化なし。

$RU$ の合成では、まず R のツイスト変化を施し、次に U の置換がツイストベクトルを並べ替えてから U のツイスト変化（ゼロ）を加える。結果として、R で生じたツイストは U の置換によって別の位置に「運ばれる」。これが ${\sigma }_1({\mathbf{x}}_2)$ の意味するところだ。

wreath product（花冠積）

半直積 $({\mathbb{Z}}_3{)}^8⋊S_8$ には特別な名前がつく。一般に、群 $A$ と対称群 $S_n$ に対し、

$$A\wr S_n=A^n⋊S_n$$

を $A$ と $S_n$ の wreath product（花冠積） と呼ぶ。$S_n$ は $A^n$ の成分を置換する標準的な作用を持つ。

コーナーの場合、制約なしでは ${\mathbb{Z}}_3\wr S_8=({\mathbb{Z}}_3{)}^8⋊S_8$ だが、ツイスト制約により向きの自由度が 1 つ減り、実際のコーナー群は

$$C=\ker \left(\sum :({\mathbb{Z}}_3{)}^8\to {\mathbb{Z}}_3\right)⋊S_8\cong ({\mathbb{Z}}_3{)}^7⋊S_8$$

となる。ここで $\ker (\sum )$ は総和が 0 になるベクトル全体の部分群だ。

エッジ群の構造

エッジについても全く同様の議論ができる。エッジの状態は $(\mathbf{y},\tau )$ で表され、$\tau \in S_{12}$ は位置置換、$\mathbf{y}\in ({\mathbb{Z}}_2{)}^{12}$ は向きベクトルだ。フリップ制約 $\sum y_i\equiv 0(\mathrm{mod}2)$ により、

$$E=({\mathbb{Z}}_2{)}^{11}⋊S_{12}$$

が得られる。これは ${\mathbb{Z}}_2\wr S_{12}$ の制約付き部分群だ。

パリティ制約と全体の構造

コーナー群 $C$ とエッジ群 $E$ が独立に動けるなら、全体は直積 $C\times E$ になる。しかし、パリティ制約 $\text{sgn}(\sigma )=\text{sgn}(\tau )$ がこれを許さない。

パリティ制約の意味を代数的に整理しよう。写像 $\Phi :C\times E\to {\mathbb{Z}}_2$ を

$$\Phi ((\mathbf{x},\sigma ),(\mathbf{y},\tau ))=\text{sgn}(\sigma )\oplus \text{sgn}(\tau )$$

で定めると、$\Phi$ は準同型であり、ルービックキューブ群 $G$ は

$$G=\ker (\Phi )\le C\times E$$

として実現される。$\ker (\Phi )$ は $\text{sgn}(\sigma )=\text{sgn}(\tau )$ を満たす元全体からなる指数 2 の部分群だ。

別の見方をすれば、符号写像 $\text{sgn}:S_8\to {\mathbb{Z}}_2$ と $\text{sgn}:S_{12}\to {\mathbb{Z}}_2$ を用いて、ファイバー積

$$G\cong C{\times }_{{\mathbb{Z}}_2}E$$

と表せる。ここで ${\times }_{{\mathbb{Z}}_2}$ は、両方の符号写像が一致する元のみを取り出す操作だ。

全体像のまとめ

以上を組み合わせると、ルービックキューブ群 $G$ の完全な代数的記述が得られる。

$$G=\left\{((\mathbf{x},\sigma ),(\mathbf{y},\tau ))\in C\times E\mid \text{sgn}(\sigma )=\text{sgn}(\tau )\right\}$$

ここで

$$C=({\mathbb{Z}}_3{)}^7⋊S_8,E=({\mathbb{Z}}_2{)}^{11}⋊S_{12}$$

であり、各半直積における $S_n$ の作用は成分の並べ替えである。

正規部分群の連鎖

$G$ の正規部分群をいくつか特定しておく。これは後の記事で可解性を議論する際に重要になる。

向き部分群 $N=({\mathbb{Z}}_3{)}^7\times ({\mathbb{Z}}_2{)}^{11}$ は $G$ の正規部分群だ。なぜなら、任意の $g=((\mathbf{x},\sigma ),(\mathbf{y},\tau ))\in G$ と $n=((\mathbf{a},\text{id}),(\mathbf{b},\text{id}))\in N$ に対し、

$$gn{g}^{-1}=((\sigma (\mathbf{a}),\text{id}),(\tau (\mathbf{b}),\text{id}))\in N$$

が成り立つからだ。共役をとっても置換部分は恒等置換のままで、向きベクトルが並べ替えられるだけである。

商群 $G/N$ を考えると、

$$G/N\cong \{(\sigma ,\tau )\in S_8\times S_{12}\mid \text{sgn}(\sigma )=\text{sgn}(\tau )\}$$

となる。この群の位数は

$$|G/N|=\frac{|S_8|\times |S_{12}|}{2}=\frac{8!\times 12!}{2}=\frac{40,320\times 479,001,600}{2}$$

であり、$G$ の正規列

$$\{e\}⊴N⊴G$$

が得られる。

wreath product の普遍性

wreath product がルービックキューブに限らず広く現れる構造であることを確認しておく。一般に、$n$ 個の同一な対象があり、それぞれが内部状態を持ち、かつ対象どうしの入れ替えが許される場合、その対称性は wreath product で記述される。

位数の再導出

群構造から位数を再計算して整合性を確認する。

$$|C|=|({\mathbb{Z}}_3{)}^7|\times |S_8|=3^7\times 8!=2,187\times 40,320=88,179,840$$

$$|E|=|({\mathbb{Z}}_2{)}^{11}|\times |S_{12}|=2^{11}\times 12!=2,048\times 479,001,600=980,995,276,800$$

パリティ制約は $C\times E$ の指数 2 部分群を取ることに相当するから、

$$|G|=\frac{|C|\times |E|}{2}=\frac{88,179,840\times 980,995,276,800}{2}$$

C = 3**7 * 40320          # 88179840
E = 2**11 * 479001600     # 980995276800
G = C * E // 2
print(f"|G| = {G:,}")
# |G| = 43,252,003,274,489,856,000

前回導出した値と完全に一致する。群構造の記述と位数の計算が整合していることが確認できた。

半直積の計算規則

最後に、半直積における逆元と共役の公式をまとめておく。これらは解法アルゴリズムの理解に直結する。

$(\mathbf{x},\sigma )\in ({\mathbb{Z}}_3{)}^7⋊S_8$ の逆元は

$$(\mathbf{x},\sigma {)}^{-1}=(-{\sigma }^{-1}(\mathbf{x}),{\sigma }^{-1})$$

で与えられる。向きベクトルを反転させるだけでなく、逆置換で並べ替える必要がある点に注意しよう。

共役 $(\mathbf{a},\alpha )(\mathbf{x},\sigma )(\mathbf{a},\alpha {)}^{-1}$ は

$$(\mathbf{a}+\alpha (\mathbf{x})-\alpha \sigma {\alpha }^{-1}(\mathbf{a}),\alpha \sigma {\alpha }^{-1})$$

となる。置換部分は通常の共役 $\alpha \sigma {\alpha }^{-1}$ だが、向き部分は置換に依存した複雑な変換を受ける。この公式が、ルービックキューブの解法における共役テクニック $AX{A}^{-1}$ の数学的基盤となる。次の記事で、この公式を解法の文脈で具体的に活用する。

まとめ

ルービックキューブ群 $G$ は、コーナーの wreath product 型部分群 $({\mathbb{Z}}_3{)}^7⋊S_8$ とエッジの wreath product 型部分群 $({\mathbb{Z}}_2{)}^{11}⋊S_{12}$ のパリティ制約付きファイバー積として記述される。半直積の構造は「置換が向きを並べ替える」という物理的操作を忠実に反映しており、群の元どうしの積・逆元・共役をすべて明示的に計算可能にする。