the Schreier-Sims Algorithm

It is a note of Permutation Groups, Cameron section 1.13.

Let $G$ be a permutation group on $\Omega =\{1,2,\cdots ,n\}$ generated by $\{g_1,\cdots ,g_m\}$. The Schreier-Sims algorithm is a technique to solve two questions:

• find $|G|$;
• for any $g\in \mathrm{Sym}(\Omega )$, whether $g\in G$ or not?

Step 1. Take ${\alpha }_1\in \Omega$ and find the orbit ${\mathcal{O}}_1$ of $\alpha$ by repeatedly applying generators until no new points are obtained. Define $G(1)=G_{{\alpha }_1}$, which is a subgroup satisfying $|G|=|{\mathcal{O}}_1|\times |G(1)|$.

Step 2. Find generators of $G(1)$. The following lemma gives us a method.

Schreier Lemma

Let $G=⟨g_1,\dots ,g_r⟩$. Let $H$ be a subgroup of index $n$ in $G$, with coset representatives $x_1,\dots ,x_n$, where $x_1=1$ is the representative of $H$. Let $\bar{g}$ be the representative of the coset $Hg$ . Then

$$H=⟨x_i{g}_j{\left(\overline{x_i{g}_j}\right)}^{-1}:1\le i\le n,1\le j\le r⟩.$$

Such elements in the form of $x_i{g}_j(\overline{x_i}\overline{g_j}{)}^{-1}$ are called Schreier Generator.

Repeat this procedure, and we end up with

• a base, a sequence $\left({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_m\right)$ whose pointwise stabilizer is the identity; and
• a strong generating set, a set $S=S_1\cup \dots \cup S_m$ of group elements, where $S_i$ is a set of coset representatives for $G(i)$ in $G(i-1)$ for $1⩽i⩽m$ and $G(i)$ is the pointwise stabilizer of $\left({\alpha }_1,\dots ,{\alpha }_i\right)$.

Consequently, the order of $G$ is

$$|G|=|G(0):G(1)|\cdots |G(m-1):G(m)|=|S_1|\cdots |S_m|.$$

For a given $x\in \mathrm{Sym}(\Omega )$, check ${\alpha }_{1}x$.

• If ${\alpha }_{1}x\notin {\mathcal{O}}_1$, then $x\notin G$.
• If ${\alpha }_{1}x\in {\mathcal{O}}_1$, then there exists $s_1\in S_1$ such that ${\alpha }_{1}x={\alpha }_1{s}_1$. Then $x\in G$ iff $x{s}_1^{-1}\in G(1)$.

Check it recursively, and finally $x{s}_1^{-1}\cdots s_m^{-1}\in G(m)=1$ and $x=s_m\cdots s_1\in G$.

Furthermore, we can choose a random element of $G$ (with all elements equally likely), by choosing random elements of $S_m,S_{m-1},\dots ,S_1$ and multiplying them.