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?

$\begingroup$ yes, but I'm asking the question for an arbitrary subgroup (the generators should be in the subgroup of course) $\endgroup$ – alesia Jun 12 at 20:52

$\begingroup$ You might be more specific on what you mean by "small". $\endgroup$ – YCor Jun 13 at 6:44

1$\begingroup$ It's easy to find a generating set of size at most $n^2$ (in fact $n(n1)/2$) such that each element can be expressed as a word of length at most $n$: just choose coset representatives in a stabilizer chain for the group. Is that good enough? Alternatively you could choose $n$ generators and have words of length at most $n^2$ (I think length $n \log n$ might be possible, but I need to check). $\endgroup$ – Derek Holt Jun 13 at 8:23

$\begingroup$ @DerekHolt : yes, this solves the question. Thanks! If you wanna write your comment as an answer, please do $\endgroup$ – alesia Jun 13 at 18:39
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(n1)/2$, maximum word length $n1$.
$X \le n1$, maximum word length $n(n1)/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_{i1}}$, 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 ni+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_{k1}$, 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 nd$, 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'} = 2C_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} = 2L_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.