Permutations with equal orders

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 ${\pi}$ and ${\pi'}$ have the same order? Equivalently, what is the “collision entropy” of the random variable ${\textup{ord}\, \pi}$ ? If ${\pi}$ and ${\pi'}$ happen to be conjugate, say if they are both ${n}$ -cycles, then of course they have the same order, which leads to the lower bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \geq \mathbf{P}(\pi \sim \pi') \sim \frac{\Delta}{n^2},$

where ${\Delta \approx 4.26}$ 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

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \sim \frac{\Delta'}{n^2}$

for some other constant ${\Delta'}$ . This guess turns out to be wrong, but only narrowly so. We prove in our paper that

$\displaystyle \limsup \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2 = \infty,$

but that

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \leq n^{-2+o(1)}.$

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:

${\liminf \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is finite.
${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is bounded by a very slowly growing function of ${n}$ , perhaps even ${\log^* n}$ .
The value of ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ depends sensitively on the arithmetic of ${n}$ . In particular, ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ converges along any sequence of the form ${n = m! + \text{constant}}$ .

The proof of the bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') = n^{-2+o(1)}$

requires a lemma that may be interesting more generally. We prove that all except ${n^{-1+\epsilon}}$ permutations ${\pi}$ have order which is divisible by ${\Omega_\epsilon(\log n)}$ primes ${p > n^{\Omega_\epsilon(1)}}$ . In particular, all except ${n^{-1+\epsilon}}$ permutations have order at least ${e^{\Omega_\epsilon(\log^2 n)}}$ . This is a sort of tail bound related to the famous result of Erdős and Turán that ${\log \textup{ord}\, \pi}$ is approximately normal with mean ${\frac12 \log^2 n}$ and variance ${\frac13 \log^3 n}$ . It might be interesting to try to pin this down more exactly: Estimate the probability that ${\textup{ord}\, \pi \leq e^{x \log^2 n}}$ for any given constant ${x>0}$ . The result should be of the form ${n^{-1 + f(x) + o(1)}}$ for some function ${f(x)}$ which tends to zero with ${x}$ .

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 ${2}$ , presumably its final value.

Happy new year everyone.

Permutations with equal orders

Published by Sean Eberhard

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Sean Eberhard

Leave a Reply Cancel reply