If $G$ is a finite group and $A \subseteq G$ a set of generators, the diameter $diam(G,A)$ is the least integer $d$ such that $A^d=G$.

Now consider the symmetric group $S_n$ and the subset $A_n = \{(12...n), (12) \}$. It is known that $diam(S_n,A_n) \asymp n^2$.

There exist a set of generators $A_n$ of bounded cardinality such that $diam(S_n,A_n) \ll n \log n$?

  • 2
    $\begingroup$ No, because if $|A_n| \le k$ then $|A_n^n| \le k^n < n!$ for all sufficiently large $n$. $\endgroup$ – Derek Holt Sep 21 '18 at 16:24
  • $\begingroup$ Ok, I missed something. The right bound is $\ll n \log n$, which is actually $\sim \log n!$. $\endgroup$ – Luca Sabatini Sep 21 '18 at 16:35

If $\lvert A_n\rvert=m$, then we have $\lvert A_n^n\rvert\le m^n$. But if $m$ is bounded, this grows more slowly than $n!$.

Edit: The question has changed. $n\log n$ is attainable, with $\lvert A_n\rvert=3$. The idea is to consider the set of $n$ points being moved as $\mathbb{Z}_{n-1}\cup\{\infty\}$. Then you define two linear transformations $\sigma_0,\sigma_1$ on $\mathbb{Z}_{n-1}$ such that you can go from $0$ to any other $m\in\mathbb{Z}_{n-1}$ in $\log n$ steps. The third generator is the transposition $(0,\infty)$.

Then you can get any transposition $(m,\infty)$ in $\log n$ steps, and since $(m,n)=(m,\infty)(n,\infty)(m,\infty)$, and you can write any permutation with $n$ transpositions, the diameter is $n\log n$.

The source for this is the paper On the diameter of finite groups (PDF), section 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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