8
$\begingroup$

One version of the Prime Number Theorem is that $p_n \sim n \ \ln \ n$, while by Stirling's formula $\ln(n!) \sim n \ \ln \ n$; consequently, $p_n \sim \ln(n!)$, $\rm \color{red}{\text{and } e^{-p_n} \sim \frac{1}{n!} ^{(*)}}$. Now, each side of the latter formula has a simple interpretation in the context of random permutations of $n$ elements. On the one hand, each possible outcome of a random permutation of $\langle 1,2,\dots,n \rangle$ has probability $\frac{1}{n!}$. On the other hand, the limiting probability (as $n \to\infty)$ that such a random permutation has no fixed point (i.e., that $\mathrm{perm} \langle 1,2,\dots,n \rangle$ does not match $\langle 1,2,\dots,n \rangle$ in any position) is $e^{-1}$; so, for $p_n$ independent random permutations of $\langle 1,2,\dots,n \rangle$, the probability that none of them has a fixed point is $e^{-p_n}$.

Are there "intuitive" grounds for expecting the event $E_n$ := "each of $p_n$ independent random permutations of $n$ elements has no fixed point" to have asymptotic probability $\frac1{n!}$?

$\rm \color{red}{^{(*)} \text{This is a non sequitur and is in fact false, as described in the answer and comments below.}}$

  • 0
    @Qiaochu Yuan: Thanks for the Granville paper -- very interesting.2011-10-18

1 Answers 1

8

There is a flaw in your question. From the fact that $p_n =n\log n+n\log\log n+O(n)$ combined with $\log(n!)\sim n\log n+O(n)$ we see that the asymptotic $e^{p_n}\sim n!$ is impossible. Specifically, $\frac{e^{p_n}}{n!}=\exp(n\log\log n+O(n))=\exp(n\log\log n)\exp\left(1+O\left(\frac{1}{\log\log n}\right)\right)$ $=e^{n\log\log n}\left(1+O\left(\frac{1}{\log \log n}\right)\right),$ whereas $n!\sim e^{p_n}$ is equivalent to $\lim_{n\rightarrow \infty} \frac{e^{p_n}}{n!}=1.$

Remark: A very useful trick to deal with an error term in the exponent is to rearrange until you have $\exp\left(1+O(f(n))\right).$ Assuming $f(n)$ decreases to zero, then $\exp\left(1+O(f(n))\right)=1+O\left(f(n)\right)$ by using the Taylor Expansion.