Dimostrazione del postulato di Bertrand

Template:F 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\ge a_2\ge a_3\ge ...\ge 0$, allora

$\sum _{n=1}^{\mathrm{\infty }}(-1{)}^{n-1}{a}_n=a_1-a_2+\sum _{n=2}^{\mathrm{\infty }}(a_{2n-1}-a_{2n})\ge a_1-a_2$

e anche

$\sum _{n=1}^{\mathrm{\infty }}(-1{)}^{n-1}{a}_n=a_1-a_2+a_3-\sum _{n=2}^{\mathrm{\infty }}(a_{2n}-a_{2n+1})\le a_1-a_2+a_3$

Dimostrazione

Siano

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

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

dove $p$ è sempre un numero primo, ora

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

e noto (vedi approssimazione di Stirling) che

$x\ln x-x\le \ln x!\le x\ln x-x+\ln x$

quindi

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

e

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

adesso in base a quanto scritto nei preliminari

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

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

dalla (1) si ricava

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

e sostituendo nella (2) si ottiene

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

dove l'ultima disuguaglianza vale per tutte le $x\ge 499$.

ora

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

e sostituendo nella (3) tenendo conto che $\theta (x)\le \psi (x)$

$\psi (x)-\psi \left(\frac{x}{2}\right)\le \theta (x)-\theta \left(\frac{x}{2}\right)+2\psi \left(\sqrt{x}\right)\le \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)\ge [\frac{x}{6}-4\sqrt{x}]\ln 2-\frac{{\ln }^{2}x}{2}$

e infine

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

il secondo membro per $x\ge 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\le x}\ln (p)$

Lemma

$\theta (n)<n\cdot \ln (4)\text{per tutti gli interi }n\ge 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}(\genfrac{}{}{0ex}{}{2m+1}{k})}{2}=\frac{x+(\genfrac{}{}{0ex}{}{2m+1}{m})+(\genfrac{}{}{0ex}{}{2m+1}{m+1})}{2}\ge (\genfrac{}{}{0ex}{}{2m+1}{m})$

Ogni primo p con $m+1<p\le 2m+1$ divide $(\genfrac{}{}{0ex}{}{2m+1}{m})$ dando:

$\theta (2m+1)-\theta (m+1)\le \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}(\genfrac{}{}{0ex}{}{2n}{k})$

Poiché $(\genfrac{}{}{0ex}{}{2n}{n})$ è il più grande termine nella somma, abbiamo:

$\frac{4^n}{2n+1}\le (\genfrac{}{}{0ex}{}{2n}{n})$

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

$R(p,n)=\sum _{j=1}^{\mathrm{\infty }}\lfloor \frac{2n}{p^j}\rfloor -2\sum _{j=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^j}\rfloor =\sum _{j=1}^{\mathrm{\infty }}\lfloor \frac{2n}{p^j}\rfloor -2\lfloor \frac{n}{p^j}\rfloor$

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

$R(p,n)\le \lfloor \frac{\ln (2n)}{\ln (p)}\rfloor$

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

$(\genfrac{}{}{0ex}{}{2n}{n})$ non ha fattori primi p tali che:

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

Ogni fattore primo di $(\genfrac{}{}{0ex}{}{2n}{n})$ è dunque minore o uguale a $\frac{2n}{3}$.

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

$\frac{4^n}{2n+1}\le (\genfrac{}{}{0ex}{}{2n}{n})\le (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}\le (2n{)}^{\sqrt{2n}}{4}^{\frac{2n}{3}}$

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

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

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

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

Passando ai logaritmi:

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

Sostituendo 2^2t al posto di 2n:

$\frac{2^t}{t}\le 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