Huseyin Acan, Charles Burnette, Eric Schmutz, James Thomas, and I have just uploaded our paper Permutations With Equal Orders to the arXiv.
The motivating question is one that was discussed previously on this blog: what is the probability that two random permutations and have the same order? Equivalently, what is the “collision entropy” of the random variable ? If and happen to be conjugate, say if they are both -cycles, then of course they have the same order, which leads to the lower bound
where is an explicit constant determined by Flajolet, Fusy, Gourdon, Panario, and Pouyanne. It is natural to guess, based on this as well as numerical evidence, that
for some other constant . This guess turns out to be wrong, but only narrowly so. We prove in our paper that
This is certainly not a complete picture, however, and the project is ongoing. Among the things I expect to be true and hope to prove are the following:
- is finite.
- is bounded by a very slowly growing function of , perhaps even .
- The value of depends sensitively on the arithmetic of . In particular, converges along any sequence of the form .
The proof of the bound
requires a lemma that may be interesting more generally. We prove that all except permutations have order which is divisible by primes . In particular, all except permutations have order at least . This is a sort of tail bound related to the famous result of Erdős and Turán that is approximately normal with mean and variance . It might be interesting to try to pin this down more exactly: Estimate the probability that for any given constant . The result should be of the form for some function which tends to zero with .
Incidentally, in terms of arXiv mechanics, we decided to upload our paper as an update to an earlier paper of the other four authors, so this paper might not have appeared in your usual feed. The overlap of this version with the previous one is virtually empty, however, apart from having the same motivating question.
Finally, I’m happy to report that my Erdős number has now fallen to , presumably its final value.
Happy new year everyone.