Schreier–Sims 算法

引入

Schreier-Sims 算法 是计算群论的一种算法，以数学家 Otto Schreier 和 Charles Sims 的名字命名。它可以在多项式时间（polynomial time）内找到有限置换群的阶数、查看给定排列是否包含在群中以及其他许多任务。Schreier-Sims 算法最早由 Sims 在 1970 年基于 Schreier 的子群引理引入。1991 年，Donald Knuth 基于此改进了时序。后来，又有了该算法更快的随机版本。

背景

Schreier-Sims 算法是一种计算置换群的基强生成集（BSGS, base and strong generating set）的有效方法。特别是，SGS 确定了群的顺序并使查看给定排列是否包含在群中变得更加容易。由于 SGS 对于计算群论中的许多算法至关重要，因此计算机代数系统通常依赖 Schreier-Sims 算法进行群的有效计算。

Schreier-Sims 的运行时间因实现而异。令 由 个生成器给出。该算法可能的运行时间为：

• 需要 的内存；
• 需要 的内存；

Schreier 向量的使用会对 Schreier-Sims 算法的实现性能产生重大影响。对于 Schreier-Sims 算法的 Monte Carlo 变体，预估复杂度如下：

• 需要 的内存；

现代计算机代数系统（例如 GAP 和 Magma）通常使用优化过的蒙特卡罗算法。

定义

定义任意群 是由一个子集 生成，, 对于所有 , 的每个元素都可以写成 与 或 的乘积。

Schreier 树

对于 根为 的 Schreier 树 是 轨道的如下表示：

• Schreier 树是一棵以 为根，以 的元素为顶点的树，
• 它的边描述了从 到每个顶点所需的 的元素，即树中的每条边 ，其中 比 更靠近根的 由生成器 标记，将 移动到 。
• Schreier 树可以通过 广度优先搜索 或 深度优先搜索 从 开始用所有生成器 尝试到达新的节点 来找到。因此，计算 Schreier 树所需的时间以 为界。这意味着我们可以以一种有效的方式找到 。

Schreier 引理

Schreier 引理说明了如何使用 的 Schreier 树来查找稳定器 的生成器。

Schreier 引理：令 。那么由一组 Schreier 生成器生成的 稳定器 ：

其中 被定义为将 移到 的 中一个元素，即 的陪集（coset）代表。

强生成集

定义 的 基（base） 为一个序列 , 因此逐点稳定器（pointwise stabilizer） 是可以忽略不计的。

定义 相对于 的 强生成集（SGS，strong generating set) 是一个对于每个 有 的集合 ，其中 ,。

过程

用来计算排列群（permutation group） 阶数的 Schreier-Sims 算法一般有三种。它们同样也可以用来计算 的基和强生成集。

基础 Schreier-Sims 算法

1. 如果 为不平凡（non-trivial）群，选择一个尚未被选择的点 。
2. 计算根为 的 Schreier 树，得到 。
3. 使用 Schreier 引理找到 的生成器。
4. 对 递归使此算法，到找到 为止。

当算法结束时， 是一个基，找到的所有生成器的并集是一个强生成集。

基础 Schreier-Sims 算法的运行时间是 指数级 的，但可以被优化成更高效的算法。

增量 Schreier-Sims 算法

增量 Schreier-Sims 算法 是常被用来构建强生成集的快速算法。

如果有一个群 的强生成集，因为已经得到了所有 稳定器的生成器，那么很容易得到 的阶。部分基（partial base） 和部分强生成集 是集合 和集合 ，使得 的任何元素都不能固定 的每个元素。

增量 Schreier-Sims 算法可以将任意部分基和部分强生成集转化为基和强生成集。

定义 为通过 Schreier 树 对 的陪集的作用。

1. 如果 ，返回 ;
2. 非空部分基 。部分强生成集 。集 ,，并递归地应用于输入 ，以将它们修改为 的基和强生成集。
3. 设 ,。用筛选算法在 中进行成员资格测试（Membership testing，检查集合（列表、集合、字典等）是否包含特定元素）。对 测试每个 Schreier 生成器 以查看 。如果都在 中，那么有 , 返回 ，。否则到步骤 4。
4. 否则有一个 Schreier 生成器 但 。设 。如果 固定了 的所有点，将一个由 移动的 点附加到 。回到步骤 2。

当算法结束时， 为基， 是大小为 的强生成集。

增量 Schreier-Sims 算法的运行时间为 ，即 的多项式。 个生成器构建 Schreier 树需要 ，或对于 为 。因为已经用 限制了 Schreier 生成器 的数量，所以每个筛选过程都可以在 中完成。

实现

以下为基础 Schreier-Sims 算法的参考代码。

例题

参考资料与拓展阅读

• [1]Schreier–Sims algorithm - Wikipedia
• [2]Knuth, Donald E，Efficient representation of perm groups, Combinatorica 11 (1991), no. 1, 33–43.
• [3]Ákos Seress,Permutation Group Algorithms, Cambridge University Press
• [4]Sims, Charles C,Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra, pp. 169–183, Pergamon, Oxford, 1970.
• [5]Martin Jaggi,Implementations of 3 Types of the Schreier-Sims Algorithm, MAS334 - Mathematics Computing Project, 2005
• [6]The Schreier-Sims algorithm for finite permutation groups
• Henrik B¨a¨arnhielm,The Schreier-Sims algorithm for matrix groups