Postulado de Bertrand y la función \pi(x)

La función $\pi(x)$ y los primos

La función contadora de primos $\pi(x)$ se define como el número de primos $p \le x$: $\pi(x) = \#\{p \le x : p \text{ primo}\}$. Por ejemplo, $\pi(10) = 4$ (los primos $2, 3, 5, 7$), $\pi(100) = 25$.

El Teorema de los Números Primos (TNP), demostrado independientemente por Hadamard y de la Vallée Poussin en 1896, establece que $\pi(x) \sim \frac{x}{\ln x}$, es decir, $\lim_{x\to\infty} \frac{\pi(x)}{x/\ln x} = 1$. Una forma más precisa es $\pi(x) \sim \text{li}(x) = \int_2^x \frac{dt}{\ln t}$.

Para olimpiadas no necesitamos el TNP completo. Lo que sí necesitamos es el Postulado de Bertrand: entre $n$ y $2n$ siempre hay un primo. Esta afirmación más modesta es suficiente para la mayoría de los problemas.

El Postulado de Bertrand: enunciado e historia

Postulado de Bertrand (Tchebychev, 1852). Para todo entero $n \ge 1$, existe un primo $p$ con $n < p \le 2n$.

Joseph Bertrand conjeturó este resultado en 1845 basándose en verificaciones computacionales. Pafnuty Tchebychev lo demostró en 1852 usando métodos analíticos. La demostración más elemental es la de Paul Erdős (1932), que usa el coeficiente binomial central $\binom{2n}{n}$.

El postulado es equivalente a decir que $\pi(2n) > \pi(n)$ para todo $n \ge 1$. Es una herramienta poderosa para garantizar la existencia de primos en intervalos, especialmente cuando se necesita un primo en un rango específico.

Demostración de Erdős: el coeficiente central

Paso 1. Estimamos $\binom{2n}{n}$. Como es el mayor de los $2n+1$ coeficientes de $(1+1)^{2n} = 2^{2n}$, tenemos $\binom{2n}{n} \ge \frac{4^n}{2n+1}$.

Paso 2. Cada primo $p \le 2n$ divide a $\binom{2n}{n}$ con cierta multiplicidad. La clave es que si $n < p \le 2n$, entonces $p$ divide exactamente una vez a $\binom{2n}{n}$ (pues $\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$ y $p$ aparece en el numerador pero no en el denominador).

Paso 3. Factorizamos $\binom{2n}{n} = \prod_{p \le 2n} p^{\nu_p(\binom{2n}{n})}$. Los primos $p \le \sqrt{2n}$ contribuyen a lo más con $p^{\log_{p}(2n)} = 2n$ cada uno. Los primos $\sqrt{2n} < p \le 2n/3$ contribuyen a lo más con $p^2$. Los primos en $(2n/3, n]$ no contribuyen a $\binom{2n}{n}$ (análisis de la fórmula de Kummer). Los primos en $(n, 2n]$ contribuyen exactamente $p$ al producto.

Paso 4. Si no hubiera primos en $(n, 2n]$, entonces $\binom{2n}{n} \le \prod_{p \le \sqrt{2n}} (2n) \cdot \prod_{\sqrt{2n} < p \le 2n/3} p^2 \le (2n)^{\pi(\sqrt{2n})} \cdot 4^{2n/3}$. Para $n$ suficientemente grande esto contradice la cota inferior $4^n/(2n+1)$, probando que debe existir un primo en $(n, 2n]$.

Consecuencias y variaciones del Postulado

Consecuencia 1. Para $n \ge 25$, hay un primo entre $n$ y $\frac{4n}{3}$ (resultado de Nagura, 1952). Esto refina el postulado para $n$ grandes.

Consecuencia 2. Para todo $k \ge 1$, hay infinitos primos $p$ tales que $(p+1)/2$ también es primo (esto son los primos de Sophie Germain, cuya infinitud es conjectural pero el Postulado de Bertrand garantiza al menos uno en cada intervalo doble).

Consecuencia 3. $p_{n+1} < 2p_n$ para todo $n \ge 1$, donde $p_n$ es el $n$-ésimo primo. Esto da una cota superior efectiva: $p_n < 2^n$.

Aplicación directa. Si queremos demostrar que existe un primo con cierta propiedad en un rango $[N, 2N]$, el postulado nos da al menos uno en ese rango, y a veces basta verificar que el único primo en ese rango tiene la propiedad deseada.

Estimaciones elementales de $\pi(x)$

El Postulado de Bertrand implica $\pi(2^k) \ge k$ para todo $k \ge 1$ (pues entre $2^{k-1}$ y $2^k$ hay siempre un primo), así $\pi(x) \ge \log_2(\log_2 x)$ para $x \ge 2$.

Una cota superior elemental: como $\binom{2n}{n} \ge \prod_{n < p \le 2n} p \ge (n+1)^{\pi(2n)-\pi(n)}$, y $\binom{2n}{n} \le 4^n$, obtenemos $\pi(2n) - \pi(n) \le \frac{n \ln 4}{\ln(n+1)}$. Sumando en potencias de 2: $\pi(x) = O(x/\ln x)$, que junto con la cota inferior del TNP da $\pi(x) \sim x/\ln x$.

Cota práctica para olimpiadas. $\pi(n) \ge \frac{n}{2 \ln n}$ para $n \ge 2$, y $p_k \le k(\ln k + \ln \ln k + 2)$ para $k \ge 6$ (Rosser y Schoenfeld). En problemas, suele bastar saber que hay "muchos" primos hasta $n$, más precisamente del orden de $n/\ln n$.

El Postulado de Bertrand en problemas de olimpiada

Estrategia de uso. El Postulado de Bertrand se aplica cuando: (1) hay que demostrar que existe un primo con cierta propiedad de rango; (2) se usa en inducción para avanzar de primos pequeños a primos en rangos mayores; (3) aparece la necesidad de un primo en un intervalo de la forma $(n, 2n]$.

Ejemplo (Cono Sur, estilo). Demuestra que para todo entero $n \ge 2$ existe un conjunto de $n$ enteros positivos cuyo mínimo común múltiplo es un número primo al cuadrado.

Solución por inducción usando Bertrand: para $n = 2$, tomamos $\{p^2, p\}$ para cualquier primo $p$: $\text{mcm}(p^2, p) = p^2$. Para el paso inductivo, si ya tenemos el conjunto $S$ de $n$ elementos con $\text{mcm} = q^2$, podemos añadir $q$ (que ya estaba en $S$) o... este problema requiere otra estrategia, pero el postulado garantiza la existencia de primos auxiliares.