Permutations with equal orders. (27th September 2021) - Acan, Huseyin
Abstract: Let ${\mathbb{P}}(ord\pi = ord\pi ')$ be the probability that two independent, uniformly random permutations of [ n ] have the same order. Answering a question of Thibault Godin, we prove that ${\mathbb{P}}(ord\pi = ord\pi ') = {n^{ - 2 + o(1)}}$ and that ${\mathbb{P}}(ord\pi = ord\pi ') \ge {1 \over 2}{n^{ - 2}}lg*n$ for infinitely many n . (Here lg * n is the height of the tallest tower of twos that is less than or equal to n .)