Dimostrazione del postulato di Bertrand

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.

Dimostrazione di Srinivasa Ramanujan

Preliminari

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

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

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

Dimostrazione

Siano

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

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

dove $p$ è sempre un numero primo, ora

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

$x\ln x-x\leq \ln x!\leq x\ln x-x+\ln x$

quindi

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

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

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

$(2)$ $\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

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

$(3)$ $\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 $x\geq 499$.

ora

$\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 $\theta (x)\leq \psi (x)$

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

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

$\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 $x\geq 938$ è sempre maggiore di 1 e poiché il postulato di Bertrand è verificato per tutti gli $x<938$ la dimostrazione è conclusa.

Dimostrazione di Paul Erdős

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

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

Lemma

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

Dimostrazione

• n = 1:

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

• n = 2:

$\theta (2)=\ln(2)<2\cdot \ln(4)$

• n > 2 ed n è pari:

$\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:

$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 $m+1<p\leq 2m+1$ divide ${2m+1 \choose m}$ dando:

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

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

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

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

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

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

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

$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 $\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor$ può essere o uguale a 0 $({\frac {n}{p^{j}}}<1/2)$ oppure ad 1 $({\frac {n}{p^{j}}}\geq 1/2)$ e tutti i termini con $j>\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor$ sono 0, otteniamo:

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

Per $p>{\sqrt {2n}}$ abbiamo $\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \leq 1$ o $R(p,n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor$.

${2n \choose n}$ non ha fattori primi p tali che:

• 2n < p, poiché 2n è il fattore più grande.
• $n<p\leq 2n$, a causa della nostra assunzione iniziale.
• ${\frac {2n}{3}}<p\leq n$, perché $p>{\sqrt {2n}}$ (dato che $n\geq 5$) che implica $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 ${2n \choose n}$ è dunque minore o uguale a ${\frac {2n}{3}}$.

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

${\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 $\theta (n)<n\cdot \ln(4)$:

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

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

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

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

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

Passando ai logaritmi:

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

Sostituendo 2^2t al posto di 2n:

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

Questo implica t<6 e la contraddizione:

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

Dunque non è possibile nessun controesempio al postulato.

CVD