The Distribution of Primes — The Road to the Prime Number Theorem

We define the prime-counting function pi(x) and trace the path from Chebyshev's estimates to the prime number theorem pi(x) ~ x / ln x. We discuss Mertens' theorems, state Dirichlet's theorem on primes in arithmetic progressions, and survey open problems including the twin prime conjecture and the Riemann hypothesis.

Folio Official

March 1, 2026

1 The Prime-Counting Function

Definition 1 (Prime-counting function).

For a real number

x

, let

π (x) = ∣ {p \leq x ∣ p is prime} ∣

denote the prime-counting function.

Example 2.

π (10) = 4

(the primes

2, 3, 5, 7

π (100) = 25

π (1000) = 168

π (1 0^{6}) = 78498

The central problem in the study of prime distribution is to determine the asymptotic behavior of $π (x)$ as $x \to \infty$ .

2 Chebyshev's Estimates

Definition 3 (Chebyshev functions).

The Chebyshev functions are defined by

θ (x) = \sum_{p \leq x} ln p

and

ψ (x) = \sum_{p^{k} \leq x} ln p = \sum_{n \leq x} Λ (n)

, where

Λ

is the von Mangoldt function.

Theorem 4 (Chebyshev's estimates).

There exist positive constants

c_{1}, c_{2}

such that, for all sufficiently large

x

c_{1} \frac{x}{ln x} \leq π (x) \leq c_{2} \frac{x}{ln x} .

More precisely,

0.92 \cdot x / ln x < π (x) < 1.11 \cdot x / ln x

for

x

sufficiently large.

Proof.

The argument uses the central binomial coefficient

(n 2 n)

. On one hand,

(n 2 n) \leq 4^{n}

(since

(n 2 n) \leq \sum_{k = 0}^{2 n} (k 2 n) = 2^{2 n}

) and

(n 2 n) \geq 4^{n} / (2 n + 1)

(by Stirling's approximation). On the other hand, every prime

p

with

n < p \leq 2 n

divides

(n 2 n)

, so

\prod_{n < p \leq 2 n} p \leq (n 2 n) \leq 4^{n}

. Taking logarithms gives

θ (2 n) - θ (n) \leq n ln 4

. Iterating yields

θ (x) \leq 2 x ln 2

, from which

π (x) \leq c_{2} x / ln x

follows. The lower bound is obtained by a more refined analysis of the prime factorization of

(n 2 n)

. □

3 The Prime Number Theorem

Theorem 5 (Prime number theorem).

π (x) \sim \frac{x}{ln x} (x \to \infty),

that is,

lim_{x \to \infty} \frac{π ( x )}{x / l n x} = 1

Remark 6.

The prime number theorem was proved independently by Hadamard and de la Vallé

ζ (s) = \sum_{n = 1}^{\infty} n^{- s}

, and in particular on the fact that

ζ (s) \neq = 0

on the line

Re (s) = 1

. A more precise approximation is provided by the logarithmic integral

Li (x) = \int_{2}^{x} \frac{d t}{l n t}

: one has

π (x) \sim Li (x)

Theorem 7 (Equivalent formulations of the prime number theorem).

The following are mutually equivalent:

$π (x) \sim x / ln x$ .
$θ (x) \sim x$ .
$ψ (x) \sim x$ .
$p_{n} \sim n ln n$ , where $p_{n}$ denotes the $n$ -th prime.

Proof.

The relation between

θ (x)

and

π (x)

is given by Abel's summation formula (summation by parts):

θ (x) = π (x) ln x - \int_{2}^{x} \frac{π ( t )}{t} d t .

Substituting

π (x) \sim x / ln x

and evaluating yields

θ (x) \sim x

. The converse is proved analogously. □

4 Mertens' Theorems

Theorem 8 (Mertens' theorems).

$p \leq x \sum \frac{1}{p} = ln ln x + M + O (1/ ln x)$ , where $M$ is the Meissel–Mertens constant.
$p \leq x \prod (1 - \frac{1}{p}) \sim \frac{e ^{- γ}}{ln x}$ , where $γ$ is the Euler–Mascheroni constant.

Remark 9.

The first theorem shows that the sum of the reciprocals of the primes diverges at the rate

ln ln x

. This can be viewed as a quantitative refinement of Euclid's theorem on the infinitude of primes.

5 Dirichlet's Theorem on Arithmetic Progressions

Theorem 10 (Dirichlet's theorem on primes in arithmetic progressions).

g cd (a, n) = 1

, then the arithmetic progression

a, a + n, a + 2 n, \dots

contains infinitely many primes.

Remark 11.

The proof requires the analytic properties of Dirichlet

L

-functions

L (s, χ) = \sum_{n = 1}^{\infty} χ (n) n^{- s}

, where

χ

is a Dirichlet character. The key step is establishing

L (1, χ) \neq = 0

for every non-principal character

χ

. A more precise result states

π (x; n, a) \sim x / (φ (n) ln x)

, showing that primes are equidistributed among the reduced residue classes.

6 Open Problems

Remark 12.

Several major open problems concern the distribution of primes:

Twin prime conjecture: Are there infinitely many primes $p$ such that $p + 2$ is also prime? Zhang (2013) proved that $p_{n + 1} - p_{n} < 7 \times 1 0^{7}$ for infinitely many $n$ , and this bound has been improved to $246$ by Maynard–Tao.
Riemann hypothesis: If $ζ (s) = 0$ and $0 < Re (s) < 1$ , then $Re (s) = 1/2$ . If true, this would imply $π (x) = Li (x) + O (x ln x)$ .
Goldbach's conjecture: Can every even integer greater than $2$ be written as the sum of two primes?

Number Theory Algebra Textbook Prime Number Theorem Distribution of Primes

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·105 articles

The Distribution of Primes — The Road to the Prime Number Theorem

1 The Prime-Counting Function

2 Chebyshev's Estimates

3 The Prime Number Theorem

4 Mertens' Theorems

5 Dirichlet's Theorem on Arithmetic Progressions

6 Open Problems

Share your expertise with the world

More from Folio Official

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry