1
$\begingroup$

In Wikipedia's proof of Bertrand's Postulate, in the second lemma, it is concluded that:

$$R = R(p,{{2n}\choose{n}}) \le \log_p 2n$$

where $R(p,n)$ is the p-adic order of ${2n}\choose{n}$

Later in the main proof, the implication is:

$$\prod\limits_{p \le \sqrt{2n}}p^{R(p,{{2n}\choose{n}})} \le (2n)^{\pi(\sqrt{2n})}$$

It seems to me that there is a slightly stronger upper bound that is also implied.

$$\prod\limits_{p \le \sqrt{2n}}p^{R(p,{{2n}\choose{n}})} \le \frac{(2n)!}{(2n - \pi(\sqrt{2n}))!}$$

Am I wrong?

Here's my thinking:

(1) For each prime $p \le \sqrt{2n}$, there exists one unique number $p^{R(p,{{2n}\choose{n}})}$ that is less than or equal to $2n$.

(2) Since each $p^{R(p,{{2n}\choose{n}})} \le 2n$ and distinct, it follows that $\prod\limits_{p \le \sqrt{2n}} p^{R(p,{{2n}\choose{n}})}$ will be less than or equal to $\frac{(2n)!}{(2n - \pi(\sqrt{2n}))!}$


Edit: I made the changes pointed out by John Omielan.

$\endgroup$
1
  • 1
    $\begingroup$ Two very minor points are that your $2n^{\pi(\sqrt{2n})}$ should be $(2n)^{\pi(\sqrt{2n})}$ instead, and your (2)'s "will be less than" doesn't technically follow, with "will be less than or equal to" being the correct phrase (although I believe that it will actually always be less than, the logic you're using technically only allows it to be less than or equal). $\endgroup$ Commented Mar 16 at 2:36

1 Answer 1

1
$\begingroup$

Your slightly stronger upper bound, and your thinking regarding it, are both correct. Good work. Nonetheless, FWIW, here's an alternate way to explain your (2). Let $\sigma$ be a permutation of $p^{R(p,{{2n}\choose{n}})}$ for all primes $p \le \sqrt{2n}$, with the values being in strictly decreasing order. With $m = \pi(\sqrt{2n})$, we therefore have

$$2n \ge \sigma_{1} \gt \sigma_{2} \gt \ldots \gt \sigma_{m} \;\;\to\;\; \sigma_{i} \le 2n - (i - 1) \; \forall \; 1 \le i \le m$$

Thus, by the commutative property of multiplication, we then get

$$\prod_{p \le \sqrt{2n}}p^{R(p,{{2n}\choose{n}})} = \prod_{i=1}^{m}\sigma_{i} \le \\ \prod_{i=1}^{m}(2n - i + 1) = (2n)\cdots(2n-\pi(\sqrt{2n})+1) = \frac{(2n)!}{(2n - \pi(\sqrt{2n}))!}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .