6
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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 \begin{equation} 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. \end{equation}

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Oct 16, 2013 at 14:56
  • $\begingroup$ 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$. $\endgroup$ Oct 16, 2013 at 15:10
  • $\begingroup$ 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. $\endgroup$ Oct 16, 2013 at 16:38
  • $\begingroup$ Yes, you are right. Unfortunately, one apparently cannot edit comments. $\endgroup$ Oct 16, 2013 at 20:51
3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 17, 2013 at 15:23
  • $\begingroup$ 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$. $\endgroup$ Oct 21, 2013 at 16:58
  • $\begingroup$ @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. $\endgroup$ Oct 21, 2013 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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