I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one expects that the probability for two permutations of $\frak S\_n$ to have the same order goes to 0 as n goes to infinity. Indeed experimentally this seems to happen with speed $O(1/n^2)$


I know that Wilf proved an asymptotic for a permutation in $\frak S\_n$ to be of order $d$ (<https://www.math.upenn.edu/~wilf/website/Asymptotics%20of%20exp%28P%28z%29%29.pdf>) but I don't think it can be used directly. 


On the other hand it is clear that the probability that two permutations have same order is more than probability that two permutations are conjugate. This is $K/n^2$ according to Flajolet et al. (<http://arxiv.org/abs/math/0606370>), but here again I failed to generalize the method for the order.



What is the probability that two random permutations have the same order?
Nice problem! I claim that $\limsup n^2 p(n) = \infty$.


Suppose $k < n/2$ is such that $n-k$ is divisible by $L\_k = \text{lcm}(1,2,\dots,k)$. Then if $\pi \in S\_n$ has a cycle of length $n-k$ (this happens with probability $1/(n-k)$) then $\text{ord}(\pi) = n-k$, so the probability gets a contribution of $1/(n-k)^2 \geq 1/n^2$ from such $\pi$. Let $K\_n$ be the set of all such $k$. Then $p(n) \geq |K\_n|/n^2$.


Now the great thing about $n \mapsto K\_n$ is that it is "lower semicontinuous on $\widehat{\mathbf{Z}}$". What I mean is this: Suppose $K = K\_n$, and let $k = \max K$. Then the condition that $K\_n \supset K$ is $L\_k$-periodic, so provided we alter $n$ only by multiples of $L\_k$, the set $K\_n$ can only get bigger. Moreover, note that we would have $n \in K\_n$, except for our stipulation that $k < n/2$. It follows that
$$
 K\_{n + L\_n} \supset K\_n \cup \{n\}.
$$
This shows that $|K\_n|$ gets arbitrarily large, which proves the claim.


I have no idea about the $\liminf$! The above argument constructs very particular $n$ (of the shape $n\_1 + \dots + n\_k$, where each $n\_i$ is large and highly divisible in comparison with $n\_{i-1}$), and the lower bound is very weak besides (roughly $\log^\*(n)/n^2$), so it's tempting to conjecture that the $\liminf$ is finite. But I'm not sure this is supported by the numerics. From the numerics it just looks like we're forgetting something.


