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.}}$

  • 4
    This isn't quite the connection you're asking about, but there is an interesting analogy between the cycle decomposition of a random permutation and the prime factorization of a random integer that might be relevant. There is a paper by Granville on the subject: http://www.dms.umontreal.ca/~andrew/PDF/Anatomy.pdf2011-10-18
  • 11
    Beware: $a_n \sim b_n$ need not imply $\exp(a_n) \sim \exp(b_n)$.2011-10-18
  • 0
    Oops ... Back to the drawing board. (Being new to SE, I'm not sure what to do with the posted question now.)2011-10-18
  • 0
    @r.e.s. Please let it stand here. The answer warns eveyone about the flaw, but it is still an interesting line of reasoning.2011-10-18
  • 2
    @r.e.s.: There's nothing wrong with the question. You posed it; someone answered it; if you agree that it was answered, you can accept the answer. There's nothing else to do about it.2011-10-18
  • 0
    @Phira, joriki: Advice taken ... Thanks for the feedback.2011-10-18
  • 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.