# Talk:Proof of Bertrand's postulate

## Why can't the proof be strengthened?

I fail to see why assuming there is no prime p such that n < p < 2n-2 won't work. This allows the possibility of 2n-1 being prime which would make the right side ${\displaystyle (2n-1)(2n)^{\sqrt {2n}}(2n/3)\#}$ but still maintains the asymptotic behavior that will lead to a contradiction.

Likewise assuming that there is no prime p such that n < p < 2n-4 would allow 2n-1 and 2n-3 to be prime and give a right side bound of ${\displaystyle (2n-3)(2n-1)(2n)^{\sqrt {2n}}(2n/3)\#}$ still maintaining the asymptotic contradiction.

I must be missing something obvious here. —Preceding unsigned comment added by 71.112.88.200 (talk) 00:40, 24 September 2010 (UTC)

## Clarifying a couple of steps

I was following this fine up until this step:

When ${\displaystyle p>{\sqrt {2n}},}$ the number ${\displaystyle {2n \choose n}}$ has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, so the product of the pR(p,n) over all other primes is at most ${\displaystyle (2n)^{\sqrt {2n}}.}$

I fail to understand two things here.

First, I don't understand the first sentence: haven't we just shown in the preceding paragraph that when ${\displaystyle p>{\sqrt {2n}}}$ the number ${\displaystyle {2n \choose n}}$ is not divisible by p?

Second, I don't understand the derivation of the final expression. As I see it we are taking ${\displaystyle {2n \choose n}\leq \prod {(p^{R(p,n)}\leq p^{2n})}\leq {({\sqrt {2n}})\#}^{2n}\leq {(2n/3)\#}^{2n}}$. I cannot see where the expression ${\displaystyle (2n)^{\sqrt {2n}}}$ comes from.

Could someone clarify these points? Hv (talk) 11:47, 17 January 2008 (UTC)

Ad the first point: we haven't. Read the paragraph more carefully, we have only shown that for p > 2n/3.
Ad the second point: the product is split into two pieces, one for primes p ≤ √(2n) (for which we have the generic bound pR(p,n) ≤ 2n by lemma 2), and one for primes p > √(2n) (for which we have R(p,n) ≤ 1 by lemma 3). So:
${\displaystyle {\binom {2n}{n}}=\prod _{p\leq 2n/3}p^{R(p,n)}=\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\prod _{{\sqrt {2n}}
${\displaystyle \leq (2n)^{\sqrt {2n}}\prod _{{\sqrt {2n}}
using the fact that all prime divisors of ${\displaystyle \textstyle {\binom {2n}{n}}}$ are at most 2n/3, as we know from the preceding paragraph. Does it make sense now? -- EJ (talk) 13:17, 17 January 2008 (UTC)
Thanks for the response, I do understand these now (with a bit more work).
For the first point: I read in the earlier text "[not] 2n/3<p<n since then p>sqrt(2n) and so ...". I didn't notice that it then uses 2n/3<p again in the derivation, so it really does prove it only for that range and not for sqrt(2n)<p<n.
For the second point: I'd got R(p,n)<=2n in my head (rather than R(p,n)<=log_p(2n)), so no wonder I couldn't derive the right product.
I may have a go at putting in some elided steps that might have helped me avoid the confusion, but I'll wait to see if I still think they'd be valuable after I've aborbed the whole thing more fully. Hv (talk) 16:37, 17 January 2008 (UTC)
I've taken the liberty of making some clarifications in these deductions already; you have convinced me that what was there was too terse. Ryan Reich (talk) 19:34, 17 January 2008 (UTC)
Cool, thanks; I added a minor correction. Hv (talk) 11:54, 18 January 2008 (UTC)

## Is Lemma 2 Correct?

I'm just going to state what I believe is a counterexample. The largest power of 3 that divides ${\displaystyle \textstyle {\binom {18}{9}}}$ is 81, which is certainly greater than 18. Am I missing something? Xylune (talk) 06:14, 2 August 2008 (UTC)

:R(p,n) isn't the highest power of p that divides n, it's the exponent of the highest power. In this case 81=34 so R(p,n)=4 ≤ 18 as required. —David Eppstein (talk) 07:03, 2 August 2008 (UTC)

Sorry! I forgot to divide (2n)! by n! twice. In fact, 3 doesn't divide ${\displaystyle \textstyle {\binom {18}{9}}}$ at all. Whoops. -Xylune (talk) 08:10, 2 August 2008 (UTC)

## Another Proof

Ramanujan's proof is needed as to explain the prime numbers which bare his name.

The beauty of this proof is not in the simplicity, but in the foundation which can be used for other proofs. Namely, with the help of a new paper by Hashimoto (July, 2008), we can prove Legendre's conjecture.

Can we make another section which explains Ramanujan proof? I am not a good writer, but do understand the general concept of why it is important. Namely, the increase in the number of Ramanujan primes, Ri, increases the number of primes between n and 2*n with n > Ri. This is the foundation of other proofs.

Hashimoto (July, 2008) http://arxiv.org/abs/0807.3690

Reddwarf2956 (talk) 11:35, 29 September 2009 (UTC)

## Two remarks

I really enjoyed this very clear exposition! I have a couple of remarks.

• Although this is written in form of a proof by contradiction, the argument by contradiction is not really needed. One could put it more naturally (IMO) as an a priori bound on the numbers n that fail to satisfy the thesis, plus a direct examination of the remaining small cases, a kind of customary procedure in mathematics. Thus, if there is no prime between n and 2n then n verifies an inequality yielding to n < 468, and then one checks the remaining cases (so I'd suggest to move the first lines of the proof, about the small values of n, to the end.)
• The slightly stronger lower bound for the central binomial coefficient,
${\displaystyle {\frac {4^{n}}{2n}}\leq {2n \choose n}}$

is also available (we may just put together ${\displaystyle \scriptstyle {2n \choose 0}}$ and ${\displaystyle \scriptstyle {2n \choose 2n}}$ in the sum, so that the number of terms in the sum is now 2n). The latter gives a somehow nicer final inequality ${\displaystyle \scriptstyle 2^{\frac {2n}{3}}\leq (2n)^{{\sqrt {2n}}+1}\;,}$ that yields quickly to n < 468 (the conclusion, although standard, may be not immediate, and of interest to some reader). --pma 15:46, 19 September 2012 (UTC)

Let me add a link to a very nice explanation about why we like more direct proofs (even in form of contrapositive) than a proof by contradiction: http://mathoverflow.net/questions/12342/reductio-ad-absurdum-or-the-contrapositive/12400#12400 (BTW, another famous theorem about prime numbers, the Euclid proof of infinitude, is also sometimes written in form of reductio ad absurdum, although the original proof was constructive!) --pma 16:21, 19 September 2012 (UTC)

## Great big hole in proof

The proof in this article is very incomplete and skipped a very large number of steps. The article did not prove that the two functions ${\displaystyle {\frac {\log 4}{3}}n}$ & ${\displaystyle ({\sqrt {2n}}+1)\log 2n}$ cross between 467 & 468. It would take so many steps to prove the latter statement that it would be better to change the method of proof than to fill in all those missing steps. The proof in this article can be completed as follows:

Taking logarithms, we get ${\displaystyle {\frac {\log _{2}4}{3}}n\leq ({\sqrt {2n}}+1)\log _{2}2n\quad \Rightarrow \quad {\frac {2}{3}}n\leq ({\sqrt {2n}}+1)\log _{2}2n\quad \Rightarrow \quad 2n\leq ({\sqrt {2n}}+1)(3\log _{2}2n)}$ but ${\displaystyle 2n>({\sqrt {2n}}+1)({\sqrt {2n}}-1)=2n-1}$ so ${\displaystyle {\sqrt {2n}}-1<3\log _{2}2n}$ Suppose n = 512, then ${\displaystyle {\sqrt {2n}}-1=31>3\log _{2}2n=30.}$ In addition to that, ${\displaystyle {\frac {d}{dn}}({\sqrt {2n}}-1)={\frac {1}{\sqrt {2n}}}>{\frac {3}{n}}>{\frac {3ln2}{n}}={\frac {d}{dn}}(3\log _{2}2n)}$ for any n > 18 so ${\displaystyle {\sqrt {2n}}-1>3\log _{2}2n}$ for all n ≥ 512. This gives the contradiction n < 512. Thus for all n ≥ 1, there exists a prime number p such that n < p ≤ 2n.

The list 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 has no problem since 512 < 631 < 2 × 512. Blackbombchu (talk) 02:57, 17 June 2013 (UTC)

This is not a hole. In mathematics, "proof" has two different meanings: (1) a step by step reduction in which each step uses only the basic axioms of the system, the sort of thing that took Principia Mathematica over a thousand pages to prove 1+1=2, or (2) a logical argument in which all the missing steps are at a level that would be considered easy to the intended audience of the proof. The proof presented in this article is a proof of the second sort, and there is no need for a complex sequence of deductive steps to expand the proof to show a crossover of functions, when it is trivial to test the crossover by anyone with a calculator. For instance, it can be done in Python as follows:
>>> from math import log
>>> def test(n): return (log(4)*n/3, ((2*n)**0.5+1)*log(2*n))
>>> test(467)
(215.79982221432962, 215.8635445367321)
>>> test(468)
(216.26192033470292, 216.15480039082343)
David Eppstein (talk) 22:44, 23 September 2012 (UTC)

I am responsible for the current form of the conclusion of the proof. The previous version ended more or less at the inequality
${\displaystyle 4^{n/3}\leq (2n)^{{\sqrt {2n}}+1}}$,
and I added a few lines because the conclusion could be unclear to a non-mathematical reader. However, I think we prefer not to include here too long and tedious computations, as explained by David Eppstein, so I was looking for a balance between clarity and brevity. That said, the idea of the anonymous user 99.225.239.166, of testing the above inequality, written :${\displaystyle {\frac {2n}{3}}\leq ({\sqrt {2n}}+1)\log _{2}2n\;}$ on odd powers of 2, seems good to me.
So for ${\displaystyle n=2}$ the inequality is true, being
${\displaystyle 4/3\leq 6}$;
for ${\displaystyle n=2^{9}}$ it is false, reducing to
${\displaystyle 2^{10}=1024\leq 3(2^{5}+1)(10)=990}$.
Being already established that the set where the inequality holds is an interval, one has as before ${\displaystyle n<512}$, so that the list of 10 prime numbers 2,..,631 still suffices.--pma 23:25, 24 September 2012 (UTC)

## Font

This is a really nice article...the only thing is, the in-line math mode is visually distracting, esp. if the HTML font size is small. Unfortunately, I don't see any way around this without completely disrupting the readability of the proof. Maybe this is an issue that will be solved as the wiki evolves. Revolver 18:42, 31 Jan 2004 (UTC)

This doesn't help the people who don't have Wikipedia logins, but you could try turning on Mathjax (in preferences ⇒ appearance ⇒ math). It will probably look better that way. —David Eppstein (talk) 00:17, 25 November 2012 (UTC)