\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{mine}
\begin{document}
\newcommand{\sym}{{\rm Sym}}
{\bf Disclaimer:} These are just notes for a lecture, not
a polished writeup. In particular, references are missing.
Use at your own discretion.
In this lecture we will solve the membership problem
for subgroups of permutation groups.
First some notation. We use $[n]$ to denote the
set $\{1,\ldots,n\}$ and $[k,n]$ to denote the
set $\{k,k+1,\ldots,n\}$.
A function $\pi:[n]\to[n]$ is a permutation if
for every $i \ne j \in [n]$ it is the case
that $\pi(i) \ne \pi(j)$.
Let $S_n$ be the symmetric group on $n$
elements, i.e., the group whose elements are
permutations on $n$
elements, and where $\pi \cdot \sigma$ is the
composition of the two functions.
For $S \subseteq S_n$, let $\langle S \rangle$
denote the subgroup generated by $S$.
In this lecture we give an algorithm that takes
as input $S \subseteq S_n$ and $\pi \in S_n$ and
determines if $\pi \in \langle S \rangle$.
(Food for thought: Among other things, this
algorithm should prove $\pi \in \langle S \rangle$
or not, as the case may be. What do such proofs
look like?)
This algorithm is due to Sims (Reference?). Good
sources for reading this algorithm (in increasing
order of simplicity) are Seress's book, Knuth's
paper on perm groups, and these notes.
The central notion to this membership algorithm
is a {\em strong generating set}. We define this
notion (somewhat differently than others) below.
Throughout this lecture let $n$ be fixed. Let
$\sym(k)$ denote the subgroup of $S_n$ that
fixes the set $[k+1,n]$. I.e.,
$\sym(k) = \{\pi \in S_n | \pi(i) = i ~ \forall i \in [k+1,n]\}$.
\begin{definition}
For a group $G \subseteq S_n$,
a set $T \subseteq G$ is a {\em strong generating set}
for $G$ if the following holds:
For every $j < k \leq n$, if
$\exists \pi \in G \cap \sym(k)$ such that $\pi(k) = j$
then there exists a permutation $\sigma = \sigma_{jk}
\in T \cap \sym(k)$ such that $\sigma(k) = j$.
\end{definition}
A priori it is not clear that a strong generating set
for $G$ should even generate $G$. We will show
however that it does do so in a strong sense.
For $\sigma \in S_n$, let $k(\sigma) = \min\{k | \sigma
\in \sym(k)\}$.
For any set $T \subseteq G$
let $\overline{T}$ denote the set
of elements that can be obtained by a
multiplication of elements in $T$ of increasing
$k(\cdot)$ value. I.e.,
$\overline{T} = \{\sigma = \sigma_1\cdot\sigma_2\cdots\sigma_{\ell}
| \sigma_i \in T, k(\sigma_i) < k(\sigma_{i+1})\}$.
Our first lemma shows that every group $G \subseteq S_n$
has a strong generating set $T$ of size $O(n^2)$ and this
generating set generates $G$ in the strong sense that
$G = \overline{T}$.
\begin{lemma}
\label{lem:one}
Fix group $G \subseteq \sym(n)$.
\begin{enumerate}
\item $G$ has a strong generating set of size $O(n^2)$.
\item For every strong generating set $T$ of $G$,
$G = \overline{T}$.
\end{enumerate}
\end{lemma}
\begin{proof}
For the first part, first notice that $G$ is itself a
strong generating set of $G$.
So consider a minimal strong generating
set $T$ of $G$. For every $\sigma \in T$ we can
associate a pair $(j,k)$, $j < k \leq n$ such that
$\sigma \in \sym(k)$ and $\sigma(k) = j$. Notice that
for $\sigma'\ne\sigma \in T$, the associated pairs
$(j',k')$ and $(j,k)$ are distinct (or else we can
delete one of $\sigma$ or $\sigma'$ and $T$ will still
be a strong generating set for $G$). Thus $T$ has
at most ${n \choose 2}$ elements.
Now consider $\pi \in G$, with $k(\pi) = k$.
We prove by induction on $k$ that $\pi \in \overline{T}$.
Note there must be an element $\sigma \in T$
with $k(\sigma) = k(\pi) = k$ and $\sigma(k) = \pi(k)$
(using the fact that $T$ is a strong generating set
for $G$).
But now the element $\rho = \pi \cdot \sigma^{-1}$
satisfies the conditions $\rho \in G$, $k(\rho)