Enumerating coprime permutations. Issue 4 (25th August 2022)

• Record Type: Journal Article
• Authors: Sah, Ashwin; Sawhney, Mehtaab
• Is Part Of: Mathematika. Volume 68:Issue 4(2022)
• Page Start: 1120
• Page End: 1134
• Publication Date: 2022-08-25
• Subjects: Mathematics -- Periodicals; 510.5
• DOI: 10.1112/mtk.12159
• Languages: English
• ISSNs: 0025-5793

Abstract

Abstract: Define a permutation σ to be coprime if gcd ( m, σ ( m ) ) = 1 $\gcd (m, \sigma (m)) = 1$ for m ∈ [ n ] $m\in [n]$ . In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on [ n ] is n ! · ( c + o ( 1 ) ) n $n!\cdot (c+o(1))^n$ where c = ∏ p prime ( p − 1 ) 2 ( 1 − 1 / p ) p · ( p − 2 ) ( 1 − 2 / p ) . \begin{equation*} c = \prod _{p\text{ prime }}\frac{(p-1)^{2(1-1/p)}}{p\cdot (p-2)^{(1-2/p)}}. \end{equation*} The techniques involve entropy maximization for the upper bound, and a mixture of number‐theoretic bounds, permanent estimates, and the absorbing method for the lower bound.