Prime Number Theorem · aiwiki.page

The prime number theorem is a fundamental result in number theory describing the large-scale distribution of prime numbers. If $\pi(x)$ counts the primes not exceeding $x$ , the theorem states that $\pi(x)\sim x/\log x$ as $x$ tends to infinity, where $\log$ denotes the natural logarithm. Thus, although individual primes occur irregularly, their cumulative number follows a precise asymptotic law. Jacques Hadamard and Charles-Jean de la Vallée Poussin independently proved the theorem in 1896. (dlmf.nist.gov)

Statement and interpretation

The prime-counting function is defined by

\pi(x)=\#\{p\leq x:p\text{ is prime}\}.

The prime number theorem asserts

\boxed{\pi(x)\sim\frac{x}{\log x}},

or, equivalently,

\lim_{x\to\infty}\frac{\pi(x)\log x}{x}=1.

Here the symbol $\sim$ means that the ratio of the two expressions approaches $1$ ; it does not mean that their difference approaches zero. (dlmf.nist.gov)

In terms of a limit, the statement says that for every $\varepsilon>0$ , there is a threshold $X$ such that

(1-\varepsilon)\frac{x}{\log x} < \pi(x) < (1+\varepsilon)\frac{x}{\log x} \qquad(x>X).

This is a reformulation of the theorem: its basic content concerns relative error, rather than an exact count or a specified rate of convergence. (terrytao.wordpress.com)

A direct consequence is

\frac{\pi(x)}{\lfloor x\rfloor}\sim\frac{1}{\log x}.

Accordingly, the probability that an integer chosen uniformly from $1,\ldots,\lfloor x\rfloor$ is prime is asymptotic to $1/\log x$ . This probability tends to zero, even though there are infinitely many primes. The probabilistic interpretation concerns the method of sampling integers, not randomness inherent in the primes themselves. (dlmf.nist.gov)

Equivalent formulations

Let $p_n$ denote the $n$ th prime, with

p_1=2,\quad p_2=3,\quad p_3=5,\ldots.

An equivalent formulation is

p_n\sim n\log n.

Thus the theorem can describe either the number of primes below a given bound or the approximate size of a prime with a given index. (dlmf.nist.gov)

For proofs, it is often more convenient to count primes with logarithmic weights. The Chebyshev functions are

\vartheta(x)=\sum_{p\leq x}\log p, \qquad \psi(x)=\sum_{p^k\leq x}\log p,

where the second sum includes every prime power $p^k$ , with $k\geq1$ . The theorem is equivalent to either of the statements

\vartheta(x)\sim x, \qquad \psi(x)\sim x.

The contributions from powers with $k\geq2$ are asymptotically smaller than $x$ , so they do not change the leading term. (math.ucdavis.edu)

Using the von Mangoldt function,

\Lambda(n)= \begin{cases} \log p,&n=p^k\text{ for a prime }p\text{ and }k\geq1,\\ 0,&\text{otherwise}, \end{cases}

one can write

\psi(x)=\sum_{n\leq x}\Lambda(n).

This weighted formulation connects prime counting to analytic identities more directly than the unweighted function $\pi(x)$ . (terrytao.wordpress.com)

Historical development

The conjecture emerged from numerical investigations in the late eighteenth century. Carl Friedrich Gauss later recalled recognizing the approximate logarithmic density of primes in 1792 or 1793. Adrien-Marie Legendre published a related conjecture in 1798, proposing an approximation of the form

\frac{x}{A\log x+B}.

These investigations identified the correct leading scale before a proof was available. (publications.ias.edu)

In the nineteenth century, Pafnuty Chebyshev established upper and lower bounds of the correct order of magnitude. These showed that prime counting grows on the scale $x/\log x$ , but did not establish that the ratio tends to exactly $1$ . Bernhard Riemann introduced a decisive analytic perspective in his 1859 work linking primes to the complex zeros of the zeta function. (math.ucdavis.edu)

Hadamard and de la Vallée Poussin completed the first proofs in 1896 using complex analysis. In 1948, Atle Selberg and Paul Erdős developed elementary proofs, which were published in 1949. Here elementary means that the proofs avoid complex function theory; it does not mean that the arguments are short or easy. (terrytao.wordpress.com)

Analytic proof and the zeta function

The central analytic object is the Riemann zeta function,

\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}, \qquad \operatorname{Re}(s)>1.

The fundamental theorem of arithmetic gives its Euler product:

\zeta(s)=\prod_p(1-p^{-s})^{-1}.

This identity encodes prime factorization in a function of a complex variable. Taking a logarithmic derivative yields

-\frac{\zeta'(s)}{\zeta(s)} =\sum_{n=1}^{\infty}\frac{\Lambda(n)}{n^s}, \qquad \operatorname{Re}(s)>1.

Consequently, the analytic behavior of $\zeta$ governs sums involving $\Lambda$ . (terrytao.wordpress.com)

Through analytic continuation, the zeta function extends beyond the region where its defining series converges. It has a simple pole at $s=1$ . The decisive additional fact is that it has no zeros on the line

\operatorname{Re}(s)=1.

Together with suitable analytic arguments, this nonvanishing establishes $\psi(x)\sim x$ , and hence the prime number theorem. Conversely, the theorem implies this nonvanishing property. The pole supplies the main term, while zeros control deviations from it. (terrytao.wordpress.com)

Elementary proofs

Selberg’s elementary approach begins with an asymptotic identity known as the Selberg symmetry formula:

\sum_{n\leq x}\Lambda(n)\log n + \sum_{ab\leq x}\Lambda(a)\Lambda(b) = 2x\log x+O(x).

The second sum runs over positive integers $a,b$ with $ab\leq x$ . The formula couples a weighted prime-power count to products of two such weights. (terrytao.wordpress.com)

Additional estimates turn this relation into control of the error in $\psi(x)$ , eventually showing that it is $o(x)$ . The elementary proofs demonstrate that complex analysis is not logically indispensable to the theorem, although it provides a particularly powerful framework for understanding stronger estimates and generalizations. (terrytao.wordpress.com)

More accurate approximations and error terms

A more informative approximation is the logarithmic integral. Using the nonsingular normalization

\operatorname{Li}_2(x)=\int_2^x\frac{dt}{\log t},

one has

\operatorname{Li}_2(x)\sim\frac{x}{\log x}.

It differs by a constant from the conventional principal-value function $\operatorname{li}(x)$ , so this choice does not affect the asymptotic estimates discussed here. (terrytao.wordpress.com)

Repeated integration by parts gives the asymptotic expansion

\operatorname{Li}_2(x) = \frac{x}{\log x} \left( 1+\frac{1}{\log x} +\frac{2!}{(\log x)^2} +\cdots+ \frac{m!}{(\log x)^m} \right) + O\!\left(\frac{x}{(\log x)^{m+2}}\right)

for each fixed nonnegative integer $m$ . This is an expansion with finitely many retained terms, not a convergent infinite series. Corresponding expansions hold for $\pi(x)$ . (dlmf.nist.gov)

A classical unconditional estimate, written using big-O notation, is

\pi(x)=\operatorname{Li}_2(x) + O\!\left(xe^{-c\sqrt{\log x}}\right)

for some constant $c>0$ . The Vinogradov–Korobov estimate improves this to

\pi(x)=\operatorname{Li}_2(x) + O\!\left( x\exp\!\left[ -c(\log x)^{3/5}(\log\log x)^{-1/5} \right]\right).

Both quantify convergence far more precisely than the basic theorem. (dlmf.nist.gov)

The Riemann hypothesis asserts that all nontrivial zeta zeros have real part $1/2$ . It would imply the substantially stronger estimate

\pi(x)=\operatorname{Li}_2(x)+O(\sqrt{x}\log x).

The prime number theorem itself requires a weaker zero-free statement and does not depend on assuming the Riemann hypothesis. (terrytao.wordpress.com)

Arithmetic progressions

An important generalization concerns primes in residue classes, expressed through modular arithmetic. For fixed positive integer $q$ and integer $a$ satisfying $\gcd(a,q)=1$ , define

\pi(x;q,a)=\#\{p\leq x:p\equiv a\pmod q\}.

Then

\pi(x;q,a)\sim \frac{1}{\varphi(q)}\frac{x}{\log x},

where Euler’s totient function $\varphi(q)$ counts the residue classes relatively prime to $q$ . Thus primes are asymptotically equally distributed among the admissible classes for a fixed modulus. (dlmf.nist.gov)

The requirement that $q$ remain fixed matters: uniform estimates when the modulus grows with $x$ require additional results. Analytic proofs of this generalization use Dirichlet $L$ -functions, extending the role played by the zeta function in the ordinary theorem. (terrytao.wordpress.com)

Consequences and limitations

Subtracting the theorem’s estimates at $x$ and $Ax$ , for any fixed $A>1$ , gives

\pi(Ax)-\pi(x)\sim\frac{(A-1)x}{\log x}.

This derived statement counts primes in intervals whose length is a fixed proportion of their starting point. It does not automatically provide comparable estimates in much shorter intervals, because the errors in two cumulative counts can exceed the number being sought. (terrytao.wordpress.com)

Likewise, the approximation $1/\log x$ describes a large-scale frequency, not the probability of primality for an unspecified individual integer. The theorem neither determines exact prime locations nor establishes independence between primality at neighboring integers. Questions about prescribed patterns, such as pairs of primes differing by $2$ , require information beyond an asymptotic count of single primes. (terrytao.wordpress.com)

References

DLMF: §27.2 Functionsdlmf.nist.gov
DLMF: §27.12 Asymptotic Formulas: Primesdlmf.nist.gov
246B, Notes 4: The Riemann zeta function and the prime number theoremterrytao.wordpress.com
The Prime Number Theoremmath.ucdavis.edu
The Prime Number Theorempublications.ias.edu
Not Always Buried Deep: A Second Course in Elementary Number Theorypollack.uga.edu
Structure and randomness in the prime numbersterrytao.wordpress.com
Expository articlesterrytao.wordpress.com
A Banach algebra proof of the prime number theoremterrytao.wordpress.com
254A, Notes 2: Complex-analytic multiplicative number theoryterrytao.wordpress.com