Dimostrazione del postulato di Bertrand

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

In matematica, il postulato di Bertrand afferma che per ogni n ≥ 2 esiste un primo p tale che n < p < 2n. La prima dimostrazione fu data da Pafnuty Chebyshev; successivamente, anche Srinivasa Ramanujan e Paul Erdős ne fornirono una dimostrazione.

Questa sezione sull'argomento matematica è ancora vuota. Aiutaci a scriverla!

Se ${\displaystyle \{a_{n}\}_{n\in N^{+}}}$ è una successione di reali tali che ${\displaystyle a_{1}\geq a_{2}\geq a_{3}\geq ...\geq 0}$, allora

${\displaystyle \sum _{n=1}^{\infty }(-1)^{n-1}a_{n}=a_{1}-a_{2}+\sum _{n=2}^{\infty }\left(a_{2n-1}-a_{2n}\right)\geq a_{1}-a_{2}}$

e anche

${\displaystyle \sum _{n=1}^{\infty }(-1)^{n-1}a_{n}=a_{1}-a_{2}+a_{3}-\sum _{n=2}^{\infty }\left(a_{2n}-a_{2n+1}\right)\leq a_{1}-a_{2}+a_{3}}$

Siano

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

${\displaystyle \psi (x)=\sum _{n=1}^{\infty }\theta (x^{\frac {1}{n}})=\sum _{p^{a}\leq x}\ln p}$

dove ${\displaystyle p}$ è sempre un numero primo, ora

${\displaystyle \ln \lfloor x\rfloor !=\sum _{n\leq x}\ln n=\sum _{n\leq x}\sum _{p^{a}|n}\ln p=\sum _{m\leq x}\psi \left({\frac {x}{m}}\right)=\sum _{m=1}^{\infty }\psi \left({\frac {x}{m}}\right)}$

e noto (vedi approssimazione di Stirling) che

${\displaystyle x\ln x-x\leq \ln x!\leq x\ln x-x+\ln x}$

quindi

${\displaystyle \ln \lfloor x\rfloor !-2\ln \left\lfloor {\frac {x}{2}}\right\rfloor !=\sum _{n=1}^{\infty }(-1)^{n-1}\psi \left({\frac {x}{n}}\right)\leq x\ln 2+\ln x}$

e

${\displaystyle \ln \lfloor x\rfloor !-2\ln \left\lfloor {\frac {x}{2}}\right\rfloor !=\sum _{n=1}^{\infty }(-1)^{n-1}\psi \left({\frac {x}{n}}\right)\geq x\ln 2-\ln x+\ln 2}$

adesso in base a quanto scritto nei preliminari

${\displaystyle (1)}$ ${\displaystyle \psi (x)-\psi \left({\frac {x}{2}}\right)\leq x\ln 2+\ln x}$

${\displaystyle (2)}$ ${\displaystyle \psi (x)-\psi \left({\frac {x}{2}}\right)+\psi \left({\frac {x}{3}}\right)\geq x\ln 2-\ln x+\ln 2}$

dalla (1) si ricava

${\displaystyle \psi (x)=\sum _{n=0}^{\left\lfloor {\frac {\ln x}{\ln 2}}\right\rfloor }\left[\psi \left({\frac {x}{2^{n}}}\right)-\psi \left({\frac {x}{2^{n+1}}}\right)\right]\leq \sum _{n=0}^{\left\lfloor {\frac {\ln x}{\ln 2}}\right\rfloor }\left[{\frac {x}{2^{n}}}\ln 2+\ln {\frac {x}{2^{n}}}\right]\leq 2x\ln 2-\ln ^{2}x+\ln 2}$

e sostituendo nella (2) si ottiene

${\displaystyle (3)}$ ${\displaystyle \psi (x)-\psi \left({\frac {x}{2}}\right)\geq x\ln 2-\ln x+\ln 2-\psi \left({\frac {x}{3}}\right)\geq x\ln 2-\ln x+\ln 2-{\frac {2}{3}}x\ln 2-\ln ^{2}{\frac {x}{3}}\geq {\frac {1}{6}}x\ln 2}$

dove l'ultima disuguaglianza vale per tutte le ${\displaystyle x\geq 499}$.

ora

${\displaystyle \psi (x)-2\psi \left({\sqrt {x}}\right)=\sum _{n=1}^{\infty }(-1)^{n-1}\theta (x^{\frac {1}{n}})\leq \theta (x)}$

e sostituendo nella (3) tenendo conto che ${\displaystyle \theta (x)\leq \psi (x)}$

${\displaystyle \psi (x)-\psi \left({\frac {x}{2}}\right)\leq \theta (x)-\theta \left({\frac {x}{2}}\right)+2\psi \left({\sqrt {x}}\right)\leq \theta (x)-\theta \left({\frac {x}{2}}\right)+4{\sqrt {x}}\ln 2+{\frac {\ln ^{2}x}{2}}}$

${\displaystyle \theta (x)-\theta \left({\frac {x}{2}}\right)\geq \left[{\frac {x}{6}}-4{\sqrt {x}}\right]\ln 2-{\frac {\ln ^{2}x}{2}}}$

e infine

${\displaystyle \pi (x)-\pi \left({\frac {x}{2}}\right)\geq {\frac {\ln 2}{\ln x}}\left[{\frac {x}{6}}-4{\sqrt {x}}\right]-{\frac {\ln x}{2}}}$

il secondo membro per ${\displaystyle x\geq 938}$ è sempre maggiore di 1 e poiché il postulato di Bertrand è verificato per tutti gli ${\displaystyle x<938}$ la dimostrazione è conclusa.

Indichiamo l'insieme dei numeri primi con ${\displaystyle \mathbb {P} }$ e definiamo:

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

${\displaystyle \theta (n)<n\cdot \ln(4)\qquad {\mbox{per tutti gli interi }}n\geq 1}$

• n = 1:

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

• n = 2:

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

• n > 2 ed n è pari:

${\displaystyle \theta (n)=\theta (n-1)<(n-1)\cdot \ln(4)<n\cdot \ln(4)}$ (per induzione)

• n > 2 ed n è dispari. Sia n = 2m + 1 con 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}}$

Ogni primo p con ${\displaystyle m+1<p\leq 2m+1}$ divide ${\displaystyle {2m+1 \choose m}}$ dando:

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

Per ipotesi induttiva ${\displaystyle \theta (m+1)<(m+1)\cdot \ln 4}$, da cui segue:

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

CVD

Detto ciò possiamo passare alla dimostrazione del postulato di Bertrand. Supponiamo per assurdo che ci sia un controesempio: un intero n ≥ 2 tale che non ci sia nessun numero primo p tale che n < p < 2n.

Se 2 ≤ n < 2048, allora uno dei numeri primi 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 e 2503 (ognuno minore del doppio del precedente), che possiamo chiamare p, soddisferà n < p < 2n. Dunque n ≥ 2048.

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

Poiché ${\displaystyle {2n \choose n}}$ è il più grande termine nella somma, abbiamo:

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

Definiamo ${\displaystyle R(p,n)}$ come il più grande numero x, tale che ${\displaystyle p^{x}}$ divide ${\displaystyle {2n \choose n}}$. Poiché n! ha ${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$ fattori di p, otteniamo:

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

Dal momento che ogni termine ${\displaystyle \left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$ può essere o uguale a 0 ${\displaystyle ({\frac {n}{p^{j}}}<1/2)}$ oppure ad 1 ${\displaystyle ({\frac {n}{p^{j}}}\geq 1/2)}$ e tutti i termini con ${\displaystyle j>\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }$ sono 0, otteniamo:

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

Per ${\displaystyle p>{\sqrt {2n}}}$ abbiamo ${\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}}$ non ha fattori primi p tali che:

• 2n < p, poiché 2n è il fattore più grande.
• ${\displaystyle n<p\leq 2n}$, a causa della nostra assunzione iniziale.
• ${\displaystyle {\frac {2n}{3}}<p\leq n}$, perché ${\displaystyle p>{\sqrt {2n}}}$ (dato che ${\displaystyle n\geq 5}$) che implica ${\displaystyle R(p,n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor =2-2=0}$.

Ogni fattore primo di ${\displaystyle {2n \choose n}}$ è dunque minore o uguale a ${\displaystyle {\frac {2n}{3}}}$.

${\displaystyle {2n \choose n}}$ ha al massimo un fattore di ogni primo ${\displaystyle p>{\sqrt {2n}}}$. Poiché ${\displaystyle p^{R(p,n)}\leq 2n}$, il prodotto di ${\displaystyle p^{R(p,n)}}$ su tutti gli altri primi vale al massimo ${\displaystyle (2n)^{\sqrt {2n}}}$. Dal momento che ${\displaystyle {2n \choose n}}$ è il prodotto di ${\displaystyle p^{R(p,n)}}$ su tutti i primi p, otteniamo:

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

Usando il lemma ${\displaystyle \theta (n)<n\cdot \ln(4)}$:

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

Dato che abbiamo ${\displaystyle (2n+1)<(2n)^{2}}$:

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

Inoltre ${\displaystyle 2\leq {\frac {\sqrt {2n}}{3}}}$ (in quanto ${\displaystyle n\geq 18}$):

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

Passando ai logaritmi:

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

Sostituendo 2^2t al posto di 2n:

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

Questo implica t<6 e la contraddizione:

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

Dunque non è possibile nessun controesempio al postulato.

CVD

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica