Schreier–Sims algorithm

Definition

Let $\Omega = \set{1, \dots, n}$ and let $G \le \operatorname{Sym}(\Omega)$ be the permutation group generated by a finite set $S$ of permutations. A base of $G$ is a sequence $(b_1, \dots, b_k)$ of points of $\Omega$ such that only the identity of $G$ fixes every $b_i$. It gives the stabiliser chain $G = G^{(1)} \ge G^{(2)} \ge \dots \ge G^{(k+1)} = \set{e}$, where $G^{(i+1)}$ is the pointwise stabiliser of $b_1, \dots, b_i$ in $G$. A strong generating set for this base is a subset $T \subseteq G$ such that $T \cap G^{(i)}$ generates $G^{(i)}$ for each $i = 1, \dots, k$.

The Schreier–Sims algorithm computes, from $S$, a base of $G$ and a strong generating set for it. It builds the chain from the top, and it repeats these steps until no new generator appears:

1. For each level $i$, compute the orbit $\Delta_i = G^{(i)} b_i$ and, for each $\delta \in \Delta_i$, an element $u_\delta \in G^{(i)}$ with $u_\delta b_i = \delta$.
2. By Schreier's lemma, $G^{(i+1)}$ is generated by the Schreier generators $u_{s\delta}^{-1} \, s \, u_\delta$, with $s$ in the current generators of $G^{(i)}$ and $\delta \in \Delta_i$.
3. Sift each Schreier generator through the levels below $i$, that is, divide it by the coset representatives $u_\delta$ found there. If the remainder is not the identity, add it to the generators of the level where sifting stopped, with a new base point if needed.