Chebyshev Bounds

Motivation

The prime counting function

\pi(x)

measures the number of primes not exceeding $x$ . Numerical evidence suggests that

\pi(x)\approx \frac{x}{\log x},

but proving such a statement is difficult.

Before the Prime Number Theorem was established, Pafnuty Chebyshev obtained strong upper and lower bounds showing that the order of growth of $\pi(x)$ is indeed approximately $x/\log x$ . These estimates were among the first major successes of analytic methods in prime number theory.

Chebyshev’s Theorem

Chebyshev proved that there exist positive constants $A$ and $B$ such that

A\frac{x}{\log x} \leq \pi(x) \leq B\frac{x}{\log x}

for all sufficiently large $x$ .

Thus the quotient

\frac{\pi(x)\log x}{x}

remains bounded above and below by positive constants.

Although this does not prove

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

it shows that the conjectured asymptotic order is correct.

Factorials and Prime Powers

Chebyshev’s argument studies the prime factorization of factorials. Recall that

n! = 1\cdot2\cdot3\cdots n.

Every prime $p\leq n$ contributes powers to the factorization of $n!$ . The exponent of $p$ in $n!$ is

\sum_{k\geq1}\left\lfloor\frac{n}{p^k}\right\rfloor.

Taking logarithms gives

\log(n!) = \sum_{p\leq n} \left( \sum_{k\geq1} \left\lfloor\frac{n}{p^k}\right\rfloor \right)\log p.

This identity links the growth of factorials with the distribution of primes.

Chebyshev Functions

Chebyshev introduced two important arithmetic functions.

The first is

\vartheta(x) = \sum_{p\leq x}\log p.

The second is

\psi(x) = \sum_{p^k\leq x}\log p.

Equivalently,

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

where $\Lambda(n)$ is the von Mangoldt function:

\Lambda(n)= \begin{cases} \log p,& n=p^k,\\ 0,& \text{otherwise}. \end{cases}

These weighted sums are often easier to analyze than $\pi(x)$ itself.

Relation to Prime Distribution

The functions $\vartheta(x)$ and $\psi(x)$ encode essentially the same asymptotic information as $\pi(x)$ .

Roughly,

\vartheta(x)\approx \pi(x)\log x.

If primes near $x$ occur with density $1/\log x$ , then summing $\log p$ over primes up to $x$ should produce a quantity of size $x$ .

Indeed, Chebyshev proved that

\vartheta(x)\asymp x

and

\psi(x)\asymp x,

meaning that each function is bounded above and below by constant multiples of $x$ .

From these estimates one derives

\pi(x)\asymp \frac{x}{\log x}.

Binomial Coefficients

A central step uses the central binomial coefficient

\binom{2n}{n} = \frac{(2n)!}{(n!)^2}.

Every prime $p$ with

n<p\leq 2n

appears in the numerator but not in the denominator. Hence

\prod_{n<p\leq2n} p \leq \binom{2n}{n}.

Using estimates for factorials gives information about how many primes lie in the interval $(n,2n]$ .

This idea leads to quantitative bounds for $\pi(x)$ .

Bertrand’s Postulate

One consequence of Chebyshev’s work is Bertrand’s postulate:

For every integer $n\geq2$ , there exists a prime $p$ satisfying

n<p<2n.

This theorem guarantees that primes never become too sparse.

Chebyshev gave the first proof. Later, Erdős discovered an elegant elementary argument using binomial coefficients.

Toward the Prime Number Theorem

Chebyshev also proved the following important statement:

If the limit

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

exists, then it must equal $1$ .

Thus once existence is established, the Prime Number Theorem follows automatically.

The remaining difficulty is proving convergence itself. This was achieved through complex analysis and the study of the zeta function.

Importance

Chebyshev bounds mark the transition from elementary prime theory to analytic number theory. They show that primes obey a strong global regularity long before exact asymptotics are known.

The functions

\vartheta(x) \quad\text{and}\quad \psi(x)

remain central throughout modern analytic number theory. In particular, the Prime Number Theorem is often written in the equivalent form

\psi(x)\sim x.

This formulation connects prime distribution directly with the analytic properties of the Riemann zeta function.