4
$\begingroup$

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?

$\endgroup$
  • $\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(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). $\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
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.