Postulat de Bertrand

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

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

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 <math>[2 ; 3 \times 10^6]</math>. 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ó <math>\theta</math>, definida per:

<math> \theta(x) = \sum_{p=2}^{x} \ln (p) </math>

on <math>p</math> recorre els nombres primers inferiors o iguals a <math>x</math>.

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 <math>k</math> enters consecutius superiors a <math>k</math> és divisible per un nombre primer més gran que <math>k</math>.

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

Demostració

S'escriurà <math>\Bbb{P}</math> el conjunt dels nombres primers i es defineix:

<math> \theta(x) = \sum_{p\in\Bbb{P};\, p\leq x} \ln (p) </math>

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

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

Lema

Per a tots els enters <math>n\ge 1</math>:

<math> \theta(n) < n \cdot \ln(4)</math>

Demostració

n = 1:

<math> \theta(1)= 0 < 1 \cdot \ln(4) </math>

n = 2:

<math> \theta(2)=\ln(2) < 2 \cdot \ln(4) </math>

n > 2 i n és parell :

<math> \theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4) </math> (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 )

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

<math> 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} </math>

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

<math> \theta(2m+1) - \theta(m+1) \le \ln({2m+1 \choose m}) \le \ln(4^m) = m \cdot \ln(4) </math>

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

<math> \theta(n) = \theta(2m+1) < (2m+1) \cdot \ln(4) = n \cdot \ln(4) </math>

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.

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.

Cas on n > 2048

Per la fórmula del binomi de Newton,

<math> 4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k} </math>

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

<math> \frac {4^n} {2n+1} \le {2n \choose n} </math>

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

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

<math> 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 </math>

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

<math> R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math>

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

<math> {2n \choose n} </math> no té pas cap factor primer p tal que:

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

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

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

<math> \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})} </math>

Utilitzant el lemma <math> \theta(n) < n \cdot \ln(4) </math>:

Ja que es té <math> (2n+1) < (2n)^2 </math>:

I també <math> 2 \le \frac {\sqrt{2n}}{3} </math> (ja que <math> n \ge 18 </math>):

Prenent logaritmes:

Substituint 2^2t per 2n:

Això dona t < 6 i la contradicció:

Conclusió

Per tant, cap contraexemple per al postulat no és pas possible.

Q.E.D.

Enllaços externs

Postulat de Bertrand − La pàgina de MathWorld sobre el postulat de Bertrand. (anglès)
Postulat de Bertrand − Demostració del teorema (pdf). (anglès) .