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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

1
Maybe your (second) question has already been answered at mathoverflow.net/questions/43820/… – Gerry Myerson Jan 14 2011 at 11:14

2
So far as I know, the bit about finding a prime between $p$ and $p^2$ is a good example of what you're asking for: off the top of my head, I don't know a shorter proof than the one which establishes Bertrand's Postulate (i.e., an elementary but somewhat tricky couple of pages), which is a much stronger result. But I think your question "[A]re there any results that their first proof was large comparing to some proof that someone found later?" is far too broad for this site. (Certainly the answer is yes: a large percentage of first proofs are longer than what is eventually found.) – Pete L. Clark Jan 14 2011 at 11:22

3
There is no considerable advantage of enlarging the interval: this only simplifies the starting verification. I vote to close as see no mathematical question. If the question is nevertheless of interest, community wiki mode sounds more appropriate. – Wadim Zudilin Jan 14 2011 at 12:07

1
Asterios, could you make the title more precise? "Shortest proof" of what? – arsmath Jan 14 2011 at 14:05

4
-1. The answer to 2. is "yes, lots" and the answer to 3. is "yes, you can generate them more or less randomly and you will not derive any insights from the answers. E.g. Every holomorphic function $f:\mathbb{C}\rightarrow\mathbb{C}$ satisfying $f(5)\neq \pi$ is infinitely differentiable." I dare you to prove this statement without proving something stronger at the same time. – Alex Bartel Jan 14 2011 at 14:34
show 6 more comments

## 3 Answers

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)

-

@Dror, that exactly what I meant in my comment above: the only range to check by hand is $n<7$. I know this because that's one of the problems for my NT class, not the best one however... – Wadim Zudilin Jan 15 2011 at 9:35

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9482325315475464, "perplexity_flag": "middle"}