Skip to main content
MathOverflow

Return to Answer

added 192 characters in body
Source Link
Ofir Gorodetsky
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

A visible permutation has been dubbed coprime permutation in a recent paper of Pomerance ("Coprime permutations", Integers 22, Paper A83, 20 p. (2022)).

Pomerance proved that the density of coprime permutations within $S_n$, the symmetric group on $\{1,2,\ldots,n\}$, is at most $1/2.5^n$ and at least $1/3.73^n$ (at least for all sufficiently large $n$).

It is pointed out in the same paper that the number of coprime permutations in $S_n$ has been studied as early as 1977, in the paper "The combinatorial interpretation of the Jacobi identity from Lie algebra" of D. M. Jackson (J. Combin. Theory, A 23 (1977), 233-256) and has an OEIS page (sequence A005326). As noted by Jackson, this number is the permanent of the $n\times n$ matrix $B$ given by $b_{i,j} = 1$ if $\gcd(i,j)=1$ and by $b_{i,j}=0$ otherwise.

In Section 5, Pomerance conjectures that the density is $1/(c_0+o(1))^n$ as $n \to \infty$, for some constant $c_0 \in [2.5, 3.73]$. He presents a heuristic of McNew which suggests $c_0 = \prod_p \frac{p(p-2)^{1-2/p}}{(p-1)^{2(1-1/p)}}$ where the product is over all primes $p$ (the factor at $p=2$ is interpreted as $2$).

This conjecture of Pomerance was resolved by Sah and Sawhney in "Enumerating coprime permutations" (Mathematika 68, No. 4, 1120-1134 (2022)), with the same $c_0$ as conjectured by McNew.

In fact, they make the $o(1)$ term somewhat explicit: the density is $1/(c_0+f(n))^n$ where $f(n)$ tends to $0$ at least as quickly as $e^{-c \sqrt{\log n \log \log n}}$ for some $c>0$.

A visible permutation has been dubbed coprime permutation in a recent paper of Pomerance ("Coprime permutations", Integers 22, Paper A83, 20 p. (2022)).

Pomerance proved that the density of coprime permutations within $S_n$, the symmetric group on $\{1,2,\ldots,n\}$, is at most $1/2.5^n$ and at least $1/3.73^n$ (at least for all sufficiently large $n$).

It is pointed out in the same paper that the number of coprime permutations in $S_n$ has been studied as early as 1977, in the paper "The combinatorial interpretation of the Jacobi identity from Lie algebra" of D. M. Jackson (J. Combin. Theory, A 23 (1977), 233-256) and has an OEIS page (sequence A005326). As noted by Jackson, this number is the permanent of the $n\times n$ matrix $B$ given by $b_{i,j} = 1$ if $\gcd(i,j)=1$ and by $b_{i,j}=0$ otherwise.

In Section 5, Pomerance conjectures that the density is $1/(c_0+o(1))^n$ as $n \to \infty$, for some constant $c_0 \in [2.5, 3.73]$. He presents a heuristic of McNew which suggests $c_0 = \prod_p \frac{p(p-2)^{1-2/p}}{(p-1)^{2(1-1/p)}}$ where the product is over all primes $p$ (the factor at $p=2$ is interpreted as $2$).

This conjecture of Pomerance was resolved by Sah and Sawhney in "Enumerating coprime permutations" (Mathematika 68, No. 4, 1120-1134 (2022)), with the same $c_0$ as conjectured by McNew.

A visible permutation has been dubbed coprime permutation in a recent paper of Pomerance ("Coprime permutations", Integers 22, Paper A83, 20 p. (2022)).

Pomerance proved that the density of coprime permutations within $S_n$, the symmetric group on $\{1,2,\ldots,n\}$, is at most $1/2.5^n$ and at least $1/3.73^n$ (at least for all sufficiently large $n$).

It is pointed out in the same paper that the number of coprime permutations in $S_n$ has been studied as early as 1977, in the paper "The combinatorial interpretation of the Jacobi identity from Lie algebra" of D. M. Jackson (J. Combin. Theory, A 23 (1977), 233-256) and has an OEIS page (sequence A005326). As noted by Jackson, this number is the permanent of the $n\times n$ matrix $B$ given by $b_{i,j} = 1$ if $\gcd(i,j)=1$ and by $b_{i,j}=0$ otherwise.

In Section 5, Pomerance conjectures that the density is $1/(c_0+o(1))^n$ as $n \to \infty$, for some constant $c_0 \in [2.5, 3.73]$. He presents a heuristic of McNew which suggests $c_0 = \prod_p \frac{p(p-2)^{1-2/p}}{(p-1)^{2(1-1/p)}}$ where the product is over all primes $p$ (the factor at $p=2$ is interpreted as $2$).

This conjecture of Pomerance was resolved by Sah and Sawhney in "Enumerating coprime permutations" (Mathematika 68, No. 4, 1120-1134 (2022)), with the same $c_0$ as conjectured by McNew.

In fact, they make the $o(1)$ term somewhat explicit: the density is $1/(c_0+f(n))^n$ where $f(n)$ tends to $0$ at least as quickly as $e^{-c \sqrt{\log n \log \log n}}$ for some $c>0$.

Source Link
Ofir Gorodetsky
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

A visible permutation has been dubbed coprime permutation in a recent paper of Pomerance ("Coprime permutations", Integers 22, Paper A83, 20 p. (2022)).

Pomerance proved that the density of coprime permutations within $S_n$, the symmetric group on $\{1,2,\ldots,n\}$, is at most $1/2.5^n$ and at least $1/3.73^n$ (at least for all sufficiently large $n$).

It is pointed out in the same paper that the number of coprime permutations in $S_n$ has been studied as early as 1977, in the paper "The combinatorial interpretation of the Jacobi identity from Lie algebra" of D. M. Jackson (J. Combin. Theory, A 23 (1977), 233-256) and has an OEIS page (sequence A005326). As noted by Jackson, this number is the permanent of the $n\times n$ matrix $B$ given by $b_{i,j} = 1$ if $\gcd(i,j)=1$ and by $b_{i,j}=0$ otherwise.

In Section 5, Pomerance conjectures that the density is $1/(c_0+o(1))^n$ as $n \to \infty$, for some constant $c_0 \in [2.5, 3.73]$. He presents a heuristic of McNew which suggests $c_0 = \prod_p \frac{p(p-2)^{1-2/p}}{(p-1)^{2(1-1/p)}}$ where the product is over all primes $p$ (the factor at $p=2$ is interpreted as $2$).

This conjecture of Pomerance was resolved by Sah and Sawhney in "Enumerating coprime permutations" (Mathematika 68, No. 4, 1120-1134 (2022)), with the same $c_0$ as conjectured by McNew.