Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this question
Judging by 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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.