# Diameter of the Symmetric group

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

• No, because if $|A_n| \le k$ then $|A_n^n| \le k^n < n!$ for all sufficiently large $n$. – Derek Holt Sep 21 '18 at 16:24
• Ok, I missed something. The right bound is $\ll n \log n$, which is actually $\sim \log n!$. – 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$$.