It is known that any subgroup of the symmetric group on $n$ elements can be generated by a linear number (in $n$) of elements. Can we choose a small set of generators such that the resulting maximal word length is also small? For example, both linear, or perhaps polynomial? 



Number of generators and word length for subgroups of symmetric group
For a subgroup $G \le S\_n$ we can choose generating sets $X$ that satisfy
any of the following three bounds for the
maximum lengths of elements of $G$ as words over $X$.


1. $|X| \le n(n-1)/2$, maximum word length $n-1$.
2. $|X| \le n-1$, maximum word length $n(n-1)/2$.
3. $|X| \le n\log n$, maximum word length $2n\log n$ (where $\log = \log\_2$).


Let $\alpha\_1,\alpha\_2,\ldots,\alpha\_k \in \Omega$ be a *base* for $G$.
That is, the stabilizer $G\_{\alpha\_1,\cdots,\alpha\_k} = 1$.
For $1 \le i \le k+1$, define $G\_i = G\_{\alpha\_1,\cdots,\alpha\_{i-1}}$,
so $G = G\_1 \ge G\_2 \ge \cdots \ge G\_{k+1} = 1$, and we can choose a base to
make the sequence strictly descending. Note that
each $|G\_i:G\_{i+1}| \le n-i+1$.


To prove 1, we let $X$ be the union of coset representatives of $G\_{i+1}$
in $G\_i$, omitting the identity element.


To prove 2, we choose $X$ by first choosing a generating set
for $G\_k$, then extending this to one for $G\_{k-1}$, and so on. (The resulting
$X$ is called a *strong generating set* for $G$.) Each new generator
decreases the total number of orbits of the subgroup of $G$ generated by the
generators chosen so far, so we have $|X| \le n-d$, where $d$ is the number
of orbits of $G$.


It is easy to see that we can find coset representatives of each $G\_{i+1}$
in $G\_i$ as words of length at most $|G\_i:G\_{i+1}|-1$ in the generators
that lie in $X \cap G\_i$, so we get 2.


Claim 3 follows from the more general result that, for any finite
group $G$, we can find a generating set $X$ of $G$ with $|X| \le \log |G|$
and maximum word length $2\log |G|$. Then 3 follows because
$\log |S\_n| \le n \log n$. We prove this as follows.


For an ordered list $L = (g\_1,g\_2,\ldots,g\_k)$ of elements of $G$,
define
$$C\_L = \{ g\_1^{\epsilon\_1}g\_2^{\epsilon\_2} \cdots g\_k^{\epsilon\_k} :
\epsilon\_i \in \{0,1\} \}.$$


Note that, for $g \in G$, if $g \not\in C\_L^{-1}C\_L$, then $C\_L \cap C\_Lg$ is
empty, and so $|C\_{L'}| = 2|C\_L|$ with $L' = (g\_1,\ldots,g\_k,g)$.
We define $X$ by constructing lists $L\_k$ of elements of $G$,
starting with $L\_0$ empty.


At any stage, if we have chosen $L = L\_k = (g\_1,g\_2,\ldots,g\_k)$ then,
if $C\_L^{-1}C\_L \ne G$, we choose $g\_{k+1} \in G \setminus C\_L^{-1}C\_L$,
and then $|L\_{k+1}| = 2|L\_k|$. If $C\_L^{-1}C\_L = G$, then $L$
generates $G$ with the maximum word length $2k$, and we stop and put $X=L$.
Since we double the size of $|C\_L|$ with each new generator, we must
stop with $C\_{L}^{-1}C\_{L} = G$ with $k \le \log |G|$.


This technique for constructing $L$ is used in algorithms for computing
with subgroups of $S\_n$, where it is usually combined with the
construction of a strong generating set, as in 2. I think it is originally
due to Babai.


