Prueba del postulado de Bertrand

Problema de números primos resuelto

En matemáticas , el postulado de Bertrand (ahora teorema ) establece que, para cada , existe un primo tal que . Conjeturada por primera vez en 1845 por Joseph Bertrand , ^[1] fue probada por primera vez por Chebyshev , y Ramanujan proporcionó una prueba más breve pero también avanzada . ^[2] ${\displaystyle n\geq 2}$ ${\displaystyle p}$ ${\displaystyle n<p<2n}$

La siguiente prueba elemental fue publicada por Paul Erdős en 1932, como una de sus primeras publicaciones matemáticas. ^[3] La idea básica es mostrar que los coeficientes binomiales centrales deben tener un factor primo dentro del intervalo para que sean lo suficientemente grandes. Esto se logra mediante el análisis de sus factorizaciones. ${\displaystyle (n,2n)}$

Los principales pasos de la prueba son los siguientes. Primero, se muestra que la contribución de cada factor de potencia primo en la descomposición prima del coeficiente binomial central es como máximo ; entonces, se muestra que cada número primo mayor que aparece como máximo una vez. ${\displaystyle p^{r}}$ ${\displaystyle \textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}}$ ${\displaystyle 2n}$ ${\displaystyle {\sqrt {2n}}}$

El siguiente paso es demostrar que no tiene factores primos en el intervalo . Como consecuencia de estos límites, la contribución al tamaño de los factores primos que son como máximo crece asintóticamente como para algunos . Dado que el crecimiento asintótico del coeficiente binomial central es al menos , la conclusión es que, por contradicción y para , el coeficiente binomial debe tener otro factor primo, que sólo puede estar entre y . ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle ({\tfrac {2n}{3}},n)}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle n}$ ${\displaystyle \theta ^{\!\;n}}$ ${\displaystyle \theta <4}$ ${\displaystyle 4^{n}\!/2n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2n}$

El argumento dado es válido para todos . Los valores restantes de  son por inspección directa, lo que completa la prueba. ${\displaystyle n\geq 427}$ ${\displaystyle n}$

Lemas en la prueba

La prueba utiliza los siguientes cuatro lemas para establecer hechos sobre los primos presentes en los coeficientes binomiales centrales.

Lema 1

Para cualquier número entero , tenemos ${\displaystyle n>0}$

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}$

Prueba: aplicando el teorema del binomio ,

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}$

puesto que es el término más grande de la suma en el lado derecho, y la suma tiene términos (incluido el inicial fuera de la suma). ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle 2n}$ ${\displaystyle 2}$

Lema 2

Para un primo fijo , defina como el orden p -ádico de , es decir, el número natural más grande tal que divide . ${\displaystyle p}$ ${\displaystyle R=R(n,p)}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle r}$ ${\displaystyle p^{r}}$ ${\displaystyle {\tbinom {2n}{n}}}$

Para cualquier primo , . ${\displaystyle p}$ ${\displaystyle p^{R}\leq 2n}$

Prueba: el exponente de in viene dado por la fórmula de Legendre ${\displaystyle p}$ ${\displaystyle n!}$

${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \!,}$

entonces

${\displaystyle R=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\!\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right)}$

Pero cada término de la última suma debe ser cero (si ) o uno (si ), y todos los términos con son cero. Por lo tanto, ${\displaystyle n/p^{j}{\bmod {1}}<1/2}$ ${\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}$ ${\displaystyle j>\log _{p}(2n)}$

${\displaystyle R\leq \log _{p}(2n),}$

y

${\displaystyle p^{R}\leq p^{\log _{p}(2n)}=2n.}$

Lema 3

Si es un primo impar y , entonces ${\displaystyle p}$ ${\displaystyle {\frac {2n}{3}}<p\leq n}$ ${\displaystyle R(n,p)=0.}$

Prueba: Hay exactamente dos factores de en el numerador de la expresión , provenientes de los dos términos y en , y también dos factores de en el denominador de una copia del término en cada uno de los dos factores de . Todos estos factores se cancelan, sin dejar factores de in . (El límite en las condiciones previas del lema garantiza que sea demasiado grande para ser un término del numerador, y la suposición de que es impar es necesaria para garantizar que contribuya solo con un factor del numerador). ${\displaystyle p}$ ${\displaystyle {\tbinom {2n}{n}}=(2n)!/(n!)^{2}}$ ${\displaystyle p}$ ${\displaystyle 2p}$ ${\displaystyle (2n)!}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n!}$ ${\displaystyle p}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle p}$ ${\displaystyle 3p}$ ${\displaystyle p}$ ${\displaystyle 2p}$ ${\displaystyle p}$

Lema 4

Se proporciona un límite superior para la función primordial ,

${\displaystyle n\#=\prod _{p\,\leq \,n}p,}$

donde el producto se toma de todos los números primos menores o iguales a . ${\displaystyle p}$ ${\displaystyle n}$

Para todos , . ${\displaystyle n\geq 1}$ ${\displaystyle n\#<4^{n}}$

Prueba: utilizamos inducción completa .

Porque tenemos y . ${\displaystyle n=1,2}$ ${\displaystyle 1\#=1<4}$ ${\displaystyle 2\#=2<4^{2}=16}$

Supongamos que la desigualdad es válida para todos . Como es compuesto, tenemos ${\displaystyle 1\leq n\leq 2k-1}$ ${\displaystyle n=2k>2}$

${\displaystyle (2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.}$

Ahora supongamos que la desigualdad es válida para todos . Como es un número entero y todos los números primos aparecen sólo en el numerador, tenemos ${\displaystyle 1\leq n\leq 2k}$ ${\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}$ ${\displaystyle k+2\leq p\leq 2k+1}$

${\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}.}$

Por lo tanto,

${\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}{\binom {2k+1}{k}}<4^{k+1}\cdot 4^{k}=4^{2k+1}.}$

Prueba del postulado de Bertrand

Supongamos que hay un contraejemplo : un número entero n  ≥ 2 tal que no hay ningún primo p con n  <  p  < 2 n .

Si 2 ≤ n < 427, entonces p puede elegirse entre los números primos 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (siendo cada uno el mayor primo menor que el doble de su predecesor) de modo que norte  <  pag  < 2 norte . Por tanto, n  ≥ 427.

No existen factores primos p de tales que: ${\displaystyle \textstyle {\binom {2n}{n}}}$

• 2 n < p , porque todo factor debe dividir (2 n )!;
• p = 2 n , porque 2 n no es primo;
• n < p < 2 n , porque asumimos que no existe tal número primo;
• 2 n  / 3 < p ≤ n : por el Lema 3.

Por lo tanto, todo factor primo p satisface p ≤ 2 n  / 3.

Cuando el número tiene como máximo un factor de p . Según el Lema 2, para cualquier primo p tenemos p ^{R ( p , n )} ≤ 2 n , y dado que 1 no es primo ni compuesto. Luego, comenzando con el Lema 1 y descomponiendo el lado derecho en su factorización prima, y ​​finalmente usando el Lema 4, estos límites dan: ${\displaystyle p>{\sqrt {2n}},}$ ${\displaystyle \textstyle {2n \choose n}}$ ${\displaystyle \pi (x)\leq x-1}$

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}p^{R(p,n)}\right)\!\!\left(\prod _{{\sqrt {2n}}\,<\,p\,\leq \,2n/3}\!\!\!\!\!\!\!p^{R(p,n)}\right)<\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}\!\!2n\right)\!\!\left(\prod _{p\,\leq \,2n/3}\!\!p\right)\leq (2n)^{{\sqrt {2n}}-1}4^{2n/3}.}$

Por lo tanto

${\displaystyle 4^{n/3}\leq (2n)^{\sqrt {2n}}}$, lo que simplifica a ${\displaystyle 2^{\sqrt {2n}}\leq (2n)^{3}.}$

Tomando logaritmos se obtiene

${\displaystyle {\sqrt {2n}}\leq 3\log _{2}(2n).}$

Por concavidad del lado derecho en función de n , la última desigualdad se verifica necesariamente en un intervalo. Como es válido para y no para , obtenemos ${\displaystyle n=426}$ ${\displaystyle n=427}$

${\displaystyle n<427.}$

Pero estos casos ya han sido resueltos y concluimos que no es posible ningún contraejemplo al postulado.

Anexo a la prueba

Es posible reducir el límite a . ${\displaystyle n=50}$

Porque obtenemos , por lo que podemos decir que el producto es como máximo , lo que da ${\displaystyle n\geq 17,}$ ${\displaystyle \pi (n)<{\frac {n}{2}}-1}$ ${\displaystyle p^{R}}$ ${\displaystyle (2n)^{0.5{\sqrt {2n}}-1}}$

${\displaystyle {\begin{aligned}&{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}\leq (2n)^{0.5{\sqrt {2n}}-1}4^{2n/3}\\&4^{\sqrt {2n}}\leq (2n)^{3}\\&2{\sqrt {2n}}\leq 3\log _{2}(2n)\end{aligned}}}$

que es verdadero y falso para . ${\displaystyle n=49}$ ${\displaystyle n=50}$

Referencias

1. Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.", Journal de l'École Royale Polytechnique (en francés), 18 (Cahier 30) : 123-140.
2. Ramanujan, S. (1919), "Una prueba del postulado de Bertrand", Revista de la Sociedad Matemática de la India , 11 : 181–182
3. {{cita | último = Erdős | primero = Pál | enlace de autor = Paul Erdős | diario = Acta Litt. Ciencia. Szeged | idioma = de | páginas = 194–198 | título = Beweis eines Satzes von Tschebyschef | trans-title = Demostración de un teorema de Chebyshev | URL = https://users.renyi.hu/~p_erdos/1932-01.pdf | volumen = 5 | año = 1932 | zbl = 0004.10103}}

enlaces externos

• Teorema de Chebyshev y postulado de Bertrand (Leo Goldmakher): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf
• Prueba del postulado de Bertrand (UW Math Circle): https://sites.math.washington.edu/~mathcircle/circle/2013-14/advanced/mc-13a-w10.pdf
• Prueba en el sistema Mizar : http://mizar.org/version/current/html/nat_4.html#T56
• Weisstein, Eric W. "Postulado de Bertrand". MundoMatemático .