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.

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

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.

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ó.

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.

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.

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

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

Q.E.D.

• 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) .