Prueba del postulado de Bertrand

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

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

Los pasos principales de la prueba son los siguientes. Primero, se demuestra que la contribución de cada factor de potencia primo en la descomposición en primos del coeficiente binomial central es como máximo ; luego, se demuestra que cada primo mayor que aparece como máximo una vez.$estilo de visualización p^{r}}$${\displaystyle \textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}}$${\estilo de visualización 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 procedente de los factores primos que son como máximo crece asintóticamente como para algún . Puesto que el crecimiento asintótico del coeficiente binomial central es al menos , la conclusión es que, por contradicción y para suficientemente grande , 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}}}$${\estilo de visualización n}$${\displaystyle \theta ^{\!\;n}}$${\displaystyle \theta <4}$${\displaystyle 4^{n}\!/2n}$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización 2n}$

El argumento dado es válido para todos los valores de . Los valores restantes de  se verifican mediante inspección directa, lo que completa la prueba.${\displaystyle n\geq 427}$${\estilo de visualización n}$

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

Para cualquier entero , tenemos${\estilo de visualización n>0}$

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

Demostración: 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}},}$

ya que es el término más grande en 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}$

Para un primo fijo , defina como el orden p -ádico de , es decir, el número natural más grande tal que divide a .${\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}$

Demostración: El exponente de in está 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.}$

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

Demostración: 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 provenientes de una copia del término en cada uno de los dos factores de . Todos estos factores se cancelan, por lo que no quedan factores de en . (El límite de en las condiciones previas del lema garantiza que es demasiado grande para ser un término del numerador, y se necesita la suposición de que es impar para garantizar que solo aporta un factor de al 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}$

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

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

donde se toma el producto 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 se cumple para todos los . Como es compuesta, tenemos${\displaystyle 1\leq n\leq 2k-1}$${\displaystyle n=2k>2}$

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

Supongamos ahora que la desigualdad se cumple para todo . Como es un entero y todos los primos aparecen solo 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}.}$

Supongamos que hay un contraejemplo : un 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 primo más grande menor que el doble de su predecesor) tales que n  <  p  < 2 n . Por lo tanto, n  ≥ 427.

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

• 2 n < p , porque cada 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 . Por el Lema 2, para cualquier primo p tenemos p ^{R ( p , n )} ≤ 2 n , y como 1 no es primo ni compuesto. Entonces, 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 se simplifica a${\displaystyle 2^{\sqrt {2n}}\leq (2n)^{3}.}$

Tomando logaritmos obtenemos

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

Por la concavidad del lado derecho en función de n , la última desigualdad se verifica necesariamente en un intervalo. Como es cierta para y no es cierta 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.

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

Para obtener , 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}}}$

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

• Teorema de Chebyshev y postulado de Bertrand (Leo Goldmakher): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf
• Prueba del postulado de Bertrand (Círculo de Matemáticas de la Universidad de Washington): 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". MathWorld .