Probability that two permutations have the same order

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.

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

Migrating my blog from Blogger to WordPress turned out to be more trouble than I hoped, because WordPress requires a particular syntax for latex, and several hacks I used to make things display nicely on Blogger just garbled things in WordPress. No one thing was actually complicated to migrate, but taken all together it was just tedious.

I ended up using Luca Trevisan’s latex2wp tool, which converts basic latex into HTML ready to be cut and paste into WordPress. This is great because I can now write and store all blog posts in basic latex, and just change the tool as necessary in the future if I need to move site again, or if WordPress changes its syntax, or whatever.

Since I found the tool so useful I decided to put my own tweaked version on github. As additional features, I’ve added

    • installation by pip,
    • a simple commandline entrypoint,
    • support for simple on-the-fly macros defined with \def.

And no doubt I will find myself adding more features as time goes on! Everything can be found at https://github.com/seaneberhard/latex2wp.