13
$\begingroup$

How do I prove the following:

$\prod_{p \leq 2k} \; p > 2^k \text{ with } p \in \mathbb{P}$

I tried induction, but I didn't know how to go on because I don't have a look at all numbers.

Any help is appreciated :-)

Edit: It's part of a proof of the AKS algorithm, given in the book Codierungstheorie und Kryptographie by Willems, on page 99 at the bottom.

  • 0
    You're right, it's part of the AKS algorithm proof, i gave no link, because it's a german textbook. Sorry for that. I added a link.2012-01-02

1 Answers 1

11

Here is a complete proof. If comes from modifying this answer. We also make use of the lemma $\theta(x)\leq 3x$ shown in this answer. Throughout, $\theta(x)$ refers to the weighted prime counting function $\sum_{p\leq x}\log p$.

Consider $\binom{2N}{N}.$ For each prime $p$, let $v_{p}$ denote the number of times it divides $\binom{2N}{N}$. Then $\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}.$ Let $t=\log_{p}(2N)$ so that $\lfloor\frac{2N}{p^{j}}\rfloor=0$. Now, using the fact that we know how many times a prime divides $n!$, and $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ we have that $v_{p}=\left(\lfloor\frac{2N}{p}\rfloor+\lfloor\frac{2N}{p^{2}}\rfloor+\cdots\right)-2\left(\lfloor\frac{N}{p}\rfloor+\lfloor\frac{N}{p^{2}}\rfloor+\cdots\right)=\sum_{i=1}^{t}\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor.$ Since $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=0$ or $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=1$ for each $i$ we see that $v_{p}\leq [t],$ the floor of $t$. Now notice that $[t]=1$ as long as $p>\sqrt{2N}$, and that $[t]=2$ when $\sqrt{2n}\geq p>(2N)^\frac{1}{3}$, etc... Hence $\log\binom{2N}{N}\leq\theta\left(2N\right)+\theta\left(\sqrt{2N}\right)+\theta\left(\left(2N\right)^{\frac{1}{3}}\right)+\cdots $ $=\psi\left(2N\right):=\sum_{p^{k}\leq2N}\log p. $

Now, since the central binomial coefficient is the largest, we have $\binom{2N}{N}\geq \frac{4^N}{2N}$. (We get $2N$ as a denominator instead of $2N+1$ by noting $1$ appears at both ends of the triangle) Hence $N\log 4-\log (2N) \leq \psi(2N).$

Idea how to proceed: Since you only need $N\log 2\leq \theta(2N),$ we can use upper bounds for $\theta$ and remove the undesirable things from the equation by showing they are less then the other $N\log 2$ which we throw away.

Specifics: In this answer here we show by a similar approach that $\theta(x)\leq 3x$ for all $x$. Hence $\theta(\sqrt{2n})+\theta\left((2n)^\frac{1}{3}\right)+\cdots\leq 3\sqrt{2n}+3(2n)^\frac{1}{3}+\cdots\leq 6\sqrt{2N}$ for $N\geq 200$. Now by using methods of calculus, you can show that for all $N\geq 200$ we have that $N\log 2< \log(2N)+6\sqrt{2N}.$ This implies that $N\log 2<\theta(N)$ when $N\geq 200$, and hence $\prod_{p\leq 2N} p >2^N$ for all $N\geq 200$. Now, just check via computer or by hand for $N\leq 200$, and the inequality will be proven for all $N$.

  • 1
    fantastic answer. Thank your very much :)2012-01-02