3
$\begingroup$

Given symmetric group $S_n$, is it possible to find $k=\lceil\log_2S_n\rceil=\lceil\log_2n!\rceil$ members $\{\alpha_i\}_{i=1}^{k}$ in $S_n$ such that every member of $S_n$ can be written as $\alpha_1^{b_1}\alpha_2^{b_2}\dots\alpha_{k}^{b_{k}}$ or $\alpha_{\sigma(1)}^{b_1}\alpha_{\sigma(2)}^{b_2}\dots\alpha_{\sigma(k)}^{b_{k}}$ where $b_i\in\{0,1\}$ and $\sigma\in S_k$?

If not, what is the minimum $k$ that is needed?

How about for representations of the form $\alpha_1^{b_1}\alpha_2^{b_2}\dots\alpha_{k}^{b_{k}}$ or $\alpha_{\sigma(1)}^{b_1}\alpha_{\sigma(2)}^{b_2}\dots\alpha_{\sigma(k)}^{b_{k}}$ where $b_i\in\{0,1,2,\dots,t\}$ for some fixed $t$ and $\sigma\in S_k$?

Are there good references for these problems?

Posted https://math.stackexchange.com/questions/1013451/base-for-symmetric-group

$\endgroup$

1 Answer 1

4
$\begingroup$

A related concept is that of minimal sorting networks. A sorting network is a list $\alpha_1$, $\alpha_2$, ..., $\alpha_k$ of transpositions (meaning permutations which switch two items and leave all others fixed) so that all permutations can be written in the form $\alpha_1^{b_1} \alpha_2^{b_2} \cdots \alpha_k^{b_k}$ for some $(b_1, \ldots, b_k) \in \{ 0, 1 \}^k$. Let $S(n)$ be the size of the minimal sorting network on $n$ elements. As you point out, the obvious bound is $S(n) \geq \lceil \log_2 n! \rceil$.

This obvious bound is NOT optimal. Van Voorhis An improved lower bound for sorting networks proves $S(n) \geq S(n-1) + \lceil \log_2 n \rceil$, giving $S(n) \geq \sum_{k=1}^n \lceil \log_2 k \rceil$, which is $> \left \lceil \sum_{k=1}^n \log_2 k \right\rceil = \lceil \log_2 n! \rceil$ as soon as $n \geq 5$. Van Voorhis later improved that bound further in Toward a lower bound for sorting networks.

It is possible (but I have no real idea) that you could extend Van Voorhis' proof to deal with generators other than transpositions.

If you are okay with just getting $\sum_{k=1}^n \lceil \log_2 k \rceil$, the following construction works (using $\alpha_i$ which are not transpositions). Let $\beta_{kr}$ be $(12\cdots k)^{2^r}$. Let the list of $\alpha$'s be $$\beta_{20} \ \beta_{30} \beta_{31}\ \beta_{40} \beta_{41}\ \beta_{50} \beta_{51} \beta_{52}\ \cdots\ \beta_{n0} \beta_{n1} \cdots \beta_{n \lfloor \log_2 n \rfloor}$$ where the $\beta_{kr}$'s run from $\beta_{k0}$ up to $\beta_{k \lfloor \log_2 k \rfloor}$.

Using base two expansion, we can express any power of $(12 \cdots k)$ as $\beta_{k0}^{c_0} \beta_{k1}^{c_1} \cdots \beta_{kr}^{c_r}$. And any element of $S_n$ is of the form $(12)^{a_2} (123)^{a_3} \cdots (12 \cdots n)^{a_n}$.

$\endgroup$
1
  • $\begingroup$ This certainly clarifies $\alpha_{\sigma(1)}^{b_1}\alpha_{\sigma(2)}^{b_2}\dots\alpha_{\sigma(k)}^{b_{k}}$ for $\sigma = id$. Can we extend this to atleast say $\sigma\in C_k$ which is cyclic group on $k$ elements? $\endgroup$
    – Turbo
    Dec 2, 2014 at 3: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.