Hay Combinatoric pruebas de Bertrand postulado?

Question

Me siento como debe existir una combinatoric la prueba de un teorema como: Hay un primer entre el $n$ $2n$ o $p$ $p^2$ o cualquier cosa similar a esta más fuerte que hay un primer entre el $p$ $(\prod_p p) + 1$ (del teorema de Euclides).

Yo estaba tratando de probar uno por el Tamiz de esta cuadrícula

    1     2     3     4 ... p
  p+1   p+2   p+3   p+4 ... 2p
 2p+1  2p+2  2p+3  2p+4 ... 3p
...........................
...........................
........................... p^2
p^2+1 p^2+2 p^2+3 p^2+4 ...

pero no funcionó.

Hacer ningún bien a argumentos como este existen? No espero nada tan fuerte como el Teorema de los números Primos o incluso Bertrand, pero sin duda una combinación directa de la prueba puede demostrar que hay un montón de números primos?

Answer 1

Interesante idea utilizar una cuadrícula. Dudo que va a trabajar para esta pregunta, ya que la escritura de las cosas en que formato de cuadrícula en un sentido divide en progresiones aritméticas modulo $p$, y suele decir cosas sobre los números primos en una progresión es más difícil.

Sin embargo, no puedo dejar de mencionar que el uso de una cuadrícula como la que se aplicó de manera brillante por Maier para probar un contra-intuitivo resultado (usando el Teorema de los números Primos de la Aritmética Progessions) y la idea es que ahora se llama la Maier Método de la Matriz.

(Una pequeña digresión, pero es muy interesante!)

El Maier Método De La Matriz

No hay preguntas sobre números primos en un breve intervalo de tiempo, y podemos preguntarnos ¿qué $$\pi(x+y)-\pi(x)$$ look like? To say anything meaningful, $y$ cannot be too small, but here lets suppose $y=\log^B(x)$ for some $B>2$. Selberg proved that under the Riemann Hypothesis, we have $$\pi(x+y)-\pi(x)\sim \frac{y}{\log x}$$ as $x\rightarrow \infty$ for almost all $x$. (A set with density $\rightarrow 1$) It was then conjectured that this asymptotic must hold for all $x$ que son lo suficientemente grandes. (Esta conjetura se hizo por varias razones, una de ellas es la que es verdadera en virtud de Cramer modelo probabilístico)

En un sorprendente giro de los acontecimientos, Maier se demostró que era falso, y que no existe $\delta>0$ y arbitrariamente grandes valores de$x_1$$x_2$, de forma que ambos $$\pi(x_1 +\log^B (x_1))-\pi (x_1)> (1+\delta)\log^{B-1}(x_1)$$and $$\pi(x_2 +\log^B (x_2))-\pi (x_2)< (1-\delta)\log^{B-1}(x_2)$$hold, despite the fact that the asymptotic holds for a set of density $1$.

Él lo demostró el uso de un método que se llama ahora la "Maier Método de la Matriz." Esencialmente, es solo dibujar una cuadrícula que es similar a la anterior, y, a continuación, aplicar un ingenioso argumento combinatorio. Las columnas son progresiones aritméticas, y por PNT4AP, fácilmente podemos decir cosas acerca de ellos para entender el número de números primos en la red. Hay un pequeño truco con la oscilación de la Dickman Función, pero luego, básicamente, por la encasillar a principio de que la cuestión se resuelve.

Definitivamente creo que usted podría encontrar este expositiva artículo por el Dr. Andrew Granville a ser interesante. (Es bastante fácil de leer, y le da una mayor profundidad, y muy clara la explicación)

Answer 2

Aquí es elemental argumento que muestra que hay "un montón" de los números primos. Considerar el número de números en el intervalo de $[1, n]$. Por un lado, esto es $n$. Por otro lado, por única factorización de cada número puede ser el único escrito en el formulario de $\prod_{i=1}^{\pi(n)} p_i^{e_i}$. De ello se desprende que $n$ es igual al número de número entero no negativo soluciones a

$$e_1 \log p_1 + ... + e_{\pi(n)} \log p_{\pi(n)} \le \log n.$$

Esto es fácilmente visto en la mayoría de las $\left( \log_2 n \right)^{\pi(n)}$, por lo tanto

$$n \le (\log_2 n)^{\pi(n)}$$

a partir de la cual se deduce que

$$\pi(n) \ge \frac{\log n}{\log \log_2 n}.$$

Podría ser posible extraer una forma débil de Bertrand postulado a partir de este argumento.

Answer 3

Editado: Aquí es muy relevante enlace sobre Robin Chapman de la página. Es la combinatoria de la prueba que Erdos originalmente usado para demostrar Bertrands postulado. (Mencionadas en el Pete L. Clark comentario)

El PDF es muy similar a las pruebas que he mencionado aquí, (y aquí) y se basa totalmente en los números primos de la división de la central de coeficiente binomial.

Voy a dejar en la prueba con respecto a un límite inferior para $\pi(x)$, ya que todavía es relevante.

Lo que sigue es una prueba el Teorema de Chebyshev basado en los números primos de la división de la central de coeficiente binomial. En primer lugar, dos hechos bien conocidos:

Hecho 1: Vamos a $r(n,p)$ denotar el más alto poder de un primer $p$ que divide $n!$. A continuación, $$r(n,p)=\lfloor\frac{N}{p}\rfloor+\lfloor\frac{2N}{p^{2}}\rfloor+\lfloor\frac{2N}{p^{3}}\rfloor+\cdots$$

Hecho 2: Para cada entero $N\geq1$ tenemos que $$\frac{4^{N}}{2N}\leq\binom{2N}{N}.$$

Teorema: Tenemos que $$\pi(x)\geq\ln(2)\frac{x}{\ln x}-2.$$

Prueba. Considere la posibilidad de $\binom{2N}{N}.$ Para cada uno de los prime $p$, vamos a $v_{p}$ denotar el número de veces que se divide $\binom{2N}{N}$. Por lo tanto $$\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}.$$ Let $t=\log_{p}(2N)$ so that $\lfloor\frac{2N}{p^{j}}\rfloor=0$ when $j\geq t.$ By the lemma, we have $$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.$ Hence if $p^{r}$ divides $\binom{2N}{N}$ we must have $p^{r}\leq2N.$ Consequently $$\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}\leq\prod_{p\leq2N}(2N)=(2N)^{\pi(2N)}.$$Applying the other lemma we get $\frac{4^{N}}{2N}\leq(2N)^{\pi(2N)}$and upon taking logarithms we find$$N\ln4-\ln(2N)\leq\pi(2N)\ln(2N)$$and hence $$\frac{2N\ln2}{\ln2N}\leq\pi(2N)+1.$$Ya que esto tiene para cada entero, y hay un primer entre números enteros obtenemos

$$\frac{x\ln2}{\ln x}-2\leq\pi(x)\ \text{for all } \ x\geq2,$$ como se desee.