I was raised largely on areas of math that often have nice, compelling proofs and/or explanations behind phenomena. Someone explains the Pythagorean Theorem to you, shows you five different intuitive ways to see why it is the way it is, and it just fits.
Here's the problem. In much of number theory, I get that familiar feeling that something inexorable, powerful, and logical is operating behind the scenes, if I could just pin it down (maybe the GRH?). But as hundreds of years of mathematicians know, many of these problems that feel so accessible are nothing of the kind, despite many existing number theory conjectures being "obviously" true.
I'll steer toward a question with some specificity. After toiling away for a couple years on the really hard classic conjectures, I've basically admitted to myself I don't have anything close to the math for it. I tried to choose a more reasonable goal: finding an alternative proof of Bertrand's Postulate, or failing that, a standalone proof of a prime in $(n,n^2)$. I've made what feels like progress, but haven't succeeded in either task yet.
To my knowledge, the cleanest (at least, the most accessible) proof out there for Bertrand is Erdos's treatment that comes up on Wikipedia. I see why it works if I work through it, but I don't find it satisfying (which could be personal preference or an insufficient background for appreciation on my part).
So, the question: In your opinion, is there likely to exist a "better" proof for Bertrand's postulate waiting out there in the ether? By "better," I suppose I mostly mean "even simpler". My working opinion had been that his approach was a systematic attack that succeeds, but feels like more firepower than should be necessary for a property that seems absolutely essential to the proper functioning of the primes. (This goes double for the question of a prime in $(n,n^2)$.)
I mean, why are there seemingly no straightforward proofs along these lines? No primes in $(n,n^2)$ sure looks like it should immediately cause an immeasurable number of ripe contradictions, and while it probably does at some level, the whole system doesn't implode the way I'm used to in a contradiction proof.
So I must admit it's very possible that Erdos's approach, while maybe not the absolute perfect proof possible, is essentially about as simple as one can expect it to get$-$that there is no deeper, obvious truth to be revealed with something like the beauty and compelling nature of Euclid's original proof of infinitude of primes, if not its simplicity.
In the opinion of someone more knowledgeable than I, is Erdos's proof likely to be a fair approximation of a minimal description of the underlying relevant machinery of primes that guarantees a prime in $(n,2n)$? It seems like I may have to finally accept that a bunch of number theoretic problems have trivial descriptions but a high degree of irreducible complexity, so I am wondering where on that spectrum Bertrand's postulate would fall. Sorry for the very soft question, but I've been mulling on this for a while now and could use some outside opinions.
Best Answer
Let $P(m)$ denote the product of all the primes less than or equal to $m$. Then the proof of Bertrand’s Postulate is based upon an elementary analysis of the prime power divisors of $\begin{pmatrix}2m\\m\\\end{pmatrix}$.
Let $r$ be the highest power of the prime $p$ which divides $\begin{pmatrix}2m\\m\\\end{pmatrix}$. Then $$r=\sum_{i\ge1}\left(\left\lfloor\frac{2m}{p^i}\right\rfloor-2\left\lfloor\frac{m}{p^i}\right\rfloor\right).$$ Each term in this sum is $0$ or $1$ and so $p^r\le2m$.
Primes $p\le\sqrt {2m}$
There are fewer than $\sqrt {2m}$ of these primes and so the product of the associated prime powers is at most $(2m)^ \sqrt {2m}\le 2^ {2m/3}$, for sufficiently large $m$.
Primes $p>\sqrt {2m}$
These occur to power $1$ (and only to power $1$) if $$\left\lfloor\frac{2m}{p}\right\rfloor-2\left\lfloor\frac{m}{p}\right\rfloor=1$$
Then $ \lfloor\frac{2m}{p}\rfloor$ is an odd integer, $2k+1$ say, and so $$2k+1\le\frac{2m}{p}<2k+2 \text { and so } \frac{m}{k+1}<p\le\frac{2m}{2k+1}.$$ Since $P(a)\le P(b)$ if $a\le b$, the product of all these primes is therefore $$\frac{P(2m)P(2m/3)P(2m/5) P(2m/7)…}{P(m)P(m/2)P(m/3)P(m/4)…}\le \frac{P(2m)P(2m/3)P(2m/7) }{P(m) P(m/3) }.$$
All that is now required are some inequalities for binomial coefficients.
$\begin{pmatrix}2m\\m\\\end{pmatrix}$ is the largest term of $(1+1)^{2m}$ and so $$\begin{pmatrix}2m\\m\\\end{pmatrix}\ge \frac{2^{2m}}{2m+1}.$$ For any positive integer $k$, $\begin{pmatrix}2k+1\\k+1\\\end{pmatrix}$ is one of the two equally largest terms of $(1+1)^{2k+1}$ and so $$\frac{P(2k+1)}{P(k+1)}\le\begin{pmatrix}2k+1\\k+1\\\end{pmatrix}\le 2^{2k}.$$ Then, by induction, $P(m)\le2^{2m}$ for any positive integer $m$.
Let $ \lfloor\frac{m}{3}\rfloor=k$, then for sufficiently large $m$, $$\frac{P(2m/3)}{P(m/3)}\le\frac{P(2k+1)}{P(k)}\le (k+1)2^{2k}<2^{0.7m}.$$
Using these inequalities in the result of the Lemma gives $$\frac{P(2m)}{P(m)}\ge\frac{2^{(2-0.7-4/7-2/3)m}}{2m+1}>\frac{2^{0.06m}}{2m+1}>1 \text { for sufficiently large }m$$.