Number of generators and word length for subgroups of symmetric group 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? 
 A: 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$.


*

*$|X| \le n(n-1)/2$, maximum word length $n-1$.

*$|X| \le n-1$, maximum word length $n(n-1)/2$.

*$|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.
