Base for symmetric group 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
 A: 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}$.
