Fotografia de Joseph Louis François Bertrand , que donà nom al postulat.
En matemàtiques , el postulat de Bertrand , anomenat també teorema de Tchebychev , afirma que si
n
{\displaystyle n}
és un nombre natural superior o igual a 1, llavors sempre existeix pel capbaix un nombre primer
p
{\displaystyle p}
tal que
n
<
p
<
2
n
{\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
[
2
;
3
×
10
6
]
{\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:
θ
(
x
)
=
∑
p
=
2
x
ln
(
p
)
{\displaystyle \theta (x)=\sum _{p=2}^{x}\ln(p)}
on
p
{\displaystyle p}
recorre els nombres primers inferiors o iguals a
x
{\displaystyle x}
.
Teorema de Sylvester [ modifica ]
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
k
{\displaystyle k}
enters consecutius superiors a
k
{\displaystyle k}
és divisible per un nombre primer més gran que
k
{\displaystyle k}
.
Una conjectura similar, anomenada conjectura de Legendre , i encara no demostrada, afirma l'existència d'un nombre primer
p
{\displaystyle p}
tal que
n
2
<
p
<
(
n
+
1
)
2
{\displaystyle n^{2}<p<(n+1)^{2}}
. < (no + 1)2. Fa referència a la hipòtesi de Riemann .
S'escriurà
P
{\displaystyle \mathbb {P} }
el conjunt dels nombres primers i es defineix:
θ
(
x
)
=
∑
p
∈
P
;
p
≤
x
ln
(
p
)
{\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
θ
(
x
)
{\displaystyle \theta (x)}
Verificació explícita de la propietat per a
n
<
2048
{\displaystyle n<2048}
Demostració de la propietat per a
n
>
2048
{\displaystyle n>2048}
Conclusió.
Per a tots els enters
n
≥
1
{\displaystyle n\geq 1}
:
θ
(
n
)
<
n
⋅
ln
(
4
)
{\displaystyle \theta (n)<n\cdot \ln(4)}
Demostració
θ
(
1
)
=
0
<
1
⋅
ln
(
4
)
{\displaystyle \theta (1)=0<1\cdot \ln(4)}
θ
(
2
)
=
ln
(
2
)
<
2
⋅
ln
(
4
)
{\displaystyle \theta (2)=\ln(2)<2\cdot \ln(4)}
θ
(
n
)
=
θ
(
n
−
1
)
<
(
n
−
1
)
⋅
ln
(
4
)
<
n
⋅
ln
(
4
)
{\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 )
n
>
2
{\displaystyle n>2}
i n és senar . Sia n = 2m +1 amb m > 0:
4
m
=
(
1
+
1
)
2
m
+
1
2
=
∑
k
=
0
2
m
+
1
(
2
m
+
1
k
)
2
=
x
+
(
2
m
+
1
m
)
+
(
2
m
+
1
m
+
1
)
2
≥
(
2
m
+
1
m
)
{\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
m
+
1
<
p
≤
2
m
+
1
{\displaystyle m+1<p\leq 2m+1}
és un divisor de
(
2
m
+
1
m
)
{\displaystyle {2m+1 \choose m}}
el que dona:
θ
(
2
m
+
1
)
−
θ
(
m
+
1
)
≤
ln
(
(
2
m
+
1
m
)
)
≤
ln
(
4
m
)
=
m
⋅
ln
(
4
)
{\displaystyle \theta (2m+1)-\theta (m+1)\leq \ln({2m+1 \choose m})\leq \ln(4^{m})=m\cdot \ln(4)}
Per inducció
θ
(
m
+
1
)
<
(
m
+
1
)
⋅
ln
4
{\displaystyle \theta (m+1)<(m+1)\cdot \ln 4}
, car :
θ
(
n
)
=
θ
(
2
m
+
1
)
<
(
2
m
+
1
)
⋅
ln
(
4
)
=
n
⋅
ln
(
4
)
{\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 [ modifica ]
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 [ modifica ]
Per la fórmula del binomi de Newton ,
4
n
=
(
1
+
1
)
2
n
=
∑
k
=
0
2
n
(
2
n
k
)
{\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}}
Com que
(
2
n
n
)
{\displaystyle {2n \choose n}}
és el terme més gran de la suma , es té:
4
n
2
n
+
1
≤
(
2
n
n
)
{\displaystyle {\frac {4^{n}}{2n+1}}\leq {2n \choose n}}
Anomenant
R
(
p
,
n
)
{\displaystyle R(p,n)}
el nombre més gran x tal que
p
x
{\displaystyle p^{x}}
és divisor de
(
2
n
n
)
{\displaystyle {2n \choose n}}
.
Com que n ! té
∑
j
=
1
∞
⌊
n
p
j
⌋
{\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }
factors de p s'obté:
R
(
p
,
n
)
=
∑
j
=
1
∞
⌊
2
n
p
j
⌋
−
2
∑
j
=
1
∞
⌊
n
p
j
⌋
=
∑
j
=
1
∞
⌊
2
n
p
j
⌋
−
2
⌊
n
p
j
⌋
{\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
⌊
2
n
p
j
⌋
−
2
⌊
n
p
j
⌋
{\displaystyle \left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }
val o bé 0 (quan
n
p
j
<
1
2
{\displaystyle {\frac {n}{p^{j}}}<{\frac {1}{2}}}
) o bé 1 (quan
n
p
j
≥
1
2
{\displaystyle {\frac {n}{p^{j}}}\geq {\frac {1}{2}}}
) i com que tots els termes amb
j
>
⌊
ln
(
2
n
)
ln
(
p
)
⌋
{\displaystyle j>\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }
són nuls, s'obté:
R
(
p
,
n
)
≤
⌊
ln
(
2
n
)
ln
(
p
)
⌋
{\displaystyle R(p,n)\leq \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }
Per a
p
>
2
n
{\displaystyle p>{\sqrt {2n}}}
es té
⌊
ln
(
2
n
)
ln
(
p
)
⌋
≤
1
{\displaystyle \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \leq 1}
où
R
(
p
,
n
)
=
⌊
2
n
p
⌋
−
2
⌊
n
p
⌋
{\displaystyle R(p,n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor }
.
(
2
n
n
)
{\displaystyle {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
≤
2
n
{\displaystyle n<p\leq 2n}
, per un desenvolupament trivial de l'afirmació original (hipòtesi que es vol contradir);
2
n
3
<
p
≤
n
{\displaystyle {\frac {2n}{3}}<p\leq n}
, ja que
p
>
2
n
{\displaystyle p>{\sqrt {2n}}}
(ja que
n
≥
5
{\displaystyle n\geq 5}
) que dona
R
(
p
,
n
)
=
⌊
2
n
p
⌋
−
2
⌊
n
p
⌋
=
2
−
2
=
0
{\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
(
2
n
n
)
{\displaystyle {2n \choose n}}
no és pas més gran que
2
n
3
{\displaystyle {\frac {2n}{3}}}
.
(
2
n
n
)
{\displaystyle {2n \choose n}}
posseeix com a màxim un factor de cada nombre primer
p
>
2
n
{\displaystyle p>{\sqrt {2n}}}
. Com que
p
R
(
p
,
n
)
≤
2
n
{\displaystyle p^{R(p,n)}\leq 2n}
, el producte de
p
R
(
p
,
n
)
{\displaystyle p^{R(p,n)}}
per a tots els altres nombres primers és com a màxim
(
2
n
)
2
n
{\displaystyle (2n)^{\sqrt {2n}}}
. Ja que
(
2
n
n
)
{\displaystyle {2n \choose n}}
és el producte de
p
R
(
p
,
n
)
{\displaystyle p^{R(p,n)}}
per tots els nombres primers p , s'obté:
4
n
2
n
+
1
≤
(
2
n
n
)
≤
(
2
n
)
2
n
∏
p
∈
P
2
n
3
p
=
(
2
n
)
2
n
e
θ
(
2
n
3
)
{\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
θ
(
n
)
<
n
⋅
ln
(
4
)
{\displaystyle \theta (n)<n\cdot \ln(4)}
:
4
n
2
n
+
1
≤
(
2
n
)
2
n
4
2
n
3
{\displaystyle {\frac {4^{n}}{2n+1}}\leq (2n)^{\sqrt {2n}}4^{\frac {2n}{3}}}
Ja que es té
(
2
n
+
1
)
<
(
2
n
)
2
{\displaystyle (2n+1)<(2n)^{2}}
:
4
n
3
≤
(
2
n
)
2
+
2
n
{\displaystyle 4^{\frac {n}{3}}\leq (2n)^{2+{\sqrt {2n}}}}
I també
2
≤
2
n
3
{\displaystyle 2\leq {\frac {\sqrt {2n}}{3}}}
(ja que
n
≥
18
{\displaystyle n\geq 18}
):
4
n
3
≤
(
2
n
)
4
3
2
n
{\displaystyle 4^{\frac {n}{3}}\leq (2n)^{{\frac {4}{3}}{\sqrt {2n}}}}
Prenent logaritmes :
2
n
ln
(
2
)
≤
4
⋅
ln
(
2
n
)
{\displaystyle {\sqrt {2n}}\ln(2)\leq 4\cdot \ln(2n)}
Substituint 22t per 2n :
2
t
t
≤
8
{\displaystyle {\frac {2^{t}}{t}}\leq 8}
Això dona t < 6 i la contradicció:
n
=
2
2
t
2
<
2
2
⋅
6
2
=
2048
{\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.
Enllaços externs [ modifica ]