For which $n≥2$ does there exist $\sigma\in A_n$ with $|\sigma| > n$ For which $n≥2$ does there exist $\sigma\in A_n$ with $|\sigma| > n$? I have a proof that I'd like to be verified.
My proof that there exists $\sigma\in A_n$ with $|\sigma| > n$ if and only if $n\geq 8$:
For $n<8$, one can manually verify for each $n$ that there is no $\sigma\in A_n$ with order greater than $n$.
Suppose $n\geq 8$.
Case 1: $n$ is even and $3\not\mid n$. Then the permutation $(1,2,3)(4,\dots,n)$
is even and has order $\operatorname{lcm}(3,n-3)=3n-9\geq n+16-9\geq n + 7$.
Case 2: $n$ is even and $3\mid n$. Then $n\geq 12$, so $n-2\geq 8$ is even and is not divisible by 3. Applying Case 1, we see that $(1,2,3)(4,\dots,n-2)\in A_n$ has order at least $n+5$.
Case 3: $n$ is odd. Then apply one of the previous two cases with $n-1$ to get an even permutation with order at least $n+4$.
$\blacksquare$
Is my proof correct?
It doesn't seem very elegant. Is there some slicker proof?

Your reasoning is correct. We can reason that way.
This way is not at all shorter than your way, but it is more instructive.
It seems so to me.

*

*If the number $k$ is even, then lcm$(k-1,k+1)=k^2-1$.


*Now choose k as follows
$$
k=\left\{%
\begin{array}{ll}
    n/2, & \hbox{if $n\equiv0\pmod4$;} \\
    (n-1)/2, & \hbox{if $n\equiv1\pmod4$;} \\
    (n-2)/2, & \hbox{if $n\equiv2\pmod4$;} \\
    (n-3)/2, & \hbox{if $n\equiv3\pmod4$.} \\
\end{array}
\right.
$$


*Let $n\equiv r\pmod4$, where $0\leq r\leq3$. We find
$$
k^2-1>n\Leftrightarrow
k^2-1>2k+r\Leftrightarrow
(k-1)^2>r+2\Leftrightarrow
$$
$$
k>\sqrt{r+2}+1\Leftrightarrow
n>2\sqrt{r+2}+2+r.
$$


*If $r=0$, then $n\geq5$;
if $r=1$, then $n\geq7$;
if $r=2$, then $n\geq8$;
if $r=3$, then $n\geq10$.


*Then the permutation $(1,\ldots, k-1)(k,k+1,\ldots,2k)$ is even and has order
$k^2-1>n$.
