Bertrands postulat

Bertrand-postulatet , Bertrand-Chebyshev- satsen eller Chebyshev-satsen säger att

För alla naturliga tal n ⩾ 2 finns ett primtal p i intervallet n < p < 2 n .

Bertrands postulat formulerades som en hypotes 1845 av den franske matematikern Bertrand (som testade det upp till n = 3 000 000 ) och bevisades 1852 [1] av Chebyshev . Ramanujan hittade ett enklare bevis 1919 och bevisade att antalet primtal i intervallet n < p < 2 n kan begränsas underifrån av en icke-minskande sekvens som tenderar till oändlighet, så att likhet uppnås i Ramanujans primtal . Erdős 1932 förenklade beviset ytterligare .

Generaliseringar

En generalisering av Bertrands postulat kan betraktas som satsen att det bland tal alltid finns ett tal med en primtal divisor större än . Detta uttalande bevisades av Sylvester 1892. För , det ger Bertrands gissning som ett specialfall. $n\geqslant 2k$ $n-k+1, \dots, n-1, n$ $k$ $n=2k$

Av satsen om fördelningen av primtal följer att det för alla finns ett tal så att det för alla finns ett primtal som uppfyller . Dessutom, för ett fast antal primtal i detta intervall tenderar att vara oändligt med tillväxt [2] . I synnerhet, till exempel, för alltid finns det ett primtal mellan och [3] . $\varepsilon >0$ $n_{0}$ $n\geqslant n_{0}$ $sid$ $n<p<(1+\varepsilon )n$ $\varepsilon$ $n$ $n\geqslant 25$ $n$ $(1+1/5)n$

Hypoteser

Legendres gissningar säger att det för alla finns ett primtal i intervallet . Oppermans gissning och Andritz gissning ger samma tillväxtordning för ett intervall som innehåller minst ett primtal. $n \geqslant 2$ $sid$ $n^{2}<p<(n+1)^{2}$

Den starkaste är Cramers gissning , som säger att

p_{n+1}-p_{n}=O(\ln ^{2}p_{n}).

Alla dessa hypoteser har inte bevisats eller vederlagts.

Bevis

Bevis på Bertrands postulat

Här presenterar vi det bevis som Erdős föreslagit .

Notation och definitioner

I beviset använder vi följande notation:

${a\välj b}$ är den binomiska koefficienten eller antalet kombinationer från med . $a$ $b$
$\vänster \lgolv x \höger \rgolv$ är hela delen . $x$

Låt oss beteckna mängden primtal med och definiera den som summan av logaritmer av primtal som inte överstiger : $\mathbb {P}$ $\theta(n)$ $n$

\theta (n)=\summa _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p).

Till exempel . $\theta(10)=\ln 2 + \ln 3 + \ln 5 + \ln 7$

Denna funktion kallas -Chebyshev-funktionen . $\theta$

Lemma

\theta(n) < n \cdot \ln(4)

för alla .

n\geqslant 1

(Intressant nog, för att bevisa satsen att det inte finns "särskilt få" primtal, måste vi först bevisa lemmat att det inte finns "särskilt många" primtal.)

Notera - och detta är huvudidén med beviset för lemma - att för alla icke-negativa heltal är binomialkoefficienten delbar med alla primtal i intervallet . Faktum är att ett valfritt primtal i det angivna intervallet delar täljaren för denna bråkdel och delar inte dess nämnare. Eftersom binomialkoefficienten är delbar med alla sådana primtal kan den inte vara mindre än deras produkt $m$ ${2m+1 \choose m}$ $[m+2,\;2m+1]$ ${2m+1 \choose m} = \frac {(2m+1)!} {m!(m+1)!}$

{2m+1 \choose m}\geqslant \prod _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}s.

Om vi tar logaritmen för båda sidor av ojämlikheten får vi

\ln {2m+1 \choose m}\geqslant \sum _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}\ln p=\theta (2m +1)-\theta (m+1).

Å andra sidan är binomialkoefficienten lätt att uppskatta från ovan: ${2m+1 \choose m}$

{2m+1 \choose m}={\frac {{2m+1 \choose m}+{2m+1 \choose m+1}}{2}}\leqslant {\frac {\sum _{ k=0}^{2m+1}{2m+1 \choose k}}{2}}=

={\frac {(1+1)^{2m+1}}{2}}=4^{m}.

Kombinerar vi de två sista ojämlikheterna får vi

\theta (2m+1)-\theta (m+1)\leqslant \ln 4^{m}=m\ln 4

Var

\theta (2m+1)\leqslant \theta (m+1)+m\ln 4

Nu är det lätt att bevisa lemmat genom induktion:

$n=1$ :

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

$n=2$ :

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

$n>2$ och udda. Låt . $n$ $n = 2m+1$

\theta (2m+1)\leqslant \theta (m+1)+m\ln 4<(m+1)\ln 4+m\ln 4=(2m+1)\ln 4=n\ ln 4

$n > 2$ och tydlig. $n$

\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)

(eftersom ett jämnt tal större än 2 är sammansatt, ingår det inte i summan ). Lemmat är bevisat. $\ln(n)$ $\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p)$

Bevis på huvudsatsen

Vi övergår nu till beviset för själva postulatet. Huvudidén med beviset är att dekomponera binomialkoefficienten i primtalsfaktorer. Om det inte finns några primtal mellan och då blir produkten av alla dessa primtal för liten. $2n \välj n$ $n$ $2n$

Vi bevisar genom motsägelse. Antag att det för något heltal inte finns något primtal så att . $n \geqslant 2$ $sid$ $n<p<2n$

Om , då ett av primtalen 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 och 2503 (varje efterföljande är mindre än två gånger det föregående), låt oss kalla det , uppfyller ojämlikhet . Därför, . $2\leqslant n<2048$ $sid$ $n<p<2n$ $n\geqslant 2048$

Låt oss uppskatta . $2n \välj n$

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

Eftersom är summans maximala term, har vi: ${2n \välj n}$

{\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}.

Definition av R ( p , n ) och dess övre skattning

Låt vara graden i nedbrytningen i primtal faktorer. $R(p,\;n)$ $sid$ ${2n \välj n}$

{2n \choose n}=\prod _{p}{p^{R(p,\;n)))

Eftersom för var och en har exakt faktorer som är delbara med , i sönderdelningen till primtalsfaktorer kommer den in i befogenheterna för . Det är därför $n!$ $j$ $\left \lfloor \frac {n} {p^j} \right \rfloor$ $p^j$ $n!$ $sid$ $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$

R(p,\;n)=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j))}\right\rfloor -2\ summa _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j))}\right\rfloor =\summa _{j=1}^{\infty }\left (\vänster\lgolv {\frac {2n}{p^{j))}\höger\rgolv -2\vänster\lgolv {\frac {n}{p^{j))}\höger\rgolv \höger) .

För att ta reda på mer om denna summa, låt oss å ena sidan uppskatta hur stora dess villkor är och å andra sidan deras antal.

Värde : varje term kan vara antingen 0 eller 1 (beroende på bråkdelen : om den är mindre än , är termen 0, och om eller mer, då 1). $\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$ $\frac {n} {p^j}$ ${\frac {1}{2))$ ${\frac {1}{2))$

Kvantitet : alla termer med är lika med noll, eftersom för dem . Därför är det bara de första termerna som har en chans att inte vara noll. $j > \frac {\ln(2n)} {\ln(p)}$ $\frac {2n} {p^j} < 1$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

Så är summan av termerna, som var och en är lika med 0 eller 1. Därför, $R(p,\;n)$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

R(p,\;n)\leqslant \left\lgolv {\frac {\ln(2n)}{\ln(p)))\höger\rgolv .

Kvalitet

{\displaystyle p^{R(p,\;n)))

Låt oss utvärdera nu . $p^{R(p,n)}$

p^{R(p,\;n)}=\exp \left(R(p,\;n)\ln p\right)\leqslant \exp \left(\left\lfloor {\frac { \ln(2n)}{\ln(p)}}\höger\rgolv \ln p\höger)\leqslant 2n.

Det var en uppskattning för någon . Men en mycket bättre uppskattning kan erhållas för . För sådana är antalet termer 1, det vill säga det finns bara en term i vår summa: $sid$ ${\sqrt {2n}}<p\leqslant 2n$ $sid$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

R(p,\;n)=\vänster\lgolv {\frac {2n}{p}}\höger\rgolv -2\vänster\lgolv {\frac {n}{p}}\höger\rgolv .

Om denna term är lika med 1, då . Och om det är lika med 0, då . $p^{R(p,\;n)}=p$ $p^{R(p,\;n)}=1$

I vilket intervall kan primtalsdivisorerna vara?

Låt oss nu se vilket intervall primtallarna befinner sig i. har inga primtalare så att: ${2n \välj n}$ $sid$

$2n<p$ , eftersom . $R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)))\right\rfloor =0$
$n<p\leqslant 2n$ , eftersom vi antog att det inte finns några primtal i detta intervall.
${\frac {2n}{3}}<p\leqslant n$ , eftersom (eftersom ), som ger oss . $p > \sqrt{2n}$ $n\geqslant 5$ $R(p,\;n)=\vänster\lgolv {\frac {2n}{p}}\höger\rgolv -2\vänster\lgolv {\frac {n}{p}}\höger\rgolv =2-2=0$

Det visar sig att det inte finns några primtalare som är större än . ${2n \välj n}$ $\frac {2n} {3}$

Multiplicera alla

{\displaystyle p^{R(p,\;n)))

Nu uppskattar vi produkten över alla primtalsdelare av talet . För divisorer som inte är stora överstiger produkten inte . Och för primtalsdelare, stora , överstiger den inte . ${\displaystyle p^{R(p,\;n)))$ $sid$ ${2n \välj n}$ $\sqrt{2n}$ ${(2n)} ^ {\sqrt{2n))$ $\sqrt{2n}$ $\prod _{p\in \mathbb {P} ;\,p\leqslant 2n/3}p=\exp \left(\theta \left({\frac {2n}{3))\right) \höger)$

Eftersom det är lika med produkten över alla primtal får vi: ${2n \välj n}$ ${\displaystyle p^{R(p,\;n)))$ $sid$

{\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}\leqslant (2n)^{\sqrt {2n}}\exp \left(\theta \left( {\frac {2n}{3}}\right)\right).

Med hjälp av vårt lemma : $\theta(n) < n \cdot \ln(4)$

{\frac {4^{n}}{2n+1}}<(2n)^{\sqrt {2n}}4^{\frac {2n}{3}}.

Eftersom : $(2n+1) < (2n)^2$

4^{\frac {n}{3}}<(2n)^{2+{\sqrt {2n}}}.

Också (eftersom ): $2\leqslant {\frac {\sqrt {2n}}{3}}$ $n\geqslant 18$

4^{\frac {n}{3}}<(2n)^{{\frac {4}{3}}{\sqrt {2n}}}.

Logaritmisering på båda sidor får vi

{\sqrt {2n}}\ln(2)<4\cdot \ln(2n).

Göra ett byte : $2^{2t}=2n$

{\frac {2^{t}}{t}}<8

Detta ger oss en motsägelse: $t<6$

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

Därför var vårt antagande felaktigt.

Ch.t.d.

Anteckningar

^ Encyclopedic Dictionary of a Young Mathematician, 1985 .
↑ GH Hardy och EM Wright, An Introduction to the Theory of Numbers , 6:e upplagan, Oxford University Press, 2008, sid. 494.
↑ J. Nagura. På intervallet som innehåller minst ett primtal // Proceedings of the Japan Academy, Series A. - 1952. - Vol. 28. - S. 177-181. - doi : 10.3792/pja/1195570997 .

Litteratur

Primtal // Encyclopedic Dictionary of a Young Mathematician / Komp. A.P. Savin. - M .: Pedagogy , 1985. - S. 262 -263. — 352 sid.
V. I. Zenkin. Fördelning av primtal. Elementära metoder. Kaliningrad, 2008.