Postulat de Bertrand

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

${\displaystyle n<p<2n}$

Tot i que ha estat demostrat, per tant és un teorema, manté el nom original de postulat, és 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 ${\displaystyle [2;3\times 10^{6}]}$. La conjectura va ser completament demostrada el 1850 per Pafnuti Txebixov, 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ó ${\displaystyle \theta }$, definida per:

${\displaystyle \theta (x)=\sum _{p=2}^{x}\ln(p)}$

on ${\displaystyle p}$ recorre els nombres primers inferiors o iguals a ${\displaystyle x}$.

Teorema de Sylvester

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

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

Demostració

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

${\displaystyle \theta (x)=\sum _{p\in \mathbb {P} ;\,p\leq x}\ln(p)}$

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

• Obtenció d'una majorant de ${\displaystyle \theta (x)}$
• Verificació explícita de la propietat per a ${\displaystyle n<2048}$
• Demostració de la propietat per a ${\displaystyle n>2048}$
• Conclusió.

Lema

Per a tots els enters ${\displaystyle n\geq 1}$:

${\displaystyle \theta (n)<n\cdot \ln(4)}$

Demostració

• n = 1:

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

• n = 2:

${\displaystyle \theta (2)=\ln(2)<2\cdot \ln(4)}$

• n > 2 i n és parell :

${\displaystyle \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)

• ${\displaystyle n>2}$ i n és senar. Sia n = 2m+1 amb m > 0:

${\displaystyle 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}}\geq {2m+1 \choose m}}$

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

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

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

${\displaystyle \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 contraexemple: 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,

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

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

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

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

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

${\displaystyle 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 ${\displaystyle \left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$ val o bé 0 (quan ${\displaystyle {\frac {n}{p^{j}}}<{\frac {1}{2}}}$) o bé 1 (quan ${\displaystyle {\frac {n}{p^{j}}}\geq {\frac {1}{2}}}$) i com que tots els termes amb ${\displaystyle j>\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }$ són nuls, s'obté:

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

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

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

• 2n < p, ja que 2n és el factor més gran;
• ${\displaystyle n<p\leq 2n}$, per un desenvolupament trivial de l'afirmació original (hipòtesi que es vol contradir);
• ${\displaystyle {\frac {2n}{3}}<p\leq n}$, ja que ${\displaystyle p>{\sqrt {2n}}}$ (ja que ${\displaystyle n\geq 5}$) que dona ${\displaystyle 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 ${\displaystyle {2n \choose n}}$ no és pas més gran que ${\displaystyle {\frac {2n}{3}}}$.

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

${\displaystyle {\frac {4^{n}}{2n+1}}\leq {2n \choose n}\leq (2n)^{\sqrt {2n}}\prod _{p\in \mathbb {P} }^{\frac {2n}{3}}p=(2n)^{\sqrt {2n}}e^{\theta ({\frac {2n}{3}})}}$

Utilitzant el lemma ${\displaystyle \theta (n)<n\cdot \ln(4)}$:

${\displaystyle {\frac {4^{n}}{2n+1}}\leq (2n)^{\sqrt {2n}}4^{\frac {2n}{3}}}$

Ja que es té ${\displaystyle (2n+1)<(2n)^{2}}$:

${\displaystyle 4^{\frac {n}{3}}\leq (2n)^{2+{\sqrt {2n}}}}$

I també ${\displaystyle 2\leq {\frac {\sqrt {2n}}{3}}}$ (ja que ${\displaystyle n\geq 18}$):

${\displaystyle 4^{\frac {n}{3}}\leq (2n)^{{\frac {4}{3}}{\sqrt {2n}}}}$

Prenent logaritmes:

${\displaystyle {\sqrt {2n}}\ln(2)\leq 4\cdot \ln(2n)}$

Substituint 2^2t per 2n:

${\displaystyle {\frac {2^{t}}{t}}\leq 8}$

Això dona t < 6 i la contradicció:

${\displaystyle n={\frac {2^{2t}}{2}}<{\frac {2^{2\cdot 6}}{2}}=2048}$

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 Arxivat 2006-08-04 a Wayback Machine. − Demostració del teorema (pdf). (anglès) .