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 ...
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^{...
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 ...
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)$, ...
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, ...
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)...
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 ...
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 ...
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 ...
Community wiki
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 ...
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 ...
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} = ...
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\...
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, ...
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, ...
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)-\...
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}{...
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 ...
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 ...
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.
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 $...
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 ...
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.
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
prime-number-theorem × 153nt.number-theory × 120
prime-numbers × 99
analytic-number-theory × 88
reference-request × 11
riemann-zeta-function × 11
real-analysis × 7
prime-constellations × 7
cv.complex-variables × 6
asymptotics × 6
riemann-hypothesis × 6
algebraic-number-theory × 5
arithmetic-progression × 5
prime-gaps × 5
inequalities × 4
pr.probability × 3
integration × 3
harmonic-analysis × 3
elementary-proofs × 3
prime-ideals × 3
ca.classical-analysis-and-odes × 2
ra.rings-and-algebras × 2
sequences-and-series × 2
it.information-theory × 2
integer-sequences × 2