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}}$ where $b_i\in\{0,1\}$?
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}}$ where $b_i\in\{0,1,2,\dots,t\}$ for some fixed $t$?
Are there good references for these problems?
We may use the structure of $S_n$ as a Coxeter group to find $\frac{n(n-1)}{2}$ elements $\alpha_{1,i},\alpha_{2,i},\ldots,\alpha_{n-1,i}$ satisfying this condition where for each $\alpha_{m,i}$ we have $0\leq i< m$. We will extend the definition so that $\alpha_{m,m}$ is the identity for all $m$ to avoid special notation. In that case for each element $x$ there is a unique factorization of the form $$x=\alpha_{1,i_1}\alpha_{2,i_2}\cdots \alpha_{n-1,i_{n-1}}$$
Let $s_1=(1,2),s_2=(2,3),\ldots,s_{n-1}=(n-1,n)$ be the simple transpositions. Then we define $$\alpha_{m,i}=s_{m}s_{m-1}s_{m-2}\cdots s_{i+1}$$ When we expand the product in terms of the simple transpositions and consider the simple transpositions as an ordered alphabet, then this factorization yields the lexicographically smallest minimal-length word for $x$ in terms of the $s_i$. This construction can be found in the text Combinatorics of Coxeter groups by Bjorner and Brenti.