x = 1. log(x)
This theorem was conjectured independently by Legendre and Gauss. The approximation x π(x) = A log(x) + B was formulated by Legendre in 1798 [Le1] and made more precise in [Le2] where he provided the values A = 1, B = −1.08366. On August 4, 1823 (see [La1], page 6) Abel, in a letter to Holmboe, characterizesthe prime number theorem (referring to Legendre) as perhaps the most remarkable theorem in all mathematics. Gauss, in his well known letter to the astronomer Encke, (see [La1], page 37) written on Christmas eve 1849 remarks that his attention to the problem of ﬁnding an asymptotic formula for π(x) dates back to 1792 or 1793 (when he was ﬁfteen or sixteen), and at that time noticed that the densityof primes in a chiliad (i.e. [x, x + 1000]) decreased approximately as 1/ log(x) leading to the approximation
π(x) ≈ Li(x) =
dt . log(t)
The remarkable part is the continuation of this letter, in which he said (referring to x Legendre’s log(x)−A(x) approximation and Legendre’s value A(x) = 1.08366) that whether the quantity A(x) tends to 1 or to a limit close to 1, he does not dareconjecture. The ﬁrst paper in which something was proved at all regarding the asymptotic distribution of primes was Tchebychef’s ﬁrst memoir ([Tch1]) which was read before the Imperial Academy of St. Petersburg in 1848. In that paper Tchebychef proved that if any approximation to π(x) held to order x/ log(x)N (with some ﬁxed large positive integer N ) then that approximation had to be Li(x). Itfollowed from this that Legendre’s conjecture that lim A(x) = 1.08366 was false, and that if the limit existed it had to be 1.
x The ﬁrst person to show that π(x) has the order of magnitude log(x) was Tchebychef in 1852 [Tch2]. His argument was entirely elementary and made use of properties of factorials. It is easy to see that the highest power of a prime p which divides x! (we assume x is aninteger) is simply x→∞
x x x + 2 + 3 + ··· p p p 1
where [t] denotes the greatest integer less than or equal to t. It immediately follows that x! =
and log(x!) =
x x x + 2 + 3 + ··· p p p
Now log(x!) is asymptotic to x log(x) by Stirling’s asymptotic formula, and, since squares, cubes, ... of primes are comparatively rare, and [x/p] isalmost the same as x/p, one may easily infer that log(p) x = x log(x) + O(x) p
from which one can deduce that π(x) is of order Tchebychef, who actually proved that [Tch2] B < π(x) for all suﬃciently large numbers x, where B= and
x log(x) .
This was essentially the method of
x 6B < log(x) 5
log 2 log 3 log 5 log 30 + + − ≈ 0.92129 2 3 5 30
6B ≈ 1.10555. 5 Unfortunately,however, he was unable to prove the prime number theorem itself this way, and the question remained as to whether an elementary proof of the prime number theorem could be found. Over the years there were various improvements on Tchebychef’s bound, and in 1892 Sylvester [Syl1], [Syl2] was able to show that 0.956 < π(x) x < 1.045 log(x)
for all suﬃciently large x. We quote from Harold Diamond’sexcellent survey article [D]: The approach of Sylvester was ad hoc and computationally complex; it oﬀered no hope of leading to a proof of the P.N.T. Indeed, Sylvester concluded in his article with the lament that “...we shall probably have to wait [for a proof of the P.N.T. ] until someone is born into the world so far surpassing Tchebychef in insight and penetration as Tchebychef has proved himself...