What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? - MathOverflow [closed]

What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples?

2011-01-14T11:05:30Z

1) It is well known that between a prime $p$ and $p^2$ always exist a prime, but what is the shortest proof of that (by elementary methods or not)?

(One can say that we can have it as a collorary of Bertrand's postulate, but it is a stronger result.)

2) I ask it as an example, are there any characteristic examples of results that their first proof was really large comparing to some proof that someone found later?

3) Or of results that their only known proof/proofs is/are a collorary of the proof of something stronger? (Maybe the one that I give is not an example for this.)

NOTE:I was asked to change the title to a more precise

Answer by Dror Speiser for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples?

2011-01-14T16:37:36Z

It is possible to shorten Bertrand's Postulate's proof so it proves only the above. We can throw away the usually-proven upper bound on the primoral. Explicitly, following Wikipedia's "Proof of Bertrand's postulate":

Lemma 1: $$\frac{4^{\lfloor n^2/2 \rfloor}}{2\lfloor n^2/2 \rfloor+1} < \binom{n^2}{\lfloor n^2/2 \rfloor}$$ For a fixed prime $p$, define $R(p,n)$ to be the highest natural number $x$, such that $p^x$ divides $\binom{n}{\lfloor n/2 \rfloor}$.

Lemma 2: $$p^{R(p,n)} \le n+1$$

If there are no primes between $n$ and $n^2$, then: $$\binom{n^2}{\lfloor n^2/2 \rfloor } = \prod_{p\le n} p^{R(p,n^2)} < (n^2+1)^n$$

This violates lemma 1 as soon as $n \ge 7$.

(* the floors where put in a bit hastily)

Answer by Pietro Majer for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples?

2011-01-14T17:32:31Z

An instance of (2): the proof of the individual ergodic theorem by Garcia, using a "maximal ergodic lemma" is considerably shorter and simpler than the original one of Birkhoff.

Answer by Pietro Majer for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples?

2011-01-14T17:33:18Z

An instance of (2): the proof of the individual ergodic theorem by Garcia, using a "maximal ergodic lemma" is considerably shorter and simpler than the original one of Birkhoff.