# Early history of lower bounds on the prime counting function

Let $\pi (x)$ be the number of prime numbers less than or equal to $x$.

Euclid's proof of the infinitude of primes gives a horrible lower bound of the type $\pi (x)>> \sqrt{\log{x}}$. Somewhat surprisingly, Euler's proof of the divergence of the sum of reciprocals of primes only gives $\pi (x)>> \log{x}$ (see problem 8 of http://www.math.uiuc.edu/~hildebr/531.fall05/hw3.pdf).

Was anybody able to get a lower bound better than $\log{x}$ before Chebyshev got the order of magnitude right in ~ 1850?

-
Judging by mathworld.wolfram.com/PrimeCountingFunction.html I suspect Gauss knew this pre-1850. –  Benjamin Dickman Nov 10 '12 at 7:52
Yes, Gauss knew and I find it very likely that he was able to prove a better bound than Euler's. But one can still ask whether someone did before Gauss, or whether someone published a proof before Chebyshev. (Gauss almost doesn't count - so much of his thinking he didn't communicate.) –  Jonah Sinick Nov 10 '12 at 7:57
@Jonah, I agree, while I also believe that Gauss knew it, one might question how he knew it. The MathWorld article says only that he postulated it. –  Dan Brumleve Nov 10 '12 at 8:07
I'm sorry I've made an incorrect statement, I could not edit it so I have removed it. –  Esteban Crespi Nov 10 '12 at 10:40

Incredibly, Gauss in 1793 conjectured $\pi_k(x)\sim \frac{x (\log\log x)^{k-1}}{(k-1)!\log x }.$ Gauss, Werke vol. 10 (Gottengen (1917),11.* In his Handbuch Landau discusses Gauss in one of the earlier sections. If I have the German right he ascribes to Gauss that there is a function A(x) with

$\pi(x) \sim \frac{x}{\log x - A(x)}$ and the conjecture that $\lim_{x \to \infty} A(x) = 1.$

Landau adds, "Aber beweisen hat Gauss nichts..." So it was maybe conjecture based on extensive calculation.

Gauss does count, as I doubt he would have speculated at all if there were already a proof extant. Given his prominence, I expect he would have been aware of one.

Landau also quotes Legendre in 1808 to the effect that "with a very satisfying precision" $\pi(x) \sim \frac{x}{\log x - 1.08366}.$

The OP asks about lower bounds and I think Landau gives a pretty complete review of the situation as it existed prior to 1850. Apart from what is mentioned in the OP I don't find anything. Doesn't mean it's not there...

Edit: Chebyshev did give a proof (possibly conditional) that $$\lim \sup_{x\to \infty} \pi(x) \geq \frac{x}{\log x}.$$ This is also from Landau and I am fairly confident that there is nothing much earlier.

*This assertion is from the first page of E.M. Wright, (1954), A Simple Proof of a Theorem of Landau, Proc. of the Edinburgh Math. Soc., 9, pp. 87-90.

-
Thanks Daniel! I didn't know about the $\pi_{k}$ conjecture of Gauss. But is it really incredible? Doesn't it follow heuristically once you assume the prime number theorem? Also, I don't see the relevance of your answer to my original question - I was asking who had a proof, not who made the correct guess. –  Jonah Sinick Nov 10 '12 at 19:39
Yes, the PNT falls out as a special case, k = 1. I do find it amazing in historical context. And yes for sure you asked for a proof, I'm just not sure there is one during that time-frame. If you un-accept, you still might get a positive answer to that question. –  daniel Nov 10 '12 at 23:48
Ok, unaccepted :) –  Jonah Sinick Nov 12 '12 at 2:36
I too would be interested if there's a proof earlier than Chebyshev. :) –  daniel Nov 12 '12 at 12:58