The following is a piece of math lore from the late forties, which was described in an Intelligencer article entitled "The Elementary Proof of the Prime Number Theorem". It reads:

Turán, who was eager to catch up with the mathematical developments that had occurred during the war, talked with Selberg about his sieve method and his now famous inequality.He tried to talk Selberg into providing a seminar, showing the power of his inequality by giving an elementary proof of Dirichlet’s Theorem on primes in arithmetic progressions; but Selberg, who was busy with other research and was also looking for a permanent academic position, declined. He suggested that Turán present the seminar, using the notes he had made for himself from his conversations with Selberg.

Turán went through with this and afterwards, much to everyone's apparent incredulity, Erdős remarked "I think you can also derive $\frac{p_{n+1}}{p_n} \to 1$, referring to the aforementioned inequality of Selberg." (And, lo and behold, Erdős was able to do just that)

Two questions: (1) what inequality exactly is being referred to here?, and (2) how is Erdős's result deduced?

ADDENDUM: Here was the reason for my confusion. The formula (Selberg's identity) appears very early on in the paper. Then, several pages later we have "...talked with Selberg about his sieve method and now famous inequality" and then in the next paragraph Erdős claims to be able to derive the result from "the inequality". This suggested to me that the referenced inequality had nothing to do with the first identity, but it was instead some well-known sieve-theoretic namesake of Selberg. (Forgive my complete lack of knowledge of sieve theory, but it seemed as if there was nothing sieve-like about the identity, which is why I did not make the connection.)

  • 3
    $\begingroup$ You probably need to make this problem more self-contained - state what Selberg's inequality/sieve are. $\endgroup$ – Thomas Andrews Jan 4 '12 at 19:20
  • $\begingroup$ @Thomas: I've revamped the question. Thank you. $\endgroup$ – Joshua Seaton Jan 4 '12 at 19:33
  • $\begingroup$ I'd guess the Selberg inequality is related to en.wikipedia.org/wiki/Selberg_sieve , but that page has some oddities - for example, it uses $\mu^2(d)$ when $d$ divides a product of distinct primes, and hence it seems like $\mu^2(d)=1$. $\endgroup$ – Thomas Andrews Jan 4 '12 at 19:47
  • 1
    $\begingroup$ springerlink.com/content/u77r1w3523557206 is open access $\endgroup$ – yoyo Jan 4 '12 at 20:19
  • 5
    $\begingroup$ Selbergs Identity states that $$(\psi(x)-x)\log x=-\sum_{n\leq x}\Lambda(n)\left(\psi\left(\frac{x}{n}\right)-\frac{x}{n}\right)+O(x).$$ Alternatively, we can write this as $$\sum_{p\leq x}(\log p)^2+\sum_{pq\leq x}(\log p)(\log q)=2x\log x+O(x).$$ The proof follows by applying the hyperbola method to the sum of $\log^2(n)$, obtaining an asymptotic for $\sum_{n\leq x}\Lambda_2 (n)$ where $\Lambda_2(n)=(\mu*\log^2)(n)$. Before doing this, some large terms are subtracted off based on $d_3(n)=(1*1*1)(n)$ and $d_2(n)=(1*1)(n)$ in a very clever way so that there will be a lot of cancelation. $\endgroup$ – Eric Naslund Jan 7 '12 at 19:28

Eric Naslund explained this in his comments but here is Goldfeld's paper concerning this dispute (see page 6 and 7).

Selberg's historic paper 'An elementary proof of the prime-number theorem' is available and contains the indication : 'Erdős' result was obtained without result of my work, except that it is based on my formula (2.8)' (the second formula showed by Eric). $$\sum_{p\leq x} (\log p)^2+\sum_{pq\leq x} (\log p)(\log q)=2x\log x + O(x).$$

Erdős' article 'On a new method in elementary number theory which leads to an elementary proof of the PNT' starts too with this formula of Selberg and explains that this allowed him to prove that $p_{n+1}/p_n \to 1$ as $n \to \infty$ but also the stronger : for every $c$ there is a positive $\delta(c)$ such that for x sufficiently large we have $$ \pi(x(1+c))-\pi(x)\gt\frac{\delta(c)x}{\log x}$$ He communicated the proof of this to Selberg who deduced the P.N.T.

  • 1
    $\begingroup$ Sorry for the repetition Gerry... $\endgroup$ – Raymond Manzoni Jan 15 '12 at 13:09

The inequality is the displayed equation in the Intelligencer article, also the second display in Eric Naslund's comment. Perhaps you are puzzled as to how an equation can be an inequality, but that is just a feature of the big-O notation.

I think a fair bit of work is needed to deduce the limit result from the inequality (note that Selberg didn't think it was even possible). The elementary proof of the Prime Number Theorem is available in some textbooks and no doubt in various places on the web. I'm not sure whether those proofs establish the limit result on the way, or whether they just ignore the limit result in favor of the big prize, the PNT.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.