Boundedly Generated Group - Free Groups Are Not Boundedly Generated - Symmetric Groups

Symmetric Groups

The symmetric group S_n can be generated by two elements, a 2-cycle and an n-cycle, so that it is a quotient group of F₂. On the other hand, it is easy to show that the maximal order M(n) of an element in S_n satisfies

log M(n) ≤ n/e

(Edmund Landau proved the more precise asymptotic estimate log M(n) ~ (n log n)1/2). In fact if the cycles in a cycle decomposition of a permutation have length N₁, ..., N_k with N₁ + ··· + N_k = n, then the order of the permutation divides the product N₁ ···N_k, which in turn is bounded by (n/k)k, using the inequality of arithmetic and geometric means. On the other hand, (n/x)x is maximized when x=e. If F₂ could be written as a product of m cyclic subgroups, then necessarily n! would have to be less than or equal to M(n)m for all n, contradicting Stirling's asymptotic formula.