1. Enumerating coprime permutations
- Author
-
Sah, Ashwin and Sawhney, Mehtaab
- Subjects
Mathematics - Number Theory ,Mathematics::Number Theory ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Number Theory (math.NT) ,Combinatorics (math.CO) - Abstract
Define a permutation $\sigma$ to be coprime if $\gcd(m,\sigma(m)) = 1$ for $m\in[n]$. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on $[n]$ is $n!\cdot (c+o(1))^n$ where \[c = \prod_{p\text{ prime }}\frac{(p-1)^{2(1-1/p)}}{p\cdot (p-2)^{(1-2/p)}}.\] 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., Comment: 11 pages; simplified proof with improved quantitative aspects
- Published
- 2022