Can someone explain how the Schreier-Sims Algorithms works on a permutation group with a simple example?

Solution 1:

The problem is that working through this algorithm by hand is very tedious and repetitive.

But, let's do $G = \langle x,y \rangle \le S_4$ with $x=(1,2,3)$, $y=(1,2,4)$.

Start with a single base point $1$, and (strong) generating set $S = [x,y]$.

The orbit of $1$ is $O_1=[1,2,3,4]$ with permutations $T_1=[1,x,x^{-1},xy]$ mapping $1$ to the orbit points.

Now we consider the Schreier generators of the stabilizer of $1$. We consider each product $ta$ in turn with $t \in T_1$ and $a \in S$, and then multiply it by the inverse of the appropriate element of $T$ to make it fix $1$.

$1xx^{-1} = 1$

$1yx^{-1} = (2,3,4)$.

This is not the identity, so we interrupt the loop through the $ta$, and adjoin a new base point $2$, and a new strong generator $z=(2,3,4)$.

So now $B=[1,2]$ and $S=[x,y,z]$ with $z$ fixing base point $1$.

Now we work with base point $2$ in the stabilizer of $1$, using strong generators $S_2=[z]$. The orbit of $2$ is $O_2=[2,3,4]$ with transversal $T_2=[1,z,z^{-1}]$. We consider the products $ta$ with $t \in T_2$ and $a \in S_2$ and get

$1zz^{-1}=1$, $zzz = 1$, $z^2z=1$. So we get the identity each time and we have verified that $S_2$ is a strong generating set for the subgroup of the stabilizer of $1$ generated by $S_2$.

Now we go back to base point $1$ and recheck the products $ta$ with $t \in T_1$, $a \in S$. I won't work through all of these, but let's just look at the one that failed last tiem, i.e. $t=1$, $a=y$. Again we multiply by $x^{-1}$ giving $1yx^{-1} = (2,3,4)$ which fixes $1$. But now we have the new base point $2$ and we have strong generator $z$ mapping $2$ to $3$. So we adjust the product to $1yx^{-1}z^{-1} = 1$.

You can verify that all $8$ products $ta$ reduce to the identity on mulitplying by inverses of elements of $T_1$ and $T_2$. So the algorithm stops, and we now know that the order of the group is the product of the basic orbit lengths i.e. $4 \times 3 = 12$.