What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-18T16:22:05Z http://mathoverflow.net/feeds/question/52060 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52060/what-is-the-shortest-proof-of-the-existence-of-a-prime-between-p-and-p2-ot What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? asterios gantzounis 2011-01-14T11:05:30Z 2011-01-14T17:33:18Z <p>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)? </p> <p>(One can say that we can have it as a collorary of Bertrand's postulate, but it is a stronger result.) </p> <p>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?</p> <p>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.) </p> <p>NOTE:I was asked to change the title to a more precise</p> http://mathoverflow.net/questions/52060/what-is-the-shortest-proof-of-the-existence-of-a-prime-between-p-and-p2-ot/52085#52085 Answer by Dror Speiser for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? Dror Speiser 2011-01-14T16:37:36Z 2011-01-14T16:37:36Z <p>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 <a href="http://en.wikipedia.org/wiki/Proof_of_Bertrand%27s_postulate" rel="nofollow">Wikipedia's "Proof of Bertrand's postulate"</a>:</p> <p>Lemma 1: $$\frac{4^{\lfloor n^2/2 \rfloor}}{2\lfloor n^2/2 \rfloor+1} &lt; \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}$.</p> <p>Lemma 2: $$p^{R(p,n)} \le n+1$$</p> <p>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)} &lt; (n^2+1)^n$$</p> <p>This violates lemma 1 as soon as $n \ge 7$.</p> <p>(* the floors where put in a bit hastily)</p> http://mathoverflow.net/questions/52060/what-is-the-shortest-proof-of-the-existence-of-a-prime-between-p-and-p2-ot/52095#52095 Answer by Pietro Majer for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? Pietro Majer 2011-01-14T17:32:31Z 2011-01-14T17:32:31Z <p>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.</p> http://mathoverflow.net/questions/52060/what-is-the-shortest-proof-of-the-existence-of-a-prime-between-p-and-p2-ot/52096#52096 Answer by Pietro Majer for What is the shortest proof of the existence of a prime between $p$ and $p^2$ ? other examples? Pietro Majer 2011-01-14T17:33:18Z 2011-01-14T17:33:18Z <p>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.</p>