Demostración del postulado de Bertrand

En matemáticas, el postulado de Bertrand (ahora un teorema) establece que, para cada $n\geq 2$, hay un primo $p$ entre $n$ y su doble, es decir, tal que $n<p<2n$. Fue conjeturado por primera vez en 1845 por Joseph Bertrand, ​ pero la primera demostración la dio Chebyshev, y Ramanujan dio una prueba más corta pero también más avanzada. ​

La siguiente prueba elemental fue publicada por Paul Erdős en 1932, como una de sus primeras publicaciones matemáticas. ​ La idea básica es demostrar que los coeficientes binomiales centrales ${2n} \choose {n}$ deben tener un factor primo dentro del intervalo $(n,2n)$ con tal de ser suficientemente grandes. Esto se logra analizando sus factorizaciones.

Los pasos principales de la demostración son los siguientes. En primer lugar, se muestra que la contribución de cada factor de la forma de potencia prima $p^{r}$ en la descomposición en factores primos del coeficiente binomial central $\textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}$ es como máximo $2n$ (es decir, $p^{r}\leq 2n$); entonces, se demuestra que todo primo mayor que ${\sqrt {2n}}$ aparece en la descomposición como máximo una vez.

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

El argumento dado es válido para todos $n\geq 427$ (es decir, esto es lo que significa en el anterior párrafo "para valores de $n$ suficientemente grandes"). Al ser los valores restantes de $n$ un número finito, se puede comprobar por inspección (comprobando hasta $427$ que los números primos siguen el patrón descrito: que siempre haya uno entre cada número y su doble), y con esto se acaba la demostración.

Lemas en la demostración

La prueba utiliza los cuatro lemas siguientes para establecer hechos sobre los primos presentes en la descomposición en factores primos de los coeficientes binomiales centrales ${2n} \choose {n}$.

Lema 1

Para cualquier entero $n>0$ se satisface que

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

Demostración: Aplicando el teorema del binomio de Newton,

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

donde se ha usado en el último paso que ${\tbinom {2n}{n}}$ es el término más grande en la suma en el lado izquierdo (incluido el $2$ fuera del sumatorio), y la suma tiene $2n$ términos (incluido el inicial $2$ fuera del sumatorio). Despejando se obtiene la inecuación deseada. $\quad \square$

Lema 2

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

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

Demostración: El exponente de $p$ en la descomposición en números primos de $n!$ viene dado por la fórmula de Legendre:

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

de manera que, como $\textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}$,

$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 del último sumatorio sólo puede ser cero (si la parte fraccionaria $n/p^{j}{\bmod {1}}<1/2$) o uno (si $n/p^{j}{\bmod {1}}\geq 1/2$). Así, todos los términos con $j>\log _{p}(2n)$ son cero. Por lo tanto, eliminando del sumatorio todos estos últimos términos y usando que los $\log _{p}(2n)$ que quedan valen como mucho uno,

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

y, reordenando los términos,

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

Lema 3

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

Demostración: Usando las cotas y la imparidad de $p$, hay exactamente dos factores de $p$ en el numerador de la expresión ${\tbinom {2n}{n}}=(2n)!/(n!)^{2}$: procedentes de los dos términos $p$ y $2p$ en $(2n)!$; también hay dos factores de $p$ en el denominador: uno por cada expansión de $n!$. Los dos factores del numerador se cancelan con los denominador, por lo que en ${\tbinom {2n}{n}}$ no quedan ya factores de $p$. (Las cotas para $p$ en las hipótesis del lema aseguran que $3p$ es demasiado grande para ser un factor del numerador, y la hipótesis de que $p$ es impar es necesaria para garantizar que $2p$ aporta sólo un factor de $p$, y no dos, al numerador). $\quad \square$

Lema 4

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

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

donde, a diferencia del factorial, el producto se toma de todos los números primos $p$ menores o iguales a $n$.

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

Demostración: Procedemos por inducción fuerte sobre $n$.

Para $n=1,2$ tenemos $1\#=1<4$ y $2\#=2<4^{2}=16$, de manera que se cumple el enunciado para los casos base.

Demostremos que la desigualdad se cumple para números pares. Supongamos que la desigualdad se cumple para todos $1\leq n\leq 2k-1$. Como $n=2k>2$ es compuesto, tenemos que el productorio de la definición del primorial de $2k$ se toma sobre todos los primos menores que $2k$ distintos de $2k$ (que no es primo), es decir, es el mismo producto usado para calcular $(2k-1)\#$. Así pues, por hipótesis de inducción,

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

Para demostrarla para los números impares, supongamos ahora que la desigualdad se cumple para todos $1\leq n\leq 2k$. Por hipótesis de inducción, se tiene que $(k+1)\#\leq 4^{k+1}$. Por otro lado, observamos que todos los primos entre $k+2$ y $2k+1$ dividen al número binomial ${\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}$. Por tanto, su producto, $\prod _{k+2\leq p\leq 2k+1}p$ debe ser menor que el anterior coeficiente binomial. Juntando estas dos cosas tenemos

$n\#=\prod _{p\leq n}p=\prod _{p\leq k+1}p\prod _{k+2\leq p\leq 2k+1}p\leq 4^{k+1}{\binom {2k+1}{k}}$

Ahora, por las propiedades de los números binomiales $\sum _{i=0}^{2k+1}{\binom {2k+1}{i}}=2^{2k+1}$ y ${\binom {2k+1}{k}}={\binom {2k+1}{k+1}}$, tenemos que

${\binom {2k+1}{k}}={\frac {1}{2}}\left({\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right)\leq {\frac {1}{2}}\sum _{i=0}^{2k+1}{\binom {2k+1}{i}}=2^{2k}$

Juntando esta cota con la cota anterior, obtenemos que

$n\#\leq 4^{k+1}2^{2k}=4^{2k+1}=4^{n}$,

que es la cota que buscábamos. $\quad \square$

Demostración del postulado de Bertrand

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

Si 2 ≤ n < 427, entonces p puede elegirse entre los números primos 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (cada número de la lista es el mayor número primo entre el anterior de la lista y su doble) de forma que n < p < 2n. Por lo tanto, n ≥ 427. Es decir, hemos descartado por inspección directa que haya contraejemplos menores que 427.

Llegaremos a contradicción suponiendo que el contraejemplo es $n\geq 427$. En primer lugar, no existen factores primos p de $\textstyle {\binom {2n}{n}}={\frac {(2n)!}{n!(n+1)!}}$ en los siguientes intervalos:

• 2n < p, porque cada factor debe dividir al numerador (2n)! ;
• p = 2n, porque 2n no es primo;
• n < p < 2n, porque asumimos que no existe tal número primo (n es un contraejemplo al postulado);
• 2n / 3 < p ≤ n : por el lema 3.

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

Afirmamos que si $p>{\sqrt {2n}},$ el número $\textstyle {2n \choose n}$ tiene como máximo un factor de p. En efecto, por el lema 2, para cualquier primo p tenemos p^R(p,n) ≤ 2n. Si, como estamos suponiendo, $p>{\sqrt {2n}},$ necesariamente $R(p,n)\leq 1$, es decir, $\textstyle {2n \choose n}$ tiene como máximo un factor de p.

Ahora, comenzando con el lema 1, descomponiendo el lado derecho en sus factores primos (que hemos visto que están entre 2 y 2n/3, y que distinguimos según sean mayores que ${\sqrt {2n}}$ o no), usando el lema 2 para unos y el anterior párrafo para los otros, y finalmente usando lema 4, obtenemos que:

${\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)\leq \left(\,\prod _{p\,\leq \,{\sqrt {2n}}}\!\!2n\right)\!\!\left(\prod _{p\,\leq \,2n/3}\!\!p\right)\leq (2n)^{{\sqrt {2n}}-1}4^{2n/3}.$

Despejando,

$4^{n/3}\leq (2n)^{\sqrt {2n}}$, de donde

$2^{\sqrt {2n}}\leq (2n)^{3}.$

Tomando logaritmos y despejando obtenemos que necesariamente

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

Ahora es sencillo comprobar que esta desigualdad es falsa para cualquier supuesto contraejemplo $n\geq 427$, que es lo que estamos suponiendo. Una manera de hacerlo es observar que no se satisface para $n=427$ y, calculando las derivadas del lado izquierdo y el lado derecho, ver que para $n\geq 427$ el izquierdo crece más rápido, por lo que la desigualdad no puede ser nunca cierta. (Nótese que para $426$ la desigualdad sí que se satisface; hemos tenido que verificar esos primeros casos por inspección porque este mismo argumento no se sostendría si $n\not \geq 427$).

Así, hemos llegado a la conclusión de que no pueden existir contraejemplos al postulado de Bertrand: ni pequeños (menores a $427$), por inspección directa, ni grandes, por el argumento que acabamos de dar. Esto implica que el postulado es cierto. $\quad \square$

Bibliografía

• Aigner, Martin; Ziegler, Günter M. (2018). «Number Theory, 2. Bertrand's postulate». Proofs from THE BOOK (en inglés). Springer. pp. 9-11. ISBN 978-3-662-57264-1. 

Enlaces externos

• 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