Chebyshev: Proof $\prod \limits_{p \leq 2k}{\;} p > 2^k$

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.

Solution 1:

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$.