群论（二）：魔方，混杂的内容

索引

注意到有一些群论的文章以魔方为例，但停留在将它作为例子，本文对三阶魔方进行详细说明。

记号

不妨设每个面的中心固定，令 $G$ 表示魔方的变换群。

我们记六个面为上面 U，下面 D，左面 L，右面 R，前面 F 和后面 B（取首字母），以大写字母表示将该面顺时针旋转 90°

显然所求的群是由它们生成的，即 $G=<U, R, F, D, L, B>$

群结构

大小

魔方剩余可动的有两类：角块和棱块，它们两两不同，由于分别有位置和旋转状态，有：

$$G\leq Z_3^8\times S_8 \times Z_2^{12}\times S_{12}$$

接下来更精细地讨论哪些角块、棱块排布是合法的。

先讨论角块，一个角块的标准状态是一个（或三个）面上与中心块颜色相同，将其记作 0，顺时针转 120° 的状态记作 1，顺时针转 240° 的状态记作 2，那么所有标记之和在 $\pmod{3}$ 下不变。同理，棱块的标记之和在 $\pmod{2}$ 下不变。此外，角块的置换奇偶性与棱块的置换奇偶性一致。

同时，我们可以说明符合上述要求的是合法的。

定义换位子 $[a, b] = aba^{-1}b^{-1}$

如果 $x^{[a, b]}\neq x$，则要么 $a\notin Stab(x), b\notin Stab(x^a)$，要么 $b\notin Stab(x), a\notin Stab(x^b)$

例如，我们构造操作：$[[R, U], D] = RUR'U'DURU'R'D'$，这只会改变三个角块的状态。

因此有 $|G| = \frac{1}{12} |Z_3^8\times S_8 \times Z_2^{12}\times S_{12}| = 43252003274489856000$

半直积

为更好地描述角块群与棱块群，我们定义直积的扩展。

群 $N, H$，$H$ 在 $N$ 上的作用 $\varphi$，定义半直积 $N\rtimes_\varphi H$ 为：

• 集合是 $N\times H$
• 运算 $(n_1, h_1)\cdot (n_2, h_2) = (n_1n_2^{h_1}, h_1h_2)$
• 单位元 $(e_N, e_H)$
• 逆元 $(n^{-h^{-1}}, h^{-1})$

例如，$D_{2n} = Z_n \rtimes Z_2$，其中

$$ \varphi: \begin{cases} e \mapsto (g \mapsto g) \\ a \mapsto (g \mapsto g^{-1}) \end{cases} $$

由于角块（通过操作造成的）位置变化会改变朝向，角块群形如 $(Z_3)^7 \rtimes S_8$

整个魔方群是 $(Z_3^7 \rtimes S_8)\times (Z_2^{11} \rtimes S_{12}) / \sim$

解法

换位子

现在人类的方法大致如此逐层复原，在后半部分使用预设的小阶数置换的公式。

降低群大小

Thislethwaite Method 将群逐步化为

• $<U, R, F^2, D, L, B^2>$
• $<U, R^2, F^2, D, L^2, B^2>$
• $<U^2, R^2, F^2, D^2, L^2, B^2>$
• $\{e\}$

Kociemba Algorithm 则将群逐步化为

• $<U, R^2, F^2, D, L^2, B^2>$
• $\{e\}$

通用解法

以上的解法都依赖于具体的结构，这里提供一个通用方法：Schreier-Sims-Minkwits 算法。¹

我们希望进行这样的操作：每次多固定一个集合上的元素，其稳定化子就是原变换群的真子群，如此下去可以得到一个链 $G = G_0 > G_1 > G_2 \cdots G_n = \{e\}$，而由于我们要写出一个操作序列，设第 $i$ 个阶段可能的操作为 $r_{i_1}, r_{i_2} \cdots$ 有 $r_{i_1}G_{i+1}, r_{i_2}G_{i+1} \cdots$ 陪集族构成 $G_i$

对 $H$ 的元素 $h = s_1s_2\cdots s_k$，其中 $s_i$ 为生成元，记 $t_i = \overline{s_{i+1}\cdots s_k}$，其中 $t_0 = t_k = e$，故有

$$h = (t_0^{-1}s_1t_1)(t_1^{-1}s_2t_2)\cdots (t_{k-1}^{-1}s_kt_k)\tag{1}$$

由于 $s_it_iH = t_{i-1}H$，有 $\overline{s_it_i} = t_{i-1}$，我们可以把上式写成

$$h = (\overline{s_0t_0}^{-1}s_1t_1)(\overline{s_1t_1}^{-1}s_2t_2)\cdots (\overline{s_{k-1}t_{k-1}}^{-1}s_kt_k)\tag{2}$$

另一方面，$\overline{sr}^{-1}srH = \overline{sr}^{-1}\overline{sr}H = H$，得证

上式给出了一般的找到链的方法，代码可参见 https://oi-wiki.org/math/algebra/schreier-sims/

注释