You are currently browsing the tag archive for the ‘Erdos’ tag.

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 constantsc_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) forn \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.

Read the rest of this entry »