Talk:Proof of Bertrand's postulate

Lemma 4 is missing details

The inductive proof is outlined but the inductive step is never proven. The claim is stated but without proof is not complete.

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 $(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 $(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 $p>{\sqrt {2n}},$ the number ${2n \choose n}$ has at most one factor of p. By Lemma 2, for any prime p we have p^R(p,n) ≤ 2n, so the product of the p^R(p,n) over all other primes is at most $(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 $p>{\sqrt {2n}}$ the number ${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 ${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 $(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 p^R(p,n) ≤ 2n by lemma 2), and one for primes p > √(2n) (for which we have R(p,n) ≤ 1 by lemma 3). So:

${\binom {2n}{n}}=\prod _{p\leq 2n/3}p^{R(p,n)}=\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\prod _{{\sqrt {2n}}<p\leq 2n/3}p^{R(p,n)}\leq \prod _{p\leq {\sqrt {2n}}}2n\prod _{{\sqrt {2n}}<p\leq 2n/3}p\leq$

$\leq (2n)^{\sqrt {2n}}\prod _{{\sqrt {2n}}<p\leq 2n/3}p\leq (2n)^{\sqrt {2n}}\prod _{p\leq 2n/3}p=(2n)^{\sqrt {2n}}(2n/3)\#,$

using the fact that all prime divisors of $\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 $\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=3⁴ 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 $\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.

http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper24/page1.htm

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, R_i, increases the number of primes between n and 2*n with n > R_i. 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,

${\frac {4^{n}}{2n}}\leq {2n \choose n}$

is also available (we may just put together $\scriptstyle {2n \choose 0}$ and $\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 $\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 ${\frac {\log 4}{3}}n$ & $({\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 ${\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 $2n>({\sqrt {2n}}+1)({\sqrt {2n}}-1)=2n-1$ so ${\sqrt {2n}}-1<3\log _{2}2n$ Suppose n = 512, then ${\sqrt {2n}}-1=31>3\log _{2}2n=30.$ In addition to that, ${\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 ${\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

$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 :${\frac {2n}{3}}\leq ({\sqrt {2n}}+1)\log _{2}2n\;$ on odd powers of 2, seems good to me.

So for $n=2$ the inequality is true, being

$4/3\leq 6$;

for $n=2^{9}$ it is false, reducing to

$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 $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)

Proof of lemma 3

I find myself unable to understand the proof of lemma 3. "The factors of p in the numerator", I do not see to what expression this refers. Does this refer to the expression of 2n choose n or to the expression of R(p,n) in lemma 2? 82.74.20.26 (talk) 22:38, 17 January 2015 (UTC)

I added a little more explaining what expression the numerator and denominator are numerator and denominator of. —David Eppstein (talk) 22:53, 17 January 2015 (UTC)

I thank you for your quick response. Could you perhaps explain why it is required that ${\frac {2n}{3}}\leq p\leq n$?

Those bounds are used to count how many factors of p show up in the numerator and denominator. If p were smaller there would be more factors and if it were larger there would be fewer. —David Eppstein (talk) 23:19, 17 January 2015 (UTC)

Lemma 4 being reviewed

Please see math.SE for a review of Lemma 4. Mark Hurd (talk) 00:25, 3 February 2015 (UTC)

Lemma 4 appears to have a factual error. At the time of this writing it claims that ${\binom {2n}{n}}<2^{2n-2}$ when n≥3. But simply plugging in n=3 gives 20<16, and plugging in n=4 gives 70<64. Furthermore, no justification is given for the claimed (but incorrect) inequality. Qaanol (talk) 17:47, 5 April 2015 (UTC)

In fact, the bound in Lemma 4, $x\#\leq 2^{2x-3}$ is a bit stronger that needed, which is $x\#\leq 4^{x}$.

pma 07:50, 20 December 2018 (UTC)

"Proof by Shigenori Tochiori"

What is the point of adding this section? It is by no means another proof, and not even "a refinement of Erdős' method", as stated. Of course, with more effort, one can improve the inequalities in the lemmas of Erdős' proof, so to make smaller the finite initial interval of primes that need to be checked by hand. Erdős managed to find extremely simple and elementary inequalities, yet leaving only 10 primes to be checked separately. This Shigenori Tochiori's variation adds nothing to Erdős' proof, but only makes it unnecessarily complicated and technical, to the only improvement of sparing these three inequalities:

$2\times 83>163,\qquad 2\times 163>317,\qquad 2\times 317>631.$

I think the exposition of the article would greatly gain in clarity and simplicity if we remove this unnecessary last section; I try and see how it looks like. pma 09:16, 8 October 2018 (UTC)

The Tochiori version was used as reference material for the Metamath formalization. Aside from the use of smaller primes which require less explicit computation, the calculation of the bound 468 for the log inequality requires a *lot* more high precision calculation, and more technical material than is developed on this page. I believe Erdos' original method puts the bound at 4001 with a more relaxed method. By contrast, the Tochiori bound at 64 works effortlessly and can be done entirely by hand.

Moreover, that section is the only translation of Tochiori's paper I am aware of. I will restore the section with some clarifications about its relation to the proof above it. Even if the section is deleted again, I would greatly appreciate if at least the reference to Tochiori is retained. —Marco Polo 23:31, 23 May 2019 (UTC)

Things that need explaning

1. "When $p>{\sqrt {2n}},$ the number $\textstyle {2n \choose n}$ has at most one factor of p."

This needs to be explained.

2. This whole section goes way too fast with multiple steps in a single line:

"Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

${\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\right)\left(\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{R(p,n)}\right)<(2n)^{\sqrt {2n}}\prod _{1<p\leq {\frac {2n}{3}}}p=(2n)^{\sqrt {2n}}\left({\frac {2n}{3}}\right)\#\leq (2n)^{\sqrt {2n}}4^{2n/3}.$

Taking logarithms yields to

${\frac {\log 4}{3}}n\leq ({\sqrt {2n}}+1)\log 2n\;.$

By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval."

I know that whoever posted the proof as it currently appears did a lot of work, and I am grateful for that.

Nevertheless, the last few steps need to be teased apart so that only one step occurs per line, so that it becomes possible to follow the reasoning.

Also: Replace "yields to" with just "yields". 2601:200:C000:1A0:306B:A689:CCD1:440 (talk) 09:46, 20 September 2021 (UTC)

Section : Proof of the Bretrand's postulate

The 3rd point • is false ! Any prime p such that n < p < 2n appears exactly once in the decomposition of 2n choose n. So all the proof shoul'd be reviewed. 176.177.54.9 (talk) 14:22, 7 December 2022 (UTC)