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.

  • 2
    $\begingroup$ The left-hand side of your inequality is the same as $\exp(\vartheta(2k))$, no? Since we have the asymptotic relation $\vartheta(k) \sim k$ and $e^2 > 2$... $\endgroup$ Jan 2, 2012 at 9:14
  • 3
    $\begingroup$ @J.M. Asymptotics cannot give the desired result for every $k$ (result which is false for $k=1$, by the way). $\endgroup$
    – Did
    Jan 2, 2012 at 10:47
  • $\begingroup$ @Didier: I know; that's why I'm hoping somebody could maybe post an answer that can do much better than my comment. $\endgroup$ Jan 2, 2012 at 10:53
  • 3
    $\begingroup$ @Daniel: I can guess to reasons why you mentioned Chebyshev in the title. A) You notice that this is related to Chebyshev function. B) You saw this estimate used in the proof of (on of) Chebyshev inequalities in some book or lecture notes. If B is true, it might help people in answering your question, if you mention where you saw this inequality. $\endgroup$ Jan 2, 2012 at 11:37
  • $\begingroup$ 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. $\endgroup$
    – ulead86
    Jan 2, 2012 at 16:48

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

  • 1
    $\begingroup$ fantastic answer. Thank your very much :) $\endgroup$
    – ulead86
    Jan 2, 2012 at 14:25

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.