You are currently browsing the category archive for the ‘Analytic Number Theory’ category.

In 1737, Euler presented a novel proof of the infinitude of the primes, in showing that the harmonic sum of the primes diverges.  Explicitly, Euler’s work furnishes the estimate

$\displaystyle\sum_{p \leq x} 1/p=\log \log x + O(1),$

in which the sum exhausts the rational primes at most $x$.  At this point, it becomes quite elementary to derive the two inequalities

$\displaystyle\limsup_{n \to \infty} \frac{p_n}{n \log n} \geq 1 \quad \text{and} \quad \liminf_{n \to \infty} \frac{p_n}{n \log n} \leq 1.$

Results of this flavor remained essentially unimproved for over a century, until Chebyshev presented the following landmark theorem in 1852:

Theorem (Chebyshev): There exist positive constants $c_1,c_2$ such that

$\displaystyle c_1 \leq \liminf_{x \to \infty} \frac{\pi(x)\log x}{x} \leq \limsup_{x \to \infty} \frac{\pi(x) \log x}{x} \leq c_2.$

Thus Chebyshev’s Theorem shows that $x/\log x$ represents the growth rate (up to constants) of $\pi(x)$; stated equivalently in Bachmann-Landau notation, we have $\pi(x) \in \Theta(x/\log x)$.  Yet more is true: the constants$c_1,c_2>0$ in Chebyshev’s proof are therein made effective, and can be taken as

$c_1 =\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30} \approx 0.921292;$

$c_2 = \frac{6}{5}\left(\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30}\right)\approx1.10555.$

As a corollary to Chebyshev’s Theorem, we have $\pi(2n-3)>\pi(n)$ for$n \gg 0$.  By making this implicit bound on $n$ precise, Chebyshev was able to prove Bertrand’s Postulate (thereafter known as the Bertrand-Chebyshev Theorem).

In this post, we’ll prove a variant of Chebyshev’s Theorem in great generality, and discuss some historically competitive bounds on the constants $c_1$ and $c_2$ given above.  Lastly, we’ll discuss how Chebyshev’s Theorem relates to proposed “elementary” proofs of the PNT.