Random Permutations

What is the probability ${p(n)}$ that two random permutations ${\pi_1, \pi_2 \in S_n}$ 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 ${p(n) \geq 1/n^2}$ : this is the probability that both ${\pi_1}$ and ${\pi_2}$ are ${n}$ -cycles. In fact since ${\pi_1}$ and ${\pi_2}$ have the same order whenever they are conjugate, we can say

$\displaystyle \mathbf{P}(\textup{ord}(\pi_1) = \textup{ord}(\pi_2)) \geq \mathbf{P}(\pi_1 \sim \pi_2).$

This latter probability gets a significant contribution from every conjugacy class ${\mathfrak{c}}$ which is a nearly an ${n}$ -cycle, specifically which contains an ${(n-k)}$ -cycle for ${k=O(1)}$ . Suppose ${\mathfrak{c}}$ consists of an ${(n-k)}$ -cycle as well as ${c_j}$ cycles of length ${j}$ for each ${j\geq 0}$ , where ${\sum j c_j = k}$ . Then the probability that ${\pi_1, \pi_2 \in \mathfrak{c}}$ is

$\displaystyle \frac1{(n-k)^2} \prod_{j\geq 0} \left( \frac1{j^{c_j} c_j!} \right)^2 \sim \frac1{n^2} \prod_{j\geq 0} \left( \frac1{j^{c_j} c_j!}\right)^2.$

If we sum this over all choices of ${k}$ and ${(c_j)}$ , we get ${\Delta / n^2}$ , where

$\displaystyle \Delta = \exp \sum_{j \geq 0} \frac1{j^{2c} c!^2} = 4.26\dots,$

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 ${p(n)}$ , since there are pairs of different conjugacy classes which contribute significantly, such as the cycle types ${(n-2, 2)}$ and ${(n-2, 1, 1)}$ if ${n}$ is even, or ${(n-3, 2, 1)}$ and ${(n-3, 1, 1, 1)}$ if ${n}$ is odd. It’s also clear from this example that the arithmetic of ${n}$ is now relevant. But at least a natural approach is suggested.

Assume that the main contribution comes from conjugacy classes of the shape ${(n-k, \lambda)}$ , where ${k=O(1)}$ and ${\lambda}$ is a partition of ${k}$ . The order is given by

$\displaystyle \textup{lcm}(n-k, \textup{lcm}(\lambda)) = \frac{\textup{lcm}(\lambda)}{\textup{gcd}(\textup{lcm}(\lambda), n-k)} \times (n-k).$

Now as long as ${k}$ is bounded, the only way we can get a collision between two of these is if the two factors separated by ${\times}$ collide separately. If we sum over such colliding pairs, we should get a rather complicated arithmetical almost-periodic function of ${n}$ , 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 ${k\leq 50}$ , we get the following picture.

Notice the drop at exactly ${n=50}$ , where we arbitrarily decided to limit ${k}$ . What this is saying is that our assumption, that the main contribution comes from ${k=O(1)}$ , was faulty.

After thinking further along these lines I contributed an answer to the MO question which proves that ${p(n)}$ is infinitely often at least roughly ${\log^*(n)/n^2}$ , and in particular ${\limsup p(n) n^2 = \infty}$ . But it really looks like there is more to understand here. Even though the ${n}$ in my MO answer are very particular, and the lower bound very weak, I’m still tempted to conjecture that ${\liminf p(n) n^2 = \infty}$ . 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.

Random Permutations

Probability that two permutations have the same order

latex2wp: a tool for converting LaTeX to WordPress-ready HTML