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

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

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 such that*

Thus Chebyshev’s Theorem shows that represents the growth rate (up to constants) of ; stated equivalently in Bachmann-Landau notation, we have .* *Yet more is true: the constants in Chebyshev’s proof are therein made effective, and can be taken as

As a corollary to Chebyshev’s Theorem, we have for. By making this implicit bound on 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 and given above. Lastly, we’ll discuss how Chebyshev’s Theorem relates to proposed “elementary” proofs of the PNT.