What is the probability that two random permutations have the same order? That is the question asked by this MathOverflow question from 2016, and considered again in this paper of Acan, Burnette, Schmutz, and Thomas from last month. It’s an innocuous-sounding question that turns out to encapsulate some rather subtle analytic combinatorics.
You haven’t got started until you realize : this is the probability that both and are -cycles. In fact since and have the same order whenever they are conjugate, we can say
This latter probability gets a significant contribution from every conjugacy class which is a nearly an -cycle, specifically which contains an -cycle for . Suppose consists of an -cycle as well as cycles of length for each , where . Then the probability that is
If we sum this over all choices of and , we get , where
and it’s not too hard to see that all other conjugacy classes contribute negligibly. As far as I know this asymptotic was original observed by Flajolet, Fusy, Gourdon, Panario, and Pouyanne (see Proposition 4).
This isn’t the full story for , since there are pairs of different conjugacy classes which contribute significantly, such as the cycle types and if is even, or and if is odd. It’s also clear from this example that the arithmetic of is now relevant. But at least a natural approach is suggested.
Assume that the main contribution comes from conjugacy classes of the shape , where and is a partition of . The order is given by
Now as long as is bounded, the only way we can get a collision between two of these is if the two factors separated by collide separately. If we sum over such colliding pairs, we should get a rather complicated arithmetical almost-periodic function of , but at least one we can try to understand with a computer.
But if you do this, a rather strange picture develops. Counting only those conjugacy classes with , we get the following picture.
Notice the drop at exactly , where we arbitrarily decided to limit . What this is saying is that our assumption, that the main contribution comes from , was faulty.
After thinking further along these lines I contributed an answer to the MO question which proves that is infinitely often at least roughly , and in particular . But it really looks like there is more to understand here. Even though the in my MO answer are very particular, and the lower bound very weak, I’m still tempted to conjecture that . And it would be nice to know the true order of magnitude!
In case anybody wants to reproduce or extend my calculations, here is my colab notebook.