Prime Number Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

The prime-counting function $\map \pi n$, that is, the number of primes less than $n$, satisfies:

$\ds \lim_{n \mathop \to \infty} \map \pi n \frac {\map \ln n} n = 1$

or equivalently:

$\map \pi n \sim \dfrac n {\map \ln n}$

where $\sim$ denotes asymptotic equivalence.


Proof


The validity of the material on this page is questionable.
In particular: The bounds obtained are too tight; the Landau notation calculation does not work
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


The proof presented here is a version of Donald J. Newman's proof. For ease of reading, the proof is broken into parts, with the goal of each part presented.

From the Von Mangoldt Equivalence, the Prime Number Theorem is logically equivalent to:

$\ds \lim_{N \mathop \to \infty} \frac 1 N \sum_{n \mathop = 1}^N \map \Lambda n = 1$

where $\Lambda$ is the von Mangoldt function.


While useful, the von Mangoldt function is a discrete function that is not very much easier to work with than $\map \pi n$ itself.

It behooves us to find another statement equivalent to the Prime Number Theorem.


From Zeta Equivalence to Prime Number Theorem, the Prime Number Theorem is logically equivalent to the statement that:

The average of the first $N$ coefficients of $\dfrac {\zeta'} {\zeta}$ tend to $-1$ as $N$ goes to infinity.


Now we demonstrate the truth of this claim regarding $\dfrac {\zeta'} {\zeta}$.

Doing so proves the Prime Number Theorem.

We know that all of the coefficients of $\zeta$ are precisely $1$.


This article, or a section of it, needs explaining.
In particular: do we?
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.


So the statement:

The average of the first $N$ coefficients of $\dfrac {\zeta'} {\zeta}$ tend to $1$ as $N$ goes to infinity

is equivalent to the statement:

The average of the first $N$ coefficients of $\frac {\zeta'} {\zeta} -\zeta$ tend to $0$ as $N$ goes to infinity.

The latter will be more convenient for our purposes.

We write:

$\dfrac {\map {\zeta'} z} {\map \zeta z} - \map \zeta z = \dfrac 1 {\map \zeta z} \paren {\map {\zeta'} z - \map {\zeta^2} z}$

From Reciprocal of Riemann Zeta Function, Square of Riemann Zeta Function and Derivative of Riemann Zeta Function:

$\ds \frac 1 {\map \zeta z} \paren {\map {\zeta'} z - \map {\zeta^2} z} = \paren {\sum_{n \mathop = 1}^\infty \frac {\map \mu n} {n^z} } \paren {\paren {\sum_{n \mathop = 1}^\infty \frac {\map \ln n} {n^z} } - \paren {\sum_{n \mathop = 1}^\infty \frac {\map {\sigma_0} n} {n^z} } }$

where:

$\map \mu n$ is the Möbius function
$\map {\sigma_0} n$ is the divisor count function.

Given this form of the function, we can see that the average of the first $N$ coefficients is:

$\ds \frac 1 N \sum_{a b \mathop \le N} \paren {\map \mu a \paren {\map \ln b - \map {\sigma_0} b} }$

Hence the Prime Number Theorem is equivalent to the statement that this expression tends to $0$ as $N \to \infty$.


At this point, we can add:

\(\ds 0\) \(=\) \(\ds \dfrac {2 \gamma} N - \dfrac {2 \gamma} N\) where $\gamma$ is the Euler-Mascheroni constant
\(\ds \) \(=\) \(\ds \frac 1 N \sum_{a b \mathop \le N} \paren {\map \mu a \paren {\map \ln b - \map {\sigma_0} b} } + 1 \frac {2 \gamma} N - \frac {2 \gamma} N\)


This article, or a section of it, needs explaining.
In particular: It's not sure what we are trying to do here. We seem to be assuming what we want to prove.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.


From Sum of Möbius Function over Divisors, this $1$ is just:

$\ds 1 = \underbrace {\sum_{a \mathop \divides 1} \map \mu a}_{= 1} + \underbrace {\sum_{a \mathop \divides 2} \map \mu a}_{= 0} + \dots + \underbrace {\sum_{a \mathop \divides N} \map \mu a}_{= 0}$

Hence we continue from the above:

\(\ds 0\) \(=\) \(\ds \frac 1 N \sum_{a b \mathop \le N} \paren {\map \mu a \paren {\map \ln b - \map {\sigma_0} b} } + 1 \frac {2 \gamma} N - \frac {2 \gamma} N\)
\(\ds \) \(=\) \(\ds \frac 1 N \sum_{a b \mathop \le N} \paren {\map \mu a \paren {\map \ln b - \map {\sigma_0} b} } + \frac 1 N \sum_{n \mathop = 1}^N \paren {\sum_{a \mathop \divides n} \map \mu a 2 \gamma} - \frac {2 \gamma} N\)
\(\ds \) \(=\) \(\ds \frac 1 N \sum_{a b \mathop \le N} \paren {\map \mu a \paren {\map \ln b - \map {\sigma_0} b + 2 \gamma} } - \frac {2 \gamma} N\)
\(\ds \) \(=\) \(\ds \frac 1 N \sum_{a \mathop \le N} \map \mu a \map \OO {-\sqrt N} - \frac {2 \gamma} N\) Order of Divisor Count Function
\(\ds \) \(=\) \(\ds \frac 1 N \map o N \map \OO {-\sqrt N} - \frac {2 \gamma} N\)
\(\ds \) \(=\) \(\ds \map \OO {\frac {-1} {\sqrt N} } \map o N - \frac {2 \gamma} N\) Order of Möbius Function


As $N \to \infty$, we have:

$\ds \lim_{N \mathop \to \infty} \paren {\map \OO {\frac {-1} {\sqrt N} } \map o N - \frac {2 \gamma} N}$

which clearly goes to $0$ as $\map \OO {\dfrac {-1} {\sqrt N} }$ dominates $\map o N$.


This article, or a section of it, needs explaining.
In particular: More detail needed in the above.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.



Interpretation

The Prime Number Theorem can also be rendered as:

$\ds \lim_{x \mathop \to \infty} \dfrac {\map \pi x / x} {1 / \ln x} = 1$

where $\dfrac {\map \pi n} n$ can be interpreted as the probability that a number chosen at random will be prime.

Thus, for large $n$, that probability is approximately equal to $\dfrac 1 {\ln n}$.


Also see


Historical Note

The Prime Number Theorem (PNT) was first conjectured by Carl Friedrich Gauss when he was $14$ or $15$, but he was never able to prove it.

He also posited the suggestion that it could be approximated by the Eulerian logarithmic integral $\ds \map \Li x = \int_2^x \frac {\d t} {\map \ln t}$.


It took another century before a proof was found.


Legendre conjectured in $1796$ that there exists a constant $B$ such that $\map \pi n$ satisfies:

$\ds \lim_{n \mathop \to \infty} \map \pi n - \frac n {\map \ln n} = B$

If such a number $B$ exists, then this implies the Prime Number Theorem.

Legendre's guess for $B$ was about $1 \cdotp 08366$, now a historical curiosity known as Legendre's constant.


Pafnuty Lvovich Chebyshev was the first one to provide any support for Gauss's conjecture when he proved in $1850$ that:

$\dfrac 7 8 < \dfrac {\map \pi x} {x / \ln x} < \dfrac 9 8$

for all sufficiently large $x$.

He also proved that if the limit of the expression in question does exist, then its value must be $1$.


In $1891$, Pafnuty Lvovich Chebyshev and James Joseph Sylvester showed that for sufficiently large $x$, there exists at least one prime number $p$ satisfying:

$x < p < \paren {1 + \alpha} x$

where $\alpha = 0 \cdotp 092 \ldots$

Again, since the Prime Number Theorem implies that the above inequality is true for all $\alpha > 0$ for sufficiently large $x$, this constant is also of historical interest only.


Since then, several complete proofs have been discovered.


The first proofs were given independently by Jacques Salomon Hadamard and Charles de la Vallée Poussin in $1896$.

They relied on the theory of functions of a complex variable.

The original theorem of Hadamard used in that proof is given on $\mathsf{Pr} \infty \mathsf{fWiki}$ as Ingham's Theorem on Convergent Dirichlet Series, which is used in Order of Möbius Function, an essential part of the above proof.


Atle Selberg and Paul Erdős would later give an elementary proof of the PNT, in $1948$.

Their proof did not make use of any analytic function theory, and relied entirely on basic properties of logarithms.

Dispute over whether to publish their results jointly or separately created a life-long feud between the two mathematicians.



This page has been identified as a candidate for refactoring of medium complexity.
In particular: Extract the following into their own statement pages with proofs.
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Refactor}} from the code.


While the PNT states that $\map \pi n$ is asymptotic to $\dfrac n {\map \ln n}$, it states nothing about the error of this approximation beyond:

$\map \pi n - \dfrac n {\map \ln n} = \map \OO {n^\alpha}$

where $\alpha < 1$.

This follows from the PNT because if the error was of the form $\map \OO {n^\alpha}, \alpha \ge 1$, the PNT would be false.

Investigations into the error of the approximation to $\map \pi N$ continue, most notably with ongoing research on the Riemann Hypothesis.

If the hypothesis is true, then the error is:

$\map \pi n - \dfrac n {\map \ln n} = \map \OO {\sqrt n \log n}$

If the hypothesis is false, the error is: $\map \OO {n^\alpha}$ for some $\alpha > \dfrac 1 2$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Prime_Number_Theorem&oldid=657631"