Skip to main content
1 of 3
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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

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

Turbo
  • 13.9k
  • 1
  • 27
  • 76