# Word length in the symmetric group

Let $n \geq 1$ and let $H_n$ be a 2-Sylow subgroup of the symmetric group $\mathrm{Sym}(2^n)$. Let also consider the cycle $\gamma_n = (1, \ldots, 2^n)$ of order $2^n$.

If we assume moreover that $H_n$ contains the transposition $(1,2)$ then $\Sigma_n = \{{\gamma_n^{\pm1}\}} \cup H_n$ is a generating set of $\mathrm{Sym}(2^n)$, and we can consider the word length on $\mathrm{Sym}(2^n)$ associated to $\Sigma_n$, defined by $$|g|_{\Sigma_n} = \min \{ k \geq 0 : \exists s_1, \ldots, s_k \in \Sigma_n; \sigma = s_1 \cdots s_k \},$$ for $g \in \mathrm{Sym}(2^n)$.

Now let $m_n$ be the maximum of the $|g|_{\Sigma_n}$ when $g$ ranges over $\mathrm{Sym}(2^n)$.

Question 1: is the sequence $(m_n)_n$ bounded ? (this may not depend on the choice of the Sylow subgroup $H_n$)

(EDIT: the answer to Question 1 is no according to Peter Mueller's answer below)

If the answer to Question 1 is no, then

Question 2: are there known bounds for $m_n$ ?

(EDIT: I am interested in an upper bound, i.e. an upper bound of the diameter of the Cayley graph $\mathrm{Cay}(\mathrm{Sym}(2^n), \Sigma_n)$ of the symmetric group $\mathrm{Sym}(2^n)$.)

Here is a lower bound on $m_n$, which settles Q1 and half of Q2: The size of a $2$-Sylow subgroup is $2^{2^{n+1}-1}$. So the size of $\Sigma_n$ is certainly less that $2^{2^{n+1}}$. Clearly $2^n!=\lvert\text{Sym}(2^n)\rvert\le \lvert\Sigma_n\rvert^{m_n}$. Together with $u!\ge (u/e)^u$ we obtain $$m_n\ge\frac{2^n\log\frac{2^n}{e}}{2^{n+1}\log 2}=\frac{n\log 2-1}{2\log 2}\ge\frac{n}{2}-1.$$

• Ok thank you very much, it answers Question 1. We can note that your argument is just about counting and does not use anything about $\Sigma_n$. I guess I should have been more precise, but I am more interested in an upper bound for Question 2. – Adrien Le Boudec Oct 16 '13 at 14:56
• What kind of upper bound do you need? Even with $\pm\gamma_n$ and $(1,2)$ you can express each transposition with about $\le 2n$ products. As each permutation is a product of $\le n-1$ transpositions, you should get something like $m_n\le 2n^2$. Maybe that can be improved by using all of $H_n$. – Peter Mueller Oct 16 '13 at 15:10
• Yes I agree with you (up to the fact that we are in $\mathrm{Sym}(2^n)$, so your $n$ needs to be changed in $2^n$). The point is actually to use the bigger generating set $\Sigma_n$ (whose cardinality is about $2^{2^n}$ as you pointed out) to get a better upper bound. – Adrien Le Boudec Oct 16 '13 at 16:38
• Yes, you are right. Unfortunately, one apparently cannot edit comments. – Peter Mueller Oct 16 '13 at 20:51

I think we can get all transpositions with words at length at most 5 over $\Sigma_n$, which will give an upper bound of $5(2^n-1)$. This can easily be improved slightly - for example, you can use elements of $H_n$ for the first and last terms of the product of length $(2^n-1)$, but I don't know whether we can do better than $O(2^n)$ for the upper bound. It seems likely that you could.

To show how to get the transpositions, we can assume that $H_n$ contains $(1,2)$, $(3,4)$, $(5,6)$, etc, and by conjugating these by $\gamma_n$, we get $(2,3)$, $(4,5)$, $(6,7)$, etc.

I claim that every transposition $(i,j)$ in $S_n$ is a conjugate to one of $(1,2)$, $(2,3)$, $(3,4)$, by an element of $H_n$, which will give the required bound. Use induction $n$. We can assume that $\{1,2,\ldots,2^{n-1}\}$ and $\{2^{n-1}+1,\ldots,2^n\}$ are blocks of imprimtivity for $H_n$. If $i$ and $j$ are in the same block, then the claim follows by induction. Otherwise, since the stabilizer of the block system in $H_n$ is $H_{n-1} \times H_{n-1}$, where $H_{n-1}$ acts transitively on the block it fixes, we can conjugate $(2^{n-1},2^{n-1}+1)$ to$(i,j)$ by and element of $H_{n-1} \times H_{n-1}$.

• I don't know why you can assume that $H_n$ contains (3,4), (5,6), etc.. These line up too conveniently with $\gamma_n$. Maybe the transpositions in $H_n$ are (1,2),(3,97),(4,25), etc. – Brendan McKay Oct 17 '13 at 15:23
• Fortunately the example I have in mind allows the assumption that $H_n$ contains these transpositions. More precisely, the reason why I ask this question comes from the following situation: numbers $\{1,2,...,2^n\}$ are identified with the leaves of a rooted regular binary tree $T_n$ of depth $n$, and $H_n$ is the automorphism group of $T_n$. – Adrien Le Boudec Oct 21 '13 at 16:58
• @Derek Holt: thank you very much for your answer. I also believe that the $O(2^n)$ bound can be improved. Actually I would need to get a $O(n)$ upper bound for $m_n$ (and by Peter Mueller's answer this is the best we can hope), but it seems that working with transpositions may not appropriate to do so. – Adrien Le Boudec Oct 21 '13 at 17:07