Representing random permutations as the product of two involutions

Abstract

An involution is a permutation that is its own inverse. Given a permutation $\sigma$ of $[n]$, let $N_n(\sigma )$ denote the number of ways to write $\sigma$ as a product of two involutions of $[n]$. If we endow the symmetric groups $S_n$ with uniform probability measures, then the random variables $N_n$ are asymptotically lognormal.

The proof is based upon the observation that, for most permutations $\sigma$, $N_n(\sigma )$ can be well-approximated by $B_n(\sigma )$, the product of the cycle lengths of $\sigma$. Asymptotic lognormality of $N_n$ can therefore be deduced from Erdős and Turán’s theorem that $B_n$ is itself asymptotically lognormal.