4
$\begingroup$

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?

  • 0
    Judging by http://mathworld.wolfram.com/PrimeCountingFunction.html I suspect Gauss knew this pre-1850.2012-11-10
  • 1
    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.)2012-11-10
  • 0
    @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.2012-11-10
  • 0
    I'm sorry I've made an incorrect statement, I could not edit it so I have removed it.2012-11-10

1 Answers 1

3

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.

  • 0
    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.2012-11-10
  • 0
    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.2012-11-10
  • 0
    Ok, unaccepted :)2012-11-12
  • 0
    I too would be interested if there's a proof earlier than Chebyshev. :)2012-11-12