# Who first proved that there are at least n^(1-ε) primes up to n?

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?

-
So far as I know, the first to prove a result which implies $\pi(n) \gg n^{1-\epsilon}$ was indeed Chebyshev. – Pete L. Clark May 28 '10 at 15:37
I think that Chebyshev was the first to prove Bertand's postulate, which gives you an idea of how little about the behavior of $\pi(n)$ had been rigorously established before. – Victor Protsak May 28 '10 at 22:32
Chebyshev said, And I say it again, There's always a prime Between $n$ and $2n$. (Nathan Fine's comment on Erdos' proof of Bertrand's Postulate) – Gerry Myerson May 28 '10 at 23:12
@Gerry: This is off-topic but I can't resist: "The question both deep and profound\\ Is whether the circle is round\\ In a paper of Erdős\\ Written in Kurdish\\ A counterexample was found!" – Victor Protsak May 29 '10 at 1:27

In the 1850's, Chebychev gave the following explicit bound, for sufficient large x.

$0.92129\ {n\over log n} < \pi(n) < 1.0556\ {n\over log n}$

This is mentioned in the book of S. J. Patterson "the theory of the Riemann Zeta function". There is an exercice in the first chapter that gives the lower bound following Chebychev method (that is, using Stirling formula and the series $log \ n! = \Sigma_{p^k\leq n} \ [n/p^k]\log p$). S. J. Patterson cites Chebychev as the first to obtain significant results toward the prime number theorem.

-
Yes, that's the result I alluded to in the post -- thanks for the specifics. (+1.) But was this the first? I was wondering if, for example, it was known that $\pi(n)>n/\log^3 n$ for sufficiently large n. – Charles May 28 '10 at 19:16

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$.

-
Agreed on both counts, FWIW. – Pete L. Clark May 28 '10 at 18:09
+1. Good point; now I need to think about whether this is enough for what I need... – Charles May 28 '10 at 19:12
Euler showed $\sum_p 1/p$ is asymptotic to $\log\log X$, which is more. en.wikipedia.org/wiki/… – Junkie Aug 22 '11 at 8:43

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.

-

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{dx}{\log x}$

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.

-
Two things: (i) the two "estimates" are equivalent, since $\operatorname{Li}(n) \sim \pi(n)$. The logarithmic integral was preferred by Gauss because the error term is smaller. (ii) These assertions were not proven until 1896, by Hadamard and de la Vallee Poussin (independently). – Pete L. Clark May 28 '10 at 15:35
@Pete: They are equivalent in the multiplicative sense, but $\pi(n)-Li(n)$ is asymptotically much smaller than $\pi(n)-n/\log(n),$ see en.wikipedia.org/wiki/…. – Victor Protsak May 28 '10 at 22:12
@Victor: yes, that's what I said in my comment: it doesn't make sense to "refine" $f(n) \sim g(n)$ to $f(n) \sim h(n)$, since the second statement contains no more information than the first. It is a matter of getting error bounds on $|f(n)-g(n)|$ versus $|f(n) - h(n)|$. – Pete L. Clark May 29 '10 at 5:50
Pete: Right so. Sorry, somehow, I overlooked the second sentence of your point (i). – Victor Protsak May 30 '10 at 1:39