Talk:Proof of Bertrand's postulate

From Wikipedia, the free encyclopedia

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)

[edit] 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 pR(p,n) ≤ 2n, so the product of the pR(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} \le \prod{(p^{R(p,n)} \le p^{2n})} \le {(\sqrt{2n})\#}^{2n} \le {(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 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:
\binom{2n}n=\prod_{p\le 2n/3}p^{R(p,n)}= \prod_{p\le\sqrt{2n}}p^{R(p,n)}\prod_{\sqrt{2n}<p\le2n/3}p^{R(p,n)}\le \prod_{p\le\sqrt{2n}}2n\prod_{\sqrt{2n}<p\le2n/3}p\le
\le(2n)^{\sqrt{2n}}\prod_{\sqrt{2n}<p\le2n/3}p\le (2n)^{\sqrt{2n}}\prod_{p\le2n/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)