Postulat de Bertrand

De Viquipèdia

En matemàtiques, el postulat de Bertrand, anomenat també teorema de Tchebychev, afirma que si $n$ és un nombre natural superior o igual a 1, llavors sempre existeix pel capbaix un nombre primer $p$ tal que

n < p < 2 n

Tot i que ha estat demostrat, per tant és un teorema, manté el nom original de postulat, es a dir conjectura.

[edita] Història

Aquesta afirmació va ser conjecturada per primera vegada el 1845 per Joseph Bertrand que la va verificar ell mateix per a tots els nombres de l'interval $[2 ; 3 \times 10^6]$ . La conjectura va ser completament demostrada el 1850 per Pafnouti Tchebychev, que va utilitzar en la seva demostració la fórmula de Stirling. Ramanujan va donar una demostració més senzilla i Paul Erdős el 1932 va publicar una prova molt senzilla en la qual va utilitzar els coeficients binomials i la funció $θ$ , definida per:

$\theta(x) = \sum_{p=2}^{x} \ln (p)$

on $p$ recorre els nombres primers inferiors o iguals a $x$ .

[edita] Teorema de Sylvester

El postulat de Bertrand va ser avançat en vista d'aplicacions al grup de les permutacions. James Joseph Sylvester el va generalitzar amb la proposició següent: el producte de $k$ enters consecutius superiors a $k$ és divisible per un nombre primer més gran que $k$ .

Una conjectura similar, anomenada conjectura de Legendre, però encara no demostrada afirma l'existència d'un nombre primer $p$ . tal que $n 2 < p < (n + 1) 2$ . < (no + 1)2. Fa referència a la hipòtesi de Riemann.

[edita] Demostració

S'escriurà $\Bbb{P}$ el conjunt dels nombres primers i es defineix:

$\theta(x) = \sum_{p\in\Bbb{P};\, p\leq x} \ln (p)$

Heus ací l'estratègia per a la demostració:

Obtenció d'una majorant de $θ(x)$
Verificació explícita de la propietat per a $n < 2048$
Demostració de la propietat per a $n > 2048$
Conclusió.

[edita] Lema

Per a tots els enters $n\ge 1$ :

$\theta(n) < n \cdot \ln(4)$

Demostració

n = 1:

$\theta(1)= 0 < 1 \cdot \ln(4)$

n = 2:

$\theta(2)=\ln(2) < 2 \cdot \ln(4)$

n > 2 i n és parell :

$\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)$ (per inducció)

(com que, tret del dos, cap nombre parell és primer, hi ha tants nombres primers entre 1 i n com entre 1 i n-1 )

$n > 2$ i n és senar. Sia n = 2m+1 amb m > 0:

$4^m = \frac {(1+1)^{2m+1}}{2} = \frac {\sum_{k=0}^{2m+1}{2m+1 \choose k}} {2} = \frac {x+{2m+1 \choose m}+{2m+1 \choose m+1}}{2} \ge {2m+1 \choose m}$

Cada nombre primer p amb $m+1 < p \le 2m+1$ és un divisor de ${2m+1 \choose m}$ el que dona:

$\theta(2m+1) - \theta(m+1) \le \ln({2m+1 \choose m}) \le \ln(4^m) = m \cdot \ln(4)$

Per inducció $\theta(m+1) < (m+1) \cdot \ln 4$ , car :

$\theta(n) = \theta(2m+1) < (2m+1) \cdot \ln(4) = n \cdot \ln(4)$

Q.E.D.

Ara, ja es pot encarar la demostració del postulat de Bertrand.

Suposant que existeix un contra exemple: un enter n ≥ 2 tal que no existeix cap nombre primer p amb n < p < 2n.

[edita] Cas on n < 2048

Si 2 ≤ n < 2048, llavors un dels nombres primers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 i 2503 (cadascun sent inferior del doble del seu predecessor), que s'anomenaran p, hauria de satisfer n < p < 2n. Ara bé es comprova que no és el cas. Per tant n ≥ 2048.

[edita] Cas on n > 2048

Per la fórmula del binomi de Newton,

$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k}$

Com que ${2n \choose n}$ és el terme més gran de la suma, es té:

$\frac {4^n} {2n+1} \le {2n \choose n}$

Anomenant $R (p, n)$ el nombre més gran x tal que $p x$ és divisor de ${2n \choose n}$ .

Com que n! té $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$ factors de p s'obté:

$R(p,n)=\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 \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$

Com que cada terme $\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$ val o bé 0 (quan $\frac {n} {p^j} < \frac{1}{2}$ ) o bé 1 (quan $\frac {n} {p^j} \ge \frac{1}{2}$ ) i com que tots els termes amb $j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$ són nuls, s'obté:

$R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

Per a $p > \sqrt{2n}$ es té $\left \lfloor \frac {\ln (2n)} {\ln(p)} \right \rfloor \le 1$ où $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor$ .

${2n \choose n}$ no té pas cap factor primer p tal que:

2n < p, ja que 2n és el factor més gran;
$n<p \le 2n$ , per un desenvolupament trivial de l'afirmació original (hipòtesis que es vol contradir);
$\frac {2n} {3} <p \le n$ , ja que $p > \sqrt{2n}$ (ja que $n \ge 5$ ) que dona $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0$ .

Per tant, factor primer de ${2n \choose n}$ no és pas més gran que $\frac {2n} {3}$ .

${2n \choose n}$ poseeix com a màxim un factor de cada nombre primer $p > \sqrt{2n}$ . Com que $p^{R(p,n)} \le 2n$ , el producte de $p R (p, n)$ per a tots els altres nombres primers és com a màxim $(2n)^{\sqrt{2n}}$ . Ja que ${2n \choose n}$ és el producte de $p R (p, n)$ per tots els nombres primers p, s'obté:

$\frac {4^n}{2n+1} \le {2n \choose n} \le (2n)^{\sqrt{2n}} \prod_{p \in \mathbb{P} }^{\frac {2n} {3}} p = (2n)^{\sqrt{2n}} e^{\theta(\frac {2n} {3})}$