---
tag: 61F4HEY84K
kind: definition
name: Schreier–Sims algorithm
msc: [68W30, 20B05]
defines: FHGDZWZ2WE
uses: [ZDJQRKPWGA, 0515A6D2Y1, 0AYMP41THN, 0YQPZB5Q1G, 0RP7VWQ0YN, 0B85S2V2DR, 0DTXBQPA2S]
sources:
  - url: https://en.wikipedia.org/wiki/Schreier–Sims_algorithm
---

## Definition

Let $\Omega = \set{1, \dots, n}$ and let $G \le \operatorname{Sym}(\Omega)$ be the [[permutation group|ZDJQRKPWGA]] [[generated|0RP7VWQ0YN]] 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|0AYMP41THN]] 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|0YQPZB5Q1G]] $\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.

## Remarks

When the algorithm ends, $\abs{G} = \abs{\Delta_1} \abs{\Delta_2} \cdots \abs{\Delta_k}$, because $\abs{\Delta_i}$ is the [[index|0DTXBQPA2S]] $[G^{(i)} : G^{(i+1)}]$ by the orbit-stabiliser theorem.
A permutation $\sigma$ lies in $G$ exactly when sifting $\sigma$ through the whole chain ends at the identity.

Example: $G = S_3$ generated by $S = \set{(1\,2\,3), (1\,2)}$, with base $(1, 2)$.
The orbit of $1$ is $\Delta_1 = \set{1, 2, 3}$.
The stabiliser of $1$ is $G^{(2)} = \set{e, (2\,3)}$, and the orbit of $2$ under it is $\Delta_2 = \set{2, 3}$.
So $\set{(1\,2\,3), (1\,2), (2\,3)}$ is a strong generating set, and $\abs{G} = 3 \cdot 2 = 6$.

Non-example: the sequence $(1)$ is not a base of $S_3$, because the element $(2\,3) \ne e$ fixes $1$.
Also, $S = \set{(1\,2\,3), (1\,2)}$ is not a strong generating set for the base $(1, 2)$: no element of $S$ fixes $1$, so $S \cap G^{(2)}$ generates only $\set{e}$.