I was thinking about Paul Erdos's proof for Bertrand's Postulate and I wondered if the basic argument could be used to show that there are more than $n$ primes between $n$ and $n^2$.

Is this approach valid? Is there a better approach?

Here's the argument:

  1. Let $v_p(n)$ be the maximum power of $p$ that divides $n$.
  2. Using Legendre's Theorem, I calculate that $v_p\left(\dfrac{(n^2)!}{(n!)^n}\right) \le (n-1)n^2$.

    1. Let $n = qp^i + r$ where $0 \le r < p^i$
    2. For $r < \dfrac{p^i}{n}$, $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) = 0$
    3. For $r \ge \dfrac{p^i}{n}$, $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) \le n-1$
    4. For $p^i > n^2$, $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) = 0$
  3. Using the multinomial theorem I get: $\dfrac{n^{n^2}}{n^2+1} < \dfrac{(n^2)!}{(n!)^n}$.
    1. $n^{n^2}=(1 + 1 + \cdots + 1)^{n^2} = \sum\limits_{k_1+k_2+\cdots+k_n=n^2} {n^2 \choose k_1, k_2, \ldots, k_n} \prod\limits_{1\le t\le n^2}x_{t}^{k_{t}}\,,$ where ${n^2 \choose k_1, k_2, \ldots, k_n} = \frac{(n^2)!}{k_1!\, k_2! \cdots k_n!}$
    2. $n^{n^2} < (n^2+1)\left(\dfrac{(n^2)!}{(n!)^n}\right)$
    3. $\dfrac{n^{n^2}}{n^2+1} < \dfrac{(n^2)!}{(n!)^n}$
  4. $\dfrac{(n^2)!}{(n!)^n} < [(n-1)(n^2)]^n\prod\limits_{n < p \le n^2} n$
  5. $\dfrac{n^{n^2}}{n^2+1} < [(n-1)(n^2)]^n\prod\limits_{n < p \le n^2} n$
  6. For $n \ge 1, \dfrac{n^{n^2}}{n^{4n}} < \dfrac{n^{n^2}}{(n^2+1)[(n-1)(n^2)]^n} < \prod\limits_{n < p \le n^2} p$
  7. For $n \ge 6$, $n^2 - 4n = n(n-2) \ge 2n$
  8. $(2\log n)(\pi(n^2) - \pi(n)) > \sum\limits_{n < p \le n^2} \log p > (n^2-4n)\log n > (2n)\log n$
  9. So $\pi(n^2) - \pi(n) > n$.



Edit: I believe that step 4 is not correct. If I can save the argument, I will update it. Otherwise, please check out the link in the answer.

  • 2
    $\begingroup$ Isn't this maybe also a consequence of known error bounds for $\pi(x)\sim x/log (x)?$ $\endgroup$ – daniel Feb 9 '15 at 17:14
  • $\begingroup$ I really don't know. I'm very interested. Could you add a link that would help me get up to speed on the topic? $\endgroup$ – Larry Freeman Feb 9 '15 at 17:19

We have the following result1:

(Chebyshev, 1850) For any $X>30$, we have: $$\pi(X)\cdot\frac{\log X}{X} \in (A,B),$$ where $A=\log\left(\frac{2^{\frac{1}{2}}3^{\frac{1}{3}}4^{\frac{1}{4}}}{30^{\frac{1}{30}}}\right)\approx 0.946$ and $B=\frac{6}{5}A\approx 1.135$.

It follows that for any $X>30$ we have: $$ \pi(X^2)-\pi(X)\geq A\frac{X^2}{2\log X}-B\frac{X}{\log X}\geq\left(\frac{A}{2}-\frac{B}{30}\right)\frac{X^2}{\log X}\geq\color{red}{\frac{2}{5}\frac{X^2}{\log X}} $$ that is way greater than $X$. So we just need to check that the our claim holds in the range $[6,30]$.

1) it is a weaker version of the PNT, but not so weaker. Its proof only relies on the properties of the central binomial coefficients, and it is rather short and ingenious.

  • $\begingroup$ Thanks very much. Do you know if the Chebyshev (1850) paper is available in English and online? $\endgroup$ – Larry Freeman Feb 9 '15 at 18:11
  • 1
    $\begingroup$ @LarryFreeman: a proof with slightly worse constants can be found here (www.fen.bilkent.edu.tr/~franz/nt/cheb.pdf) or in the Erdos book Proofs from the Book. $\endgroup$ – Jack D'Aurizio Feb 9 '15 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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