Representing random permutations as the product of two involutions

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.