# 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?

• yes, but I'm asking the question for an arbitrary subgroup (the generators should be in the subgroup of course) – alesia Jun 12 at 20:52
• You might be more specific on what you mean by "small". – YCor Jun 13 at 6:44
• It's easy to find a generating set of size at most $n^2$ (in fact $n(n-1)/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). – Derek Holt Jun 13 at 8:23
• @DerekHolt : yes, this solves the question. Thanks! If you wanna write your comment as an answer, please do – 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$$.

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.