Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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$... –  J. M. Jan 2 '12 at 9:14
3  
@J.M. Asymptotics cannot give the desired result for every $k$ (result which is false for $k=1$, by the way). –  Did Jan 2 '12 at 10:47
    
@Didier: I know; that's why I'm hoping somebody could maybe post an answer that can do much better than my comment. –  J. M. Jan 2 '12 at 10:53
3  
@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. –  Martin Sleziak Jan 2 '12 at 11:37
    
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. –  ulead86 Jan 2 '12 at 16:48

1 Answer 1

up vote 10 down vote accepted

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

share|improve this answer
1  
fantastic answer. Thank your very much :) –  ulead86 Jan 2 '12 at 14:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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