The Rényi entropy of the order of a random permutation

Abstract

We study the distribution of the order of a random permutation of $[n]$ through the lens of Rényi entropy. In particular, we obtain an asymptotic for the Rényi $q$-entropy of the order in the full range $1\le q\le \infty$. For $q>1$, our results are quantitatively optimal and reveal a tight connection between the asymptotic behaviour of the Rényi $q$-entropy and arithmetic properties of $n$. Of particular interest are the cases $q=\infty$ and $q=2$, which correspond to the maximum probability of achieving a particular order and the probability that two independent random permutations have equal orders, respectively. In the former case, we show that the probability in question is asymptotic to $1/n$ and additionally characterise the maximiser for sufficiently large $n$. In the latter case, we determine a minimal and maximal order for the probability as a function of $n$, of respective forms $c/n^2$ and ${\log }^{\ast }n/n^2$. Our results provide an essentially complete answer to a set of questions raised by Acan, Burnette, Eberhard, Schmutz and Thomas, some of which go back to work of Erdős and Turán from the 1960s.

25 pages; this article supersedes arXiv:2510.11698