52 votes
Accepted

Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)

The complex-analytic proof of the prime number theorem can help inform the elementary one. The von Mangoldt function $\Lambda$ is related to the Riemann zeta function $\zeta$ by the formula $$ \sum_n ...
Terry Tao's user avatar
  • 108k
46 votes

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

The PNT is indeed equivalent to $\lim_{x\to\infty} \frac{\psi(x) -x}{x}=0$ which Von Mangoldt's formula and some trivial estimates reduce to proving $$ \lim_{x\to\infty} \sum_{ \zeta(\rho)=0} \frac{x^{...
Will Sawin's user avatar
  • 135k
37 votes

Motivated account of the prime number theorem and related topics

To a certain extent, I think that analytic number theory really is magical, and there's a limit to how natural and motivated it can be. Of the accounts I have seen, the one in Donald Newman's book ...
Timothy Chow's user avatar
  • 78.1k
29 votes

Is there a Kolmogorov complexity proof of the prime number theorem?

Firstly, the proof given there doesn't really show that $p_n = O(n(\log n)^2)$ (at least not without further effort). Instead what it shows is that there are $n$ for which $p_n = O(n(\log n)^2)$, ...
Lucia's user avatar
  • 43.3k
29 votes
Accepted

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

To complement Will Sawin's answer, in the specific context of the prime number theorem, there are historically well-established notions of "elementary" and "non-elementary" proofs, ...
Kostya_I's user avatar
  • 8,642
22 votes
Accepted

A curious prime counting approximation or just data overfitting?

Your heuristic approximation is not correct. It was proved by Turán (1934) that $E_n$ and $V_n$ are both asymptotically $\log\log n$. As a result, the RHS of your display is $$n\frac{\gamma\left(1+o(1)...
GH from MO's user avatar
  • 98.2k
21 votes
Accepted

information-theoretic derivation of the prime number theorem

You may be interested in this arxiv paper [1], "Some information-theoretic computations related to the distribution of prime numbers", Ioannis Kontoyiannis, 2007. It discusses Chebyshev's ...
usul's user avatar
  • 4,429
20 votes

Teaching prime number theorem in a complex analysis class for physicists

"Newman's short proof of the prime number theorem" by Don Zagier might work, in particular since there is an extensive discussion of the steps in that proof in this MSE posting. "The proof has a ...
Carlo Beenakker's user avatar
20 votes
Accepted

Why shouldn't this prove the Prime Number Theorem?

You ask: Denote by $\mu$ the Mobius function. It is known that for every integer $k>1$, the number $\sum_{n=1}^{\infty} \frac{\mu(n)}{n^k}$ can be interpreted as the probability that a randomly ...
20 votes

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

The fundamental problem with using formulas of the kind you described for $\psi(x)$ is that the series $\sum_\rho x^\rho/\rho$ is hard to estimate on its own. The crux of the problem here is that ...
KConrad's user avatar
  • 49.5k
19 votes

Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)

Complementing Terry's nice response, let me try to explain from a more elementary point of view why Selberg's formula (1) is natural, and why it is true. It is natural to formulate the PNT in terms ...
GH from MO's user avatar
  • 98.2k
18 votes
Accepted

Does the Prime Number Theorem have anything to do with Erdos-Kac law or vice versa?

Yes. The number of prime factors of a number is distributed roughly like a Poisson process of expectation $\log \log n$, so the probability of exactly one prime factor is roughly $e^{- \log \log n} = ...
Will Sawin's user avatar
  • 135k
18 votes
Accepted

An explicit value for a bound proof

An explicit version of the Prime Number Theorem required here is Theorem 1.12 on Page 42 of Dusart's thesis. In particular, it follows from this theorem that $$ |\pi(x)-\mathrm{Li}(x)|<x e^{-0.32\...
GH from MO's user avatar
  • 98.2k
18 votes

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

Some historical context may be helpful here. Back in the first half of the twentieth century, mathematics was widely regarded as being stratified into three "tiers": arithmetic, analysis, ...
Timothy Chow's user avatar
  • 78.1k
16 votes
Accepted

Elementary lower bounds for the number of primes in arithmetic progressions

In Section 9 of Diamond, Harold G., Elementary methods in the study of the distribution of prime numbers, Bull. Am. Math. Soc., New Ser. 7, 553-589 (1982). ZBL0505.10021. an argument from Diamond, ...
Terry Tao's user avatar
  • 108k
16 votes
Accepted

Strange and non-strange prime numbers, are there infinitely many of them?

Zsigmondy's Theorem shows that the only strange primes are the Mersenne primes. Indeed, it shows that for any $n\geq 2$ the number $p^n-1$ has a prime factor not dividing $p^k-1$ for any $k<n$, ...
Wojowu's user avatar
  • 27.4k
16 votes
Accepted

Proving Mertens' theorem using the prime number theorem

Well, one can always say that the PNT is equivalent to $$\sum_{p \leq x}\frac{1}{p} = \log \log x + M + o\left(\frac{1}{\log x}\right),\tag{$\ast$}$$ because both results are true (with better error ...
GH from MO's user avatar
  • 98.2k
16 votes
Accepted

Mertens-like theorem

This lies beyond Mertens, in the sense that this variant actually implies the Prime Number Theorem, as will be explained below, while Mertens' theorem is weaker than the PNT. I sketch below a complex ...
Ofir Gorodetsky's user avatar
15 votes

Motivated account of the prime number theorem and related topics

You might like the short (150 page) book by Mazur and Stein: Prime Numbers and the Riemann Hypothesis, Barry Mazur, William Stein, Cambridge University Press, 2016. The discussion is definitely ...
Joe Silverman's user avatar
15 votes
Accepted

A naive question about the prime number theorem

Theorem 1 in the following paper of Ingham shows that the stated estimate, together with $\psi$ being positive and nondecreasing, is 'enough' to deduce that $\psi(x)/x \to 1$: A. E. Ingham: Some ...
so-called friend Don's user avatar
14 votes
Accepted

Motivated account of the prime number theorem and related topics

Let me record a pedestrian answer here. It all starts with Euler's formula $$ \prod_p\left(1-\frac{1}{p^s}\right)^{-1}=\sum_{n\geq 1}\frac{1}{n^s}=:\zeta(s),\quad s>1, $$ and the observation that ...
Kostya_I's user avatar
  • 8,642
13 votes
Accepted

Newman's proof of the prime number theorem

It doesn't seem to me that either article follows the line of reasoning as you have presented it. Indeed, we do not take the integral over the union of integrals $(x_n,(1+\varepsilon)x_n)$. We do get ...
Wojowu's user avatar
  • 27.4k
12 votes
Accepted

$\pi(x+200)-\pi(x)\leq 50$?

Yes. Up to $207$ there are $46$ primes. Hence, the inequality is true for $x \le 7$. Let $$\pi_{210}(x) = \textrm{card}(\{n \in [0,x] \cap \mathbb{N}, \, \gcd(n,210)=1\}).$$ For $x>7$, $\pi(x+200)-\...
Ofir Gorodetsky's user avatar
12 votes
Accepted

Are there highly composite prime gaps?

Assuming the prime tuples conjecture, all of these questions have affirmative answers. For instance, one can use the Chinese remainder theorem to find $a,b$ such that the tuple $$ an+b, \frac{an+b+1}{...
Terry Tao's user avatar
  • 108k
12 votes

Smallest prime factor of numbers

The number of integers $1\leq n\leq x$ with smallest prime factor exceeding $y$ is usually denoted by $\Phi(x,y)$. It has been studied thoroughly. See, for example, Chapter III. 6 (Integers free of ...
GH from MO's user avatar
  • 98.2k
11 votes
Accepted

An extremal problem related either to an uncertainty principle on the circle, or else to the prime number theorem

A compactness argument shows that for sufficiently large $X$ one has the bound $$ \sup_{x \in {\mathbb T} \backslash [-1/X,1/X]} |f(x)| \gg \sup_{x \in [-1/X,1/X]} |f(x)|$$ whenever $f$ is a ...
Terry Tao's user avatar
  • 108k
11 votes

Teaching prime number theorem in a complex analysis class for physicists

A bit easier than the Prime Number Theorem is Dirichlet's Theorem on primes in arithmetic progression. There are lots of proofs around, using complex variables: here is one.
Gerry Myerson's user avatar
11 votes

information-theoretic derivation of the prime number theorem

The following argument seems related in spirit (though it shows far less), but may be of independent interest. Let $X$, $N$, etc, be as you defined. Then $X = p_1^{E_1}\cdots p_k^{E_k}$ where the $...
Kevin K Lin's user avatar
11 votes
Accepted

Asymptotics of $\operatorname{lcm} ((2-1), (3-1), (5-1), (7-1), (11-1), \dotsc, p_n-1 )$

It is true that $\ln L(n)=o(p_n)$ for $n\to+\infty$. To prove it, let us get a bound for contribution of large primes into $\ln L(n)$ and then estimate the contribution of the rest trivially. Choose a ...
Alexander Kalmynin's user avatar
10 votes
Accepted

$n$th prime: a better approximation

You can find an in-depth answer to your question in this paper of de Reyna and Jeremy. See in particular (65)-(66) along with (30) and Theorem 4.9. See also Theorem 6.2.
GH from MO's user avatar
  • 98.2k

Only top scored, non community-wiki answers of a minimum length are eligible