It's well-known that Hadamard and de la Vallée-Poussin independently proved the Prime Number Theorem in 1896: that $\pi(n)=n/\log n+o(n/\log n)$. I'm curious as to a weaker result: that for any $\varepsilon>0$, $\pi(n)\gg n^{1-\varepsilon}$.
Chebyshev famously proved that if $\lim \pi(n)\log n$ exists it must be equal to 1, but I seem to remember that he also proved bounds on that value, pushing the date back to 1850 or so in that case. But were there earlier results in this direction?
In the 1850's, Chebyshev gave the following explicit bound, for sufficiently large n.
$$0.92129 \, \frac{n}{\log n} < \pi(n) < 1.0556 \, \frac{n}{\log n}.$$
This is mentioned in "An introduction to the theory of the Riemann zeta function" by S. J. Patterson. There is an exercise in the first chapter that gives the lower bound following Chebyshev's method (that is, using Stirling's formula and the series $\log \ n! = \Sigma_{p^k\leq n} \lfloor n/p^k \rfloor\log p$). S. J. Patterson cites Chebyshev as the first to obtain significant results toward the prime number theorem.
Didn't Euler prove that $\sum 1/p$ diverges? This proves that $\pi(N)$ is infinitely often larger than $N^{1-\epsilon}$: If there were only $N^{1-\epsilon}$ primes less than $N$, then there are at most $2^{k (1-\epsilon)}$ primes between $2^{k-1}$ and $2^k$. So we can bound $\sum 1/p$ above by $\sum 2^{k(1-\epsilon)}/2^{k-1} = 2 \sum 2^{-k \epsilon}$, which converges.
UPDATE: I should clarify that I see no way to get from here to the stronger statement that $\pi(N)$ is greater than $N^{1 - \epsilon}$ for all sufficiently large $N$.
The following is an MO-adopted extract from my lectures.
Euclid's theorem about the infiniteness of primes can be written as $$ \pi(x)\to+\infty \qquad\text{as}\quad x\to+\infty. $$ However, this theorem tells us nothing about how fast the function $\pi(x)$ increases with $x$. In 1808 Legendre published a discovered empirical formula, namely, $$ \pi(x)\approx\frac x{\ln x-1.08366}; $$ some years later Gauss noted that $x/(\ln x-1)$ and even $$ \int_2^x\frac{dt}{\ln t} $$ is a much better approximation to $\pi(x)$ for larger $x$. In 1850 Chebyshev published his work containing the following result.
Theorem (Chebyshev). There exist two constants $A$ and $B$, $0< A< 1< B$, such that for all $x\ge2$ the following bounds are valid: $$ \frac{Ax}{\ln x}< \pi(x)< \frac{Bx}{\ln x}. \qquad(1) $$
Chebyshev actually proved the theorem by showing that one can take $A=0.921$ and $B=1.106$ for $x\ge x_0$, so that $A$ and $B$ are very close to $1$. In our simplified proof we will get more modest estimates for $A$ and $B$. Note however that for the proof of the prime number theorem one needs the existence result for these constants. Chebyshev's theorem states the correct order of growth of the function $\pi(x)$ as $x\to+\infty$.
We need some properties of the function $$ T(x)=\sum_p\ln p\biggl(\biggl[\frac xp\biggr] +\biggl[\frac x{p^2}\biggr] +\biggl[\frac x{p^3}\biggr]+\dots\biggr), $$ where $[\cdot]$ denotes the integer part of a real number.
Lemma 1. For positive integers $n$ we have the equality $T(n)=\ln n!$.
Proof. Factorise $n!$ into product of primes, $n!=\prod_pp^{\nu_p}$, and use the formula $$ \operatorname{ord}_p n!=\biggl[\frac np\biggr] +\biggl[\frac n{p^2}\biggr] +\biggl[\frac n{p^3}\biggr]+\dots $$ (the sum is in fact finite!) to see that $$ \nu_p=\biggl[\frac np\biggr] +\biggl[\frac n{p^2}\biggr] +\biggl[\frac n{p^3}\biggr]+\dots \qquad\text{for each prime $p$}. $$ Taking the logarithm of the factorisation of $n!$ we deduce the required equality.
Lemma 2. The function $T(n)$ (of natural argument $n$) is nondecreasing.
Proof. It follows from Lemma 1 that $$ T(n+1)-T(n)=\ln(n+1)!-\ln n!=\ln(n+1)> 0. $$
Lemma 3. If $[x]=n$, then $T(x)=T(n)$.
Proof. Let $n=[x]$, $\alpha=\{x\}$ (the fractional part of $x$, hence $0< \alpha< 1$), and let $m$ be a power of prime $p$. If $[n/m]=q$, then $n=mq+r$ where $0\le r\le m-1$. Therefore, $x=n+\alpha=mq+(r+\alpha)$ where $0\le r+\alpha< m$; consequently, $$ \biggl[\frac xm\biggr] =\biggl[q+\frac{r+\alpha}m\biggr] =q+\biggl[\frac{r+\alpha}m\biggr] =q=\biggl[\frac nm\biggr]. $$ From this inequality and from the definition of $T(x)$ the required property follows immediately.
We will also need the following elementary inequality: for $n\ge3$, $$ (n+1)^3\le2^{2n}. $$
Lemma 4. For $x\ge6$ the following estimates take place: $$ \frac{\ln2}2\cdot x< T(x)-2T\biggl(\frac x2\biggr) < \frac{4\ln2}3\cdot x. $$
Proof. Denote $n=[x/2]\ge3$, so that $2n\le x< 2n+2$. Then by Lemma 3, $$ T(x)-2T\biggl(\frac x2\biggr) =T(2n)-2T(n) \quad \text{if $2n\le x< 2n+1$}, \qquad\text{and}\qquad =T(2n+1)-2T(n) \quad \text{if $2n+1\le x< 2n+2$}, $$ hence with the help of Lemma 2 we obtain $$ T(2n)-2T(n) \le T(x)-2T\biggl(\frac x2\biggr) \le T(2n+1)-2T(n). \qquad(2) $$
By Lemma 1 for $n\ge3$ we find that $$ T(2n)-2T(n) =\sum_{k=1}^{2n}\ln k-2\sum_{k=1}^n\ln k =\sum_{k=n+1}^{2n}\ln k-\sum_{k=1}^n\ln k $$ $$ =\ln\frac{n+1}{1}+\ln\frac{n+2}{2}+\dots+\ln\frac{n+n}{n} \ge(n+1)\ln2 \gt \frac{x}{2}\ln 2, \qquad (3) $$ so that $$ \ln\frac{n+1}1\ge\ln4=2\ln2, \qquad \ln\frac{n+k}k=\ln\biggl(1+\frac nk\biggr)\ge\ln2 \quad\text{for } k=2,3,\dots,n, $$ and $x/2< n+1$.
On the other hand, for $n\ge3$, $$ \frac{(2n+1)!}{n!^2} =(n+1)\cdot\frac{(2n+1)!}{n!(n+1)!} =\frac{n+1}2\cdot\biggl(\binom{2n+1}n+\binom{2n+1}{n+1}\biggr) $$ $$ < \frac{n+1}2\sum_{k=0}^{2n+1}\binom{2n}k =\frac{n+1}2\cdot(1+1)^{2n+1}=2^{2n}(n+1) $$ $$ \le2^{2n+2n/3}=2^{8n/3} $$ (on the last step we use the above elementary inequality). Thus, by Lemma 1 $$ T(2n+1)-2T(n)=\ln\frac{(2n+1)!}{n!^2} < \frac{8n}3\ln2\le\frac{4x}3\ln2. \qquad(4) $$ Substituting the inequalities (3) and (4) into (2), we arrive at the desired claim.
Lemma 5. For a real number $\alpha$, the difference $[2\alpha]-2[\alpha]$ is either $0$ or $1$.
The proof of the lemma is straightforward.
Proof of Chebyshev's theorem. Lower bound. Using the definition of $T(x)$ we obtain $$ T(x)-2T\biggl(\frac x2\biggr) =\sum_{p\le x}\ln p\biggl( \biggl(\biggl[\frac xp\biggr]-2\biggl[\frac x{2p}\biggr]\biggr) +\biggl(\biggl[\frac x{p^2}\biggr]-2\biggl[\frac x{2p^2}\biggr]\biggr) +\dots\biggr), \qquad(5) $$ since all the terms on the right-hand side vanish for $p> x$. The groups $$ \biggl(\biggl[\frac x{p^k}\biggr]-2\biggl[\frac x{2p^k}\biggr]\biggr) $$ also vanish for $p^k> x$, whence the coefficient of $\ln p$ on the right-hand side of (5) can be written as $$ \sum_{k=1}^s \biggl(\biggl[\frac x{p^k}\biggr]-2\biggl[\frac x{2p^k}\biggr]\biggr), $$ for $p^s\le x$, that is, for $s\le\dfrac{\ln x}{\ln p}$. By Lemma 5 each term in parenthesis on the right-hand side of (5) is at most $1$, and the number of such terms is at most $s$, hence $$ T(x)-2T\biggl(\frac x2\biggr) \le\sum_{p\le x}\ln p\cdot\frac{\ln x}{\ln p} =\ln x\cdot\sum_{p\le x}1 =\pi(x)\ln x. $$ Consequently, by Lemma 4 $$ \pi(x)\ln x> \frac{\ln2}2x, $$ and the desired lower estimate is deduced with $A=\frac12\ln2$.
Upper bound. Since all the terms on the right-hand side of (5) are non-negative, leaving those for which $p> x/2$ does not increase the whole sum. For $x/2< p\le x$ we have $$ \biggl(\biggl[\frac xp\biggr]-2\biggl[\frac x{2p}\biggr]\biggr) +\biggl(\biggl[\frac x{p^2}\biggr]-2\biggl[\frac x{2p^2}\biggr]\biggr) +\dots =1, \qquad(6) $$ because for such $p$ and $x\ge6$ there holds $2p> x$ and $p^2> x^2/4> x$, that is, the left-hand side of (6) involves a unique nonzero term, $[x/p]$. Thus, from (5) we obtain $$ T(x)-2T\biggl(\frac x2\biggr) \ge\sum_{x/2< p\le x}\ln p \gt \ln\frac x2\cdot\sum_{x/2< p\le x}1 =\biggl(\pi(x)-\pi\biggl(\frac x2\biggr)\biggr)\ln\frac x2 $$ $$ =\pi(x)\ln x-\pi\biggl(\frac x2\biggr)\ln\frac x2-\pi(x)\ln2 $$ $$ \ge\pi(x)\ln x-\pi\biggl(\frac x2\biggr)\ln\frac x2-x\ln2 $$ (where we applied the trivial bound $\pi(x)\le x$), whence $$ \pi(x)\ln x-\pi\biggl(\frac x2\biggr)\ln\frac x2< T(x) -2T\biggl(\frac x2\biggr)+x\ln2< \biggl(\frac{4\ln2}3+\ln2\biggr)x< 2x \qquad(7) $$ for $x\ge6$. For any $x> 0$ there exists a positive integer $s$ such that $x/2^s< 2$, so that $\pi(x/2^s)=0$. Successively applying the inequalities (7) we find that $$ \pi(x)\ln x < 2x+\pi\biggl(\frac x2\biggr)\ln\frac x2 < 2x+2\cdot\frac x2+\pi\biggl(\frac x4\biggr)\ln\frac x4 < \dots $$ $$ < 2x+2\cdot\frac x2+\dots+2\cdot\frac x{2^{s-1}} +\pi\biggl(\frac x{2^s}\biggr)\ln\frac x{2^s} $$ $$ < 2x\biggl(1+\frac12+\frac14+\dots\biggr) =4x, $$ which gives us the required estimate with $B=4$.
Remarks. In order to get $A$ and $B$ closer to $1$, Chebyshev considered the expression $$ T(x)-T\biggl(\frac x2\biggr) -T\biggl(\frac x3\biggr) -T\biggl(\frac x5\biggr) +T\biggl(\frac x{30}\biggr) $$ instead of $T(x)-2T(x/2)$; in addition, he first deduced estimates for the functions $$ \vartheta(x)=\sum_{p\le x}\ln p \qquad\text{and}\qquad \psi(x)=\sum_{p\le x}\biggl[\frac{\ln x}{\ln p}\biggr]\ln p, $$ and then translated them for $\pi(x)$. The functions $\vartheta(x)$ and $\psi(x)$ are now known as Chebyshev's functions.
From MathWorld's article on the PNT:
In 1792, when only 15 years old, Gauss proposed that $\pi(n) \sim n/\log n$.
Gauss later refined his estimate to $\pi(n) \sim \mbox{Li}(n)$ where
$\mbox{Li}(n) := \int_2^n \frac{1}{\log x} \, dx$
is the logarithmic integral. Gauss did not publish this result, which he first mentioned in an 1849 letter to Encke. It was subsequently posthumously published in 1863.
