Postulat de Bertrand

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, le postulat de Bertrand, aussi appelé théorème de Tchebychev, affirme que si $n$ est un entier naturel supérieur ou égal à 1, alors il existe toujours au moins un nombre premier $p$ tel que

n < p < 2 n

Bien que démontré, il a gardé son nom de postulat, c'est-à-dire une conjecture.

[modifier] Historique

Cette affirmation fut pour la première fois conjecturée en 1845 par Joseph Bertrand qui la vérifia lui-même pour tous les nombres de l'intervalle $[2 ; 3 \times 10^6]$ . La conjecture fut complètement démontrée en 1850 par Pafnouti Tchebychev, qui utilisa dans sa démonstration la formule de Stirling.

Ramanujan donna une démonstration plus simple et Paul Erdős en 1932 publia une preuve très simple dans laquelle il utilisa les coefficients binomiaux et la fonction $θ$ , définie par:

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

où $p$ parcourt les nombres premiers inférieurs ou égaux à $x$ .

[modifier] Théorème de Sylvester

Le postulat de Bertrand fut avancé en vue d'applications au groupe des permutations. James Joseph Sylvester le généralisa avec la proposition suivante : le produit de $k$ entiers consécutifs supérieurs à $k$ est divisible par un nombre premier plus grand que $k$ .

Une conjecture similaire, appelée conjecture de Legendre, mais non encore résolue affirme l'existence d'un nombre premier $p$ tel que $n 2 < p < (n + 1) 2$ . Elle touche à l'hypothèse de Riemann.

[modifier] Démonstration

Nous noterons l'ensemble des nombres premiers $\Bbb{P}$ et définissons :

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

Voici le plan de la démonstration:

Majoration de $θ(x)$
Vérification explicite de la propriété pour $n < 2048$
Démonstration de la propriété pour $n > 2048$
Conclusion.

[modifier] Lemme

pour tous les entiers $n\ge 1$ :

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

Démonstration

n = 1:

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

n = 2:

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

n > 2 et n est pair :

$\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)$ (par induction)

(parce que chaque nombre pair n'est pas premier, donc il y a autant de nombres premiers entre 1 et n qu'avec 1 et n-1 )

$n > 2$ et n est impair. Soit n = 2m+1 avec 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}$

Chaque nombre premier p avec $m+1 < p \le 2m+1$ divise ${2m+1 \choose m}$ ce qui nous donne :

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

Par induction $\theta(m+1) < (m+1) \cdot \ln 4$ , donc :

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

CQFD

Maintenant, pour la démonstration du postulat de Bertrand.

Supposons qu'il existe un contre-exemple : un entier n ≥ 2 tel qu'il n'existe pas de nombre premier p avec n < p < 2n.

[modifier] Cas où n < 2048

Si 2 ≤ n < 2048, alors un des nombres premiers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 et 2503 (chacun étant inférieur du double de son prédécesseur), que nous nommerons p, devrait satisfaire n < p < 2n. Or on constate que ce n'est pas le cas. Par conséquent n ≥ 2048.

[modifier] Cas où n > 2048

Par la formule de binôme de Newton,

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

Puisque ${2n \choose n}$ est le plus grand terme de la somme, nous avons :

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

Appelons $R (p, n)$ le plus grand nombre x tel que $p x$ divise ${2n \choose n}$ .

Puisque n! possède $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$ facteurs de p nous obtenons :

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

Puisque chaque terme $\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$ vaut soit 0 (lorsque $\frac {n} {p^j} < \frac{1}{2}$ ) soit 1 (lorsque $\frac {n} {p^j} \ge \frac{1}{2}$ ) et que tous les termes avec $j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$ sont nuls, nous obtenons :

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

Pour $p > \sqrt{2n}$ nous avons $\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}$ n'a pas de facteur premier p tel que :

2n < p, car 2n est le facteur le plus grand;
$n<p \le 2n$ , à cause d'un développement trivial de l'assertion originale (hypothèse que nous cherchons à contredire);
$\frac {2n} {3} <p \le n$ , car $p > \sqrt{2n}$ (puisque $n \ge 5$ ) qui nous donne $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0$ .

Aucun facteur premier de ${2n \choose n}$ n'est donc plus grand que $\frac {2n} {3}$ .

${2n \choose n}$ possède au plus un facteur de chaque nombre premier $p > \sqrt{2n}$ . Comme $p^{R(p,n)} \le 2n$ , le produit de $p R (p, n)$ pour tous les autres nombres premiers est au plus $(2n)^{\sqrt{2n}}$ . Puisque ${2n \choose n}$ est le produit de $p R (p, n)$ pour tous les nombres premiers p, nous obtenons :

$\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})}$