Bertrandův postulát

Bertrandův postulát , Bertrand-Chebyshev teorém nebo Chebyshev teorém říká, že

Pro libovolné přirozené číslo n ⩾ 2 existuje prvočíslo p v intervalu n < p < 2 n .

Bertrandův postulát formuloval jako hypotézu v roce 1845 francouzský matematik Bertrand (který jej otestoval až do n = 3 000 000 ) a dokázal ho v roce 1852 [1] Čebyšev . Ramanujan našel jednodušší důkaz v roce 1919 a dokázal , že počet prvočísel v intervalu n < p < 2 n může být zespodu ohraničen neklesající posloupností, která inklinuje k nekonečnu, takže je dosaženo rovnosti v Ramanujanových prvočíslech . Erdős v roce 1932 dále zjednodušil důkaz.

Zobecnění

Za zobecnění Bertrandova postulátu lze považovat teorém, že mezi čísly vždy existuje číslo s prvočíslem větším než . Toto tvrzení dokázal Sylvester v roce 1892. Pro , uvádí Bertrandovu domněnku jako zvláštní případ. $n\geqslant 2k$ $n-k+1, \tečky, n-1, n$ $k$ $n=2k$

Z věty o rozdělení prvočísel vyplývá, že pro jakékoli existuje číslo takové, že pro jakékoli existuje prvočíslo splňující . Navíc pro pevný počet prvočísel v tomto intervalu inklinuje k nekonečnu s růstem [2] . Konkrétně například pro vždy existuje prvočíslo mezi a [3] . $\varepsilon >0$ $n_{0}$ $n\geqslant n_{0}$ $p$ $n<p<(1+\varepsilon )n$ $\varepsilon$ $n$ $n\geqslant 25$ $n$ $(1+1/5)n$

Hypotézy

Legendreův dohad říká, že pro nějaký tam je prvočíslo v intervalu . Oppermanova domněnka a Andritzova domněnka dávají stejné pořadí růstu pro interval, který obsahuje alespoň jedno prvočíslo. $n \geqslant 2$ $p$ ${\displaystyle n^{2}<p<(n+1)^{2))$

Nejsilnější je Cramerův dohad , který tvrdí, že

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

Všechny tyto hypotézy nebyly prokázány ani vyvráceny.

Důkaz

Důkaz Bertrandova postulátu

Zde uvádíme důkaz navržený Erdősem .

Notace a definice

V důkazu používáme následující zápis:

${a\vyberte b}$ je binomický koeficient nebo počet kombinací z by . $A$ $b$
$\left \lpatro x \right \rpatro$ je celá část . $X$

Označme množinu prvočísel a definujme ji jako součet logaritmů prvočísel nepřesahujících : $\mathbb {P}$ $\Opalování)$ $n$

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

Například . $\theta(10)=\ln 2 + \ln 3 + \ln 5 + \ln 7$

Tato funkce se nazývá -Čebyševova funkce . $\theta$

Lemma

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

pro všechny .

n\geqslant 1

(Zajímavé je, že abychom dokázali větu, že prvočísel „není příliš málo“, musíme nejprve dokázat lemma, že prvočísel „není příliš mnoho“.)

Všimněte si - a to je hlavní myšlenka důkazu lemmatu - že pro jakékoli nezáporné celé číslo je binomický koeficient dělitelný všemi prvočísly v intervalu . Jakékoli prvočíslo v zadaném intervalu totiž dělí čitatel tohoto zlomku a nedělí jeho jmenovatele. Protože binomický koeficient je dělitelný všemi takovými prvočísly, nemůže být menší než jejich součin $m$ ${2m+1 \vyberte m}$ $[m+2,\;2m+1]$ ${2m+1 \vyberte m} = \frac {(2m+1)!} {m!(m+1)!}$

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

Vezmeme-li logaritmus obou stran nerovnosti, dostaneme

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

Na druhou stranu, binomický koeficient lze snadno odhadnout shora: ${2m+1 \vyberte m}$

{2m+1 \choose m}={\frac {{2m+1 \vyber m}+{2m+1 \vyber m+1}}{2}}\leqslant {\frac {\součet _{ k=0}^{2m+1}{2m+1 \vyberte k}}{2}}=

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

Spojením posledních dvou nerovností dostaneme

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

Kde

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

Nyní je snadné dokázat lemma indukcí:

$n=1$ :

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

$n=2$ :

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

$n>2$ a liché. Nechte _ $n$ $n = 2 m+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$ a jasné. $n$

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

(protože každé sudé číslo větší než 2 je složené, není zahrnuto do součtu ). Lema je dokázáno. $\ln(n)$ $\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p)$

Důkaz hlavní věty

Nyní přejdeme k důkazu samotného postulátu. Hlavní myšlenkou důkazu je rozložit binomický koeficient na prvočinitele. Pokud mezi nimi nejsou žádná prvočísla a pak součin všech těchto prvočísel bude příliš malý. $2n \vyberte n$ $n$ $2n$

Dokazujeme protikladem. Předpokládejme, že pro nějaké celé číslo neexistuje prvočíslo takové, že . $n \geqslant 2$ $p$ $n<p<2n$

Jestliže , pak jedno z prvočísel 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 a 2503 (každé následující je menší než dvojnásobek toho předchozího), říkejme mu , vyhovuje nerovnost . Proto, . $2\leqslant n<2048$ $p$ $n<p<2n$ $n\geqslant 2048$

Pojďme odhadnout . $2n \vyberte n$

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

Protože je maximální doba součtu, máme: ${2n \vyberte n}$

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

Definice R ( p , n ) a jeho horní odhad

Nechť je stupeň rozkladu na prvočinitele. $R(p,\;n)$ $p$ ${2n \vyberte n}$

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

Protože pro každý má přesně faktory, které jsou dělitelné , při rozkladu na prvočinitele vstupuje do mocnin . Proto $n$ $j$ $\left \lfloor \frac {n} {p^j} \right \rfloor$ $p^j$ $n$ $p$ $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$

R(p,\;n)=\sum _{j=1}^{\infty }\left\lpatro {\frac {2n}{p^{j))}\right\rpatro -2\ součet _{j=1}^{\infty }\left\lpatro {\frac {n}{p^{j))}\pravý\rpatro =\sum _{j=1}^{\infty }\left (\left\lpatro {\frac {2n}{p^{j))}\right\rpatro -2\left\lpatro {\frac {n}{p^{j))}\right\rpatro \right) .

Abychom se o této sumě dozvěděli více, odhadněme na jedné straně, jak velké jsou její členy, a na druhé straně jejich počet.

Hodnota : každý člen může být 0 nebo 1 (v závislosti na zlomkové části : pokud je menší než , člen je 0, a pokud nebo více, pak 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))$

Množství : všechny členy s jsou rovny nule, protože pro ně . Proto pouze první členy mají šanci být nenulové. $j > \frac {\ln(2n)} {\ln(p)}$ $\frac {2n} {p^j} < 1$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

Je tedy součet členů, z nichž každý je roven 0 nebo 1. $R(p,\;n)$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)))\right\rfloor .

Školní známka

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

Pojďme nyní hodnotit . $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)}}\pravé\rpodlaží \ln p\vpravo)\leqslant 2n.

Byl to odhad pro všechny . Ale mnohem lepší odhad lze získat pro . Pro takový je počet členů 1, to znamená, že v našem součtu je pouze jeden člen: $p$ ${\sqrt {2n}}<p\leqslant 2n$ $p$ $\left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

R(p,\;n)=\left\lpatro {\frac {2n}{p}}\right\rfloor -2\left\lpatro {\frac {n}{p}}\right\rpatro .

Pokud je tento člen roven 1, pak . A pokud se rovná 0, pak . $p^{R(p,\;n)}=p$ $p^{R(p,\;n)}=1$

V jakém intervalu mohou být prvočíslí dělitelé?

Nyní se podívejme, v jakém intervalu jsou prvočíslí dělitelé. nemá žádné prvočíselné dělitele takové, že: ${2n \vyberte n}$ $p$

$2n<p$ , protože . $R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)))\right\rfloor =0$
$n<p\leqslant 2n$ , protože jsme předpokládali, že v tomto intervalu nejsou žádná prvočísla.
${\frac {2n}{3}}<p\leqslant n$ , protože (protože ), což nám dává . $p > \sqrt{2n}$ $n\geqslant 5$ $R(p,\;n)=\left\lpatro {\frac {2n}{p}}\right\rfloor -2\left\lpatro {\frac {n}{p}}\right\rpatro =2-2=0$

Ukazuje se, že neexistují žádné prvočíselníky větší než . ${2n \vyberte n}$ $\frac {2n} {3}$

Vynásobení všech

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

Nyní odhadneme součin přes všechny prvočíselné dělitele čísla . U nevelkých dělitelů součin nepřesahuje . A pro prvočíselníky, velké , nepřesahuje . ${\displaystyle p^{R(p,\;n)))$ $p$ ${2n \vyberte 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) \že jo)$

Protože se rovná součinu přes všechna prvočísla , dostáváme: ${2n \vyberte n}$ ${\displaystyle p^{R(p,\;n)))$ $p$

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

Pomocí našeho lemmatu : $\theta(n) < n \cdot \ln(4)$

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

Protože : $(2n+1) < (2n)^2$

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

Také (protože ): $2\leqslant {\frac {\sqrt {2n}}{3}}$ $n\geqslant 18$

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

Logaritmizujeme obě strany, dostaneme

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

Provedení náhrady : $2^{2t}=2n$

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

To nám dává rozpor: $t<6$

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

Proto byl náš předpoklad mylný.

Ch.t.d.

Poznámky

↑ Encyklopedický slovník mladého matematika, 1985 .
↑ GH Hardy a EM Wright, Úvod do teorie čísel , 6. vydání, Oxford University Press, 2008, str. 494.
↑ J. Nagura. Na intervalu obsahujícím alespoň jedno prvočíslo // Proceedings of the Japan Academy, Series A. - 1952. - Vol. 28. - S. 177-181. - doi : 10.3792/pja/1195570997 .

Literatura

Prvočíslo // Encyklopedický slovník mladého matematika / Komp. A. P. Savin. - M .: Pedagogika , 1985. - S. 262 -263. — 352 s.
V. I. Zenkin. Rozdělení prvočísel. Elementární metody. Kaliningrad, 2008.