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}$?

  • $\begingroup$ In the first line of your quote, you have "decomposition of $n$." Dudley's book has "decomposition of $N$." You need to sort out your n's before we can even understand your questions. Also, there's a typo in your factoriztion of $20!$. $\endgroup$ – B. Goddard Feb 24 '18 at 15:04
  • $\begingroup$ okay thanks for pointing that out, where is the error in 20!, I copied it from the book pp 166? $\endgroup$ – onepound Feb 24 '18 at 19:52
  • 1
    $\begingroup$ You have $20^{18}$ instead of $2^{18}.$ And I think people will need to know what $N$ is. $\endgroup$ – B. Goddard Feb 24 '18 at 20:39

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.