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

Question

¿Cómo puedo demostrar lo siguiente?

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

Intenté la inducción, pero no sabía cómo seguir porque no veo todos los números.

Agradecemos cualquier ayuda :-)

Edita: Es parte de una prueba del algoritmo AKS, dada en el libro Teoría de la codificación y criptografía de Willems, en la página 99 al final.

Answer 1

He aquí una prueba completa. Si viene de modificar esta respuesta. También hacemos uso del lema $\theta(x)\leq 3x$ que se muestra en esta respuesta. Por todas partes, $\theta(x)$ se refiere a la función ponderada de recuento de primos $\sum_{p\leq x}\log p$ .

Considere $\binom{2N}{N}.$ Para cada primo $p$ , dejemos que $v_{p}$ denota el número de veces que divide a $\binom{2N}{N}$ . Entonces $$\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}.$$ Sea $t=\log_{p}(2N)$ para que $\lfloor\frac{2N}{p^{j}}\rfloor=0$ . Ahora, usando el hecho de que sabemos cuántas veces un primo divide a $n!$ y $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ tenemos que $$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.$$ Desde $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=0$ o $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=1$ para cada $i$ vemos que $v_{p}\leq [t],$ el suelo de $t$ . Ahora observe que $[t]=1$ mientras $p>\sqrt{2N}$ y que $[t]=2$ cuando $\sqrt{2n}\geq p>(2N)^\frac{1}{3}$ etc. De ahí $$\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. $$

Ahora, como el coeficiente binomial central es el mayor, tenemos $\binom{2N}{N}\geq \frac{4^N}{2N}$ . (Obtenemos $2N$ como denominador en lugar de $2N+1$ observando $1$ aparece en ambos extremos del triángulo) Por lo tanto $$N\log 4-\log (2N) \leq \psi(2N).$$

Idea de cómo proceder: Puesto que sólo necesita $$N\log 2\leq \theta(2N),$$ podemos utilizar límites superiores para $\theta$ y eliminar las cosas indeseables de la ecuación demostrando que son menos que las otras $N\log 2$ que tiramos.

Específicos: En esta respuesta demostramos por un método similar que $\theta(x)\leq 3x$ para todos $x$ . Por lo tanto $$\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}$$ para $N\geq 200$ . Ahora, utilizando métodos de cálculo, se puede demostrar que para todo $N\geq 200$ tenemos que $$N\log 2< \log(2N)+6\sqrt{2N}.$$ Esto implica que $N\log 2<\theta(N)$ cuando $N\geq 200$ y, por tanto $$\prod_{p\leq 2N} p >2^N$$ para todos $N\geq 200$ . Ahora, basta con comprobar a través del ordenador o a mano si $N\leq 200$ y la desigualdad se demostrará para todo $N$ .