Show that for all L(n)<2^n for all n ∈ N
Where Landau’s function L(n) is defined for every n ∈ N to be the largest order of an element of Sn.
I have proven by induction, that n<2^n for all n ∈ N.
L(n) is the largest order of an element of Sn.
I know if f∈Sn, then it has a decomposition f=α1 .... αk where each of the αi are disjoint cycles with lengths ri. Then the order of f is the least common multiple of the lengths, i.e. lcm(r1,...,rk).
I want to show that no such least common multiple is more than 2n.
But how do I do this from proving n<2^n
Does proving this let you know that the order of any n-cycle is at most 2n, since the order of an n-cycle is just n. But what would I do from here?
Thank you
Take that cycle decomposition you have. The order of the permutation is the least common multiple of the cycle lengths, so it's less than or equal to the product of the cycle lengths $r_1\cdot r_2\cdot r_3\cdots r_k$. But then, $n=r_1+r_2+r_3+\cdots+r_k$, so $2^n = 2^{r_1+r_2+r_3+\cdots+r_k} = 2^{r_1}\cdot 2^{r_2}\cdot 2^{r_3}\cdots 2^{r_k}$. For each term in the products, $r_j < 2^{r^j}$ (and they're positive), so the same inequality applies for the products.