Bertrand's Theorem: prime-power decomposition proof

267 Views Asked by At

In a book on elementary number theory (pp 177-179, Underwood Dudley 2ed) I am having trouble understanding the following paragraph based on Erdos's proof using Binomial theorem:

"...each prime power in the prime-power decomposition of $N$ is at most $2n$. So if $p$ appears in the prime-power decomposition to be a power greater than 1, then $p^2 \leq 2n$ and $p \leq \sqrt(2n)$.

Where $N=\binom{2n}{n}$.

There are at most $\sqrt(2n)$ such primes, and since each prime power is at most $2n$, their contribution is at most $2n^{\sqrt(2n)}$ "

1) I can see that each prime power is less than $2n$ even from $n!$:

$\color{blue} {20! = 2^{18}3^85^47^211\,13\,17\,19}$

Indeed that is proved earlier in the text, but why for powers greater than 1 is $p^2$ used to show $p \leq \sqrt(2n)$ when the power can be $p^{2n}$?

2) then he says since each prime power is at most $2n$, their contribution is at most $2n^{\sqrt(2n)}$, if the prime power is a maximum of $2n$ and there are $\sqrt(2n)$ of them why would the maximum possible prime-power be raised to the maximum possible number of them to give the maximum possible product of primes greater than power 1 in $N=\binom{2n}{n}$?

1

There are 1 best solutions below

0
On BEST ANSWER

I can answer your second question.

Let $p_i$ represent the $i$th prime dividing $n$ where $i$ is at most $\root \of{2n}$. Each $p_i < 2n$ so $$\prod_i p_i \le \prod_i 2n \le 2n^{\root \of{2n}}$$

As for the reason we only consider $p^2$ is because if we used $p^3$ for example we get $$\prod_i p_i \le 3n^{\root \of{3n}}$$

which is useless when we have the first bound