The Schreier-Sims Algorithm

Posted on Edited on In

Abstract. 本文将浅谈计算群论中的 Schreier-Sims 算法，该算法的核心思想是将群 $G$ 的信息表示为一列正规子群 $1 = G_1 \subset G_2 \subset \cdots \subset G_k = G$，通过 $G_i$ 在 $G_{i+1}$ 中的截面，回答一些重要的问题如某元素是否在群当中、某给定生成元的有限群的阶数是多少等。

本文的第二节介绍该算法使用的重要技术截面（Transversal）和 Schreier 引理，第三节介绍该算法的核心技术 BSGS，但是很遗憾我们暂时没能看懂如何求解一组 BSGS，只能给出一类大多数应用问题的简单快速的下替算法（参见第 3.3 节）。

声明与记号

考虑作为计算问题的实际性，本文中所有集合均假设为有限集。

本文需要用到群在集合上的作用相关的概念，读者想必知之甚详，本节仅作统一记号之用。

在本文中，群 $G$ 给出了集合 $\Omega$ 上的右作用。其中群中元素 $g$ 作用在 $\alpha$ 上记作 $\alpha^g$。

元素 $\alpha$ 的轨道 $\mathrm{Orb}_G(\alpha) = \{\alpha^g : g \in G\}$，简写作 $\alpha^G$。

元素 $\alpha$ 的稳定子 $\mathrm{Stab}_G(\alpha) = \{g \in G : \alpha^g = \alpha\}$，简写作 $G_\alpha$。

所谓的 Caley 定理揭示了在群 $G$ 有限时，其一定同构于 $\Omega = \{1, 2, …, n\}$ 上的置换群。在实现时不妨暂时只考虑这种情形。

截面（Transversal）和稳定子集合的生成元

著名的轨道-稳定子定理指出：

Theorem 1（轨道-稳定子）. 下列映射

$$
\begin{matrix}
\phi : & G_x \backslash G &\rightarrow &x^G \\
& G_x g & \mapsto & x^g
\end{matrix}
$$

为双射，结合拉格朗日定理导出

$$
|G| = |x^G||G_x|
$$

证明可以参见任意一本抽象代数书籍。

给定子群 $H\subset G$，对于群 $G$ 的一个陪集分解

$$
G = \sqcup_{x} xH
$$

针对这个分解，我们取出每个 $xH$ 的代表元，引出如下定义：

Difinition 2（右截面）. 下面的序列 $u_1, …, u_k$ 称为子群 $H$ 的截面，若

  1. $1\in \{u_1, …, u_k\}$。
  2. $G = \sqcup_{i=1}^k Hx_i$，而 $u_i\in Hx_i$。

定义 $\bar x$ 表示使得 $x\in Hu_i$ 的元素 $u_i$。

而双射 $(1)$ 自然地导出了 $G_x$ 的截面，我们只需要求出 $x^G$ 中所有的元素是如何到达的即可。下面的算法给出了求 $G_x$ 的一个右截面的方式：

Algorithm 3（OrbitTransversal）. 求稳定子的右截面。

输入： $\alpha \in \Omega, X = [x_1, …, x_r], G = \langle X\rangle$。

输出： $OT = \{(\gamma, u_\gamma) : \gamma \in \alpha^G, \alpha^{u_\gamma} = \gamma\}$。${u_\gamma}$ 即为 $G_x$ 的右截面。

  1. $OT \leftarrow \{\alpha, 1\}$
  2. for $(\gamma, u_\gamma) \in OT, x\in X$ do if $\gamma^x \notin \mathrm{Proj}_1(OT)$
  3. $\qquad$ then $OT\leftarrow OT \sqcup {(\gamma^x, u_\gamma x)}$
  4. return $OT$

我们发现稳定子集合的大小可能是天文数字（考虑定义一个作用在黑白染色上的置换群，$\chi_1$ 即只有第一位涂黑的涂色方案的稳定子集合大小为 $(n-1)!$）。所幸的是一些结果能够帮助我们利用其右截面求出其生成元。

Lemma 4（Schreier）. 设 $G = \langle X \rangle$，$H$ 是 $G$ 的子群，$U$ 是 $H$ 的右截面。定义集合

$$
Y = \{ ux\overline{ux}^{-1} : x\in X, u \in U \}
$$

那么 $H = \langle Y \rangle$。

Proof.

先证明 $H \subset \langle Y \rangle$。对于 $h\in H$，将其拆成 $X$ 中元素的乘积 $x_1x_2\cdots x_k$，其中 $x_i\in X \cap X^{-1}$。

定义 $u_0 = 1, u_i = \overline{x_1\cdots x_i}$，容易知道 $u_i\in U$。那么

$$
h = (u_0xu_1^{-1})(u_1xu_2^{-1})\cdots(u_{k-1}xu_k^{-1})
$$

根据 $u_i$ 的定义有 $x_1\cdots x_{i-1}=hu_{i-1}$，于是 $x_1\cdots x_i = h’u_i = hu_{i-1}x_i$，可知 $u_i$ 和 $u_{i-1}x_i$ 属于相同的陪集，换言之 $u_i = \overline{u_i} = \overline{u_{i-1}x_i}$。于是

$$
h = (u_0x\overline{u_0x}^{-1})\cdots(u_{k-1}x\overline{u_{k-1}x}^{-1})\in \langle Y\rangle
$$

$Y$ 的定义自然决定了它是 $H$ 的子集，于是 $\langle Y \rangle = H$。$\square$

于是自然有如下算法。

Algorithm 5（OrbitTransversalStabilizer）. 求稳定子的生成元。

输入： $\alpha \in \Omega, X = [x_1, …, x_r], G = \langle X\rangle$。

输出： $OT, Y$，含义同上方。

  1. $OT \leftarrow \{\alpha, 1\}, Y \leftarrow \{1\}$
  2. for $(\gamma, u_\gamma) \in OT, x\in X$ do if $\gamma^x \notin \mathrm{Proj}_1(OT)$
  3. $\qquad$ then $OT\leftarrow OT \sqcup \{(\gamma^x, u_\gamma x)\}$
  4. $\qquad$ else $Y\leftarrow Y \sqcup \{u_\gamma x u_{\gamma^x}^{-1}\}$
  5. return $OT, Y$

基和强生成集

本算法的核心是将 $G$ 的信息归结为一个正规子群列 $\{1\} = G_1\subset\cdots\subset G_k = G$。如群 $G$ 的阶可以由下面的式子给出

$$
|G| = \prod_{i=1}^{k-1} |G_{i+1} : G_i|
$$

自然地，$G_i$ 的大小是不受控制的，但是上面我们已经得到了若干求解稳定子集合的生成元的方法，因此考虑从稳定子的方向去构造这一列子群。

基本定义

Definition 6（基与强生成集）. 给定 $S$ 使得 $G = \langle S\rangle$ 和 $B = [\beta_1, …, \beta_k]$ 代表 $\Omega$ 中一列互不相同的元素，对于 $1\leq i\leq k+1$ 我们定义

$$
\begin{aligned}
G^{(i)} &= G_{\beta_1, …, \beta_{i-1}} \quad (G^{(1)} = G) \\
S^{(i)} &= S \cap G^{(i)} \\
H^{(i)} &= \langle S^{(i)}\rangle \\
\Delta^{(i)} &= \beta_i^{H^{(i)}} \\
U^{(i)} &= \{u_{\gamma}^{(i)} : \gamma \in \Delta^{(i)}\}
\end{aligned}
$$

不难注意到 $H^{(i)}$ 总是 $G^{(i)}$ 的子群。给定 $B, S$，$S^{(i)}$ 可以直接求出。其余可以用 Orbit Transversal 求出。

称 $B$ 为 $G$ 的基（base），如果 $G^{(k+1)} = 1$。此时显然 $G^{(i)}$ 是 $G$ 的正规列。

称 $S$ 为 $G$ 的强生成集（strong generating set），如果 $\forall i, G^{(i)} = H^{(i)}$。

$(B, S)$ 合称 BSGS。

简单应用

给定 BSGS 和截面序列 $U^{(i)}$，很多问题诸如判定一个元素是否属于 $G$，求 $G$ 的阶数都迎刃而解。这是因为根据上述定义，$U^{(i)}$ 给出了 $G^{(i)}$ 关于子群 $G^{(i+1)}$ 的右陪集分解。因此实际上 $G$ 中的每个元素可以被逐渐拆解到递降的子群当中，从而得到一个唯一的表示

$$
g = u^{(1)}_{\gamma_1}\cdots u^{(k)}_{\gamma_k}
$$

显而易见 $G$ 的阶即是 $\prod_{i=1}^k |U^{(k)}|$，而下面的算法给出判定 $g\in \mathrm{Sym}(\Omega)$ 是否属于 $G$ 的方式。

Algorithm 7（Strip）. 判定 $g$ 是否属于群 $G$。

Input. $g$，BSGS $(B, S)$，截面序列 $[U^{(i)}]$，轨道序列 $[\Delta^{(i)}]$

Output. 标准分解序列 $u_1, …, u_k$，残余量 $h$。$g\in G$ 当且仅当返回 $h=1$。

  1. $h\leftarrow g, U \leftarrow []$
  2. for $i = 1, …, k$ do
  3. $\qquad$ $\gamma_i \leftarrow \beta^h$
  4. $\qquad$ if $\gamma_i \notin \Delta^{(i)}$ then return $U, h$
  5. $\qquad$ $x \leftarrow u_{\gamma_i}$
  6. $\qquad$ $U\leftarrow x ~{::}~ U$
  7. $\qquad$ $h\leftarrow hx^{-1}$
  8. return $U, x$

给定 $(B, S)$，下面的递归算法可以判断其是否是 BSGS：

Algorithm 8（Schreier-Sims-Test）. 判断 $(B, S)$ 是否是 BSGS。

Input. $B, S, \Delta^{(i)}$。

Output. true（若是 BSGS），false（若不是）。

  1. if not $\textrm{Schreier-Sims-Test}(B \setminus \beta_1, S\cap G_{\beta_1}, [\Delta^{(i)} : i > 1])$
  2. $\qquad$ then return false
  3. $\Delta, Y \leftarrow \textrm{OrbitTransversalStabilizer}(\beta_1, S)$
  4. for $y\in Y$ do
  5. $\qquad$ $U, h = \textrm{Strip}(y, B \setminus \beta_1, S\cap G_{\beta_1}, [\Delta^{(i)} : i > 1])$
  6. $\qquad$ if $h\ne 1$ then return false
  7. return true

构造子群链的通俗算法

在大多数简单的应用中我们无须正式求出 $B, S$，只需要令 $B = \Omega$ 并得到相关的信息如截面 $U^{(i)}$，每个稳定子群 $H^{(i)}$ 的生成元（无需是 $S^{(i)}$）。此时存在一个简单的低复杂度算法。

现在给定了 $G = \langle S\rangle$，增量地将 $S$ 中的每一个元素插入其中，并维护上述截面和生成元的变化。

当将 $g$ 插入 $H^{(i)}$ 时，对于当前截面 $u^{(i)}$，我们用 $x = u^{(i)}_*g$ 去尝试更新截面。如果 $u^{(i)}_*g$ 已经在轨道中（通过 $\gamma$ 到达），Schreier Lemma 指出 $u^{(i)}g\gamma^{-1}$ 为 $H^{(i+1)}$ 的元素，因此递归将其插入 $H^{(i + 1)}$。否则它生成了一个新的截面，此时应当枚举 $H^{(i)}$ 的生成元 $g’$ 尝试用 $xg’$ 更新截面。

这里的算法实际上是 OrbitTransversalStabilizer 的 dfs 版本，直接给出该算法的 C++ 实现如下

Implementation in C++

本代码通过了 LibreOJ #177. 生成子群阶数，略去了高精度整数和置换定义的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class generatingSet {
    private:
    int beta, tot, size;
    permutation generator[N * 2], transversal[N];
    bool orbit[N];
    generatingSet *succ;

    public:
    generatingSet(int _size = 0, int _beta = 0, generatingSet *suc = NULL) {
        succ = suc, beta = _beta, tot = 0, size = _size;
        memset(orbit, 0, sizeof(orbit)); orbit[beta] = true; transversal[beta] = permutation(size);
    }

    int getOrbitIndex() {
        int res = 0;
        for(int i = 1; i <= size; i++) if(orbit[i]) res++;
        return res;
    }
    
    bool strip(permutation g) const {
        int gamma = g[beta];
        if(!orbit[gamma]) return false;
        return succ == NULL || succ->strip(g * transversal[gamma].inv());
    }

    void orbitTransversalStabilizer(permutation g) {
        int gamma = g[beta];
        if(orbit[gamma]) {
            if(succ) succ->insert(g * transversal[gamma].inv());
        }
        else {
            orbit[gamma] = true, transversal[gamma] = g;
            for(int i = 1; i <= tot; i++) orbitTransversalStabilizer(g * generator[i]);
        }
    }

    void insert(permutation g) {
        if(strip(g)) return;
        generator[++tot] = g;
        for(int i = 1; i <= size; i++) 
            if(orbit[i]) orbitTransversalStabilizer(transversal[i] * g);
    }
} H[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++) 
        H[i] = generatingSet(n, i, i == 1? NULL : (H + i - 1));

    for(int i = 1; i <= m; i++) {
        permutation x;
        x.read(n);
        H[n].insert(x);
    }

    Int ans = 1;
    for(int i = 1; i <= n; i++) 
        ans = ans * H[i].getOrbitIndex();
     ans.print();
    return 0;
}

分析各函数调用的次数可以知道该算法的复杂度至多是 $O(n^5)$ 的。

求基和强生成集（未完成）

存在一个增量构造基和强生成集的 $\tilde{O}(n^8)$ 算法，不是很实际，先搁置。