Informatyka MIMUW

Już Euklides odnotował, że "jest więcej liczb pierwszych niż w każdym danym zbiorze liczb pierwszych", tzn.:

Twierdzenie 10.11

Liczb pierwszych jest nieskończenie wiele.

Dowód

Podamy dwa dowody tego twierdzenia pochodzące odpowiednio od Euklidesa i Eulera.

Załóżmy niewprost za Euklidesem, że liczb pierwszych jest skończenie wiele i są to: $p_1,\ldots,p_k$. Rozważmy liczbę $n=p_1p_2\ldots p_k+1$. Jest ona oczywiście większa od każdej $p_i$. Ponadto żadna z liczb pierwszych $p_i$ nie dzieli $n$, bo przy dzieleniu przez $p_i$ daje resztę $1$. A zatem $n$, albo jest nową liczbą pierwszą, albo w rozkładzie $n$ są nowe liczby pierwsze. Sprzeczność.

Również dowód Eulera jest dowodem niewprost. Załóżmy więc, że zbiór $\mathbb{P}$ wszystkich liczb pierwszych jest skończony. Zauważmy, że:

$\displaystyle \prod_{p\in\mathbb{P}}\frac{1}{1-\frac{1}{p}} =\prod_{p\in\mathbb{P}}(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\ldots) =\sum_{n\geq1}\frac{1}{n}.$

Istotnie, pierwsza równość wynika ze wzoru na sumę nieskończonego ciągu geometrycznego: każdy czynnik iloczynu po lewej jest sumą nieskończonego ciągu geometrycznego o ilorazie $\frac{1}{p}$. Druga równość jest konsekwencją Fundamentalnego Twierdzenia Arytmetyki. Ponieważ założyliśmy, że liczb pierwszych jest skończenie wiele, to lewa strona równości jest oczywiście skończona. Wiemy natomiast, że suma po prawej stronie jest nieograniczona, jako że sumy częściowe początkowych $n$ wyrazów tego ciągu to kolejne liczby harmoniczne $H_n\geq \frac{\lfloor \lg{n}\rfloor+1}{2}$.

Matematycy zastanawiali się także, czy liczby pierwsze są, w pewnym sensie, regularnie rozłożone wśród liczb naturalnych. Jest wiele ciekawych rezultatów opisujących ten rozkład.

Twierdzenie 10.12 [Dirichlet 1837]

Dla dowolnych dwu dodatnich i względnie pierwszych liczb $a,d$ istnieje nieskończenie wiele liczb postaci $nd+a$ dla $n>0$.

Przykład

Twierdzenie Dirichleta uogólnia wiele wcześniej znanych faktów. Dla przykładu, możemy wywnioskować, iż jest nieskończenie wiele liczb pierwszych postaci $4n+1$ ($d=4,a=1$):

$\begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 4n+1 & 1 & \bf 5 & 9 & 13 & \bf 17 & 21 & 25 & \bf 29 & 33 & \bf 37 & \bf 41 & 45 & 49 \\ \hline \end {array}$

jak i postaci $4n+3$ ($d=4, a=3$):

$\begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 4n+3 & \bf 3 & \bf 7 & \bf 11 & 15 & \bf 19 & \bf 23 & 27 & \bf 31 & 35 & 39 & \bf 43 & \bf 47 & 51 \\ \hline \end {array}$

Tezę kolejnego twierdzenia, znanego jako Twierdzenie Bertanda-Czebyszewa lub Twierdzenie Czebyszewa, postawił Joseph Bertrand w 1845 roku. Zweryfikował on poprawność swojej tezy dla liczb $n$ z przedziału $[2,\ldots,3\cdot10^6]$. Pełny dowód przestawił dopiero Pafnuty Czebyszew w 1850 roku. Dowód, który tu przedstawiamy pochodzi od Paula Erd{o}s'a. Wykorzystał on następującą funkcję

$\displaystyle \vartheta(n)=\sum_{p\in\mathbb{P}_n}\ln{p},$

gdzie $\mathbb{P}_n$ oznacza zbiór liczb pierwszych nie większych od $n$. Ważną własność tej funkcji opisuje następujący lemat.

Lemat 10.13

Dla $n\geq 1$ zachodzi

$\vartheta(n) < n\cdot\ln{4}.$

Dowód

Dla dowodu indukcyjnego odnotujmy najpierw, że $\vartheta(1)=0 < 1\cdot\ln{4}$ oraz $\vartheta(2)=\ln{2} < 2\cdot\ln{4}$.

Niech teraz $n>2$ będzie parzyste. Wtedy oczywiście $n$ nie jest liczbą pierwszą i mamy

$\vartheta(n)=\vartheta(n-1) < (n-1)\cdot\ln{4} < n\cdot\ln{4}.$

Niech więc $n>2$ będzie nieparzyste, czyli $n=2m+1$ dla pewnego $m>0$. Rozważmy liczbę

${2m+1\choose m}=\frac{(2m)!}{m!\cdot m!}.$

Zauważmy, że każda liczba pierwsza $p$ w przedziale $m < p\leq 2m+1$ dzieli ${2m+1\choose m}$. Rzeczywiście, żadna liczba z mianownika nie może skrócić liczby pierwszej $p$ w liczniku co oznacza, że $p$ jest w rozkładzie ${2m+1\choose m}$. Ponadto, łatwo oszacować ${2m+1\choose m}$ od góry przez $4^m$, np. w ten sposób:

$\displaystyle 4^m=\frac{(1+1)^{2m+1}}{2} =\frac{\sum_{k=0}^{2m+1}{2m+1\choose k}}{2} \geq\frac{{2m+1\choose m}+{2m+1\choose m+1}}{2} ={2m+1\choose m}.$

To z kolei pozwala nam oszacować $\vartheta(2m+1)$ następująco:

$\displaystyle \vartheta(2m+1)-\vartheta(m+1) =\sum_{p\in\mathbb{P}_{2m+1}-\mathbb{P}_{m+1}}\ln{p} \leq\ln{{2m+1\choose m}} \leq\ln{4^m} \leq m\cdot\ln{4}.$

Z założenia indukcyjnego mamy natomiast $\vartheta(m+1) < m\cdot\ln{4}$, czyli

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

Twierdzenie 10.14 [Czebyszew 1850]

Dla dowolnego $n>1$ istnieje liczba pierwsza $p$ taka, że $n < p < 2n$.

Dowód

Dla dowodu niewprost załóżmy, że $n$ jest najmniejszą liczbą $n\geq 2$, dla której nie ma żadnej liczby pierwszej $p$ w przedziale $n < p < 2n$. Jeśli $2\leq n\leq 2048$, to jedna z liczb pierwszych $3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503$ będzie pomiędzy $n$ a $2n$. Oznacza to, że $n\geq2048$.

Przeanalizujmy teraz rozkład na czynniki pierwsze liczby:

${2n\choose n}=\frac{(2n)!}{n!\cdot n!}.$

Najpierw jednak zauważmy, że ponieważ $\displaystyle 4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n\choose k}$ a liczba ${2n\choose n}$ jest największym składnikiem tej sumy, to:

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

Ponieważ $2n$ jest największym czynnikiem licznika $\frac{(2n)!}{n!\cdot n!}={2n\choose n}$, to wszystkie liczby pierwsze $p$ w rozkładzie $2n\choose n$ są mniejsze od $2n$. Niech $R(p,n)$, gdzie $p$ jest liczbą pierwszą, będzie największą liczbą $x$ taką, że $p^x|{2n\choose n}$. Innymi słowy, $R(p,n)$ jest potęgą liczby $p$ w rozkładzie ${2n\choose n}$.

Łatwo zauważyć, że $n!$ ma czynnik $p$ w swoim rozkładzie na czynniki pierwsze $\displaystyle \sum_{k=1}^{\infty}\lfloor\frac{n}{p^k}\rfloor$ razy. To implikuje, że

$\displaystyle R(p,n) =\sum_{k=1}^\infty\lfloor\frac{2n}{p^k}\rfloor-2\cdot\sum_{k=1}^\infty\lfloor\frac{n}{p^k}\rfloor =\sum_{k=1}^{\infty}(\lfloor\frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor).$

Każdy składnik tej sumy postaci $\lfloor\frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor$ może przyjąć wartość:

• $0$, jeśli część ułamkowa $\frac{n}{p^k}$ jest mniejsza od $\frac{1}{2}$,

lub

• $1$, jeśli część ułamkowa $\frac{n}{p^k}$ jest niemniejsza od $\frac{1}{2}$.

Ponadto, dla $k>\log_p{2n}$ wszystkie składniki zerują się, bo $\frac{2n}{p^k} < 1$. To pozwala na następujące oszacowanie liczby $R(p,n)$

$R(p,n) < \lfloor\log_p{2n}\rfloor.$

To z kolei daje zaskakującą nierówność

$p^{R(p,n)}\leq 2n.$

Z dotychczasowych ustaleń dotyczących rozkładu liczby ${2n\choose n}$ na czynniki pierwsze wiemy, że nie występują tam liczby pierwsze $p$ takie, że:

• $p>2n$, gdyż $2n$ jest największym czynnikiem w liczniku rozważanego symbolu Newtona,

• $n < p\leq 2n$, gdyż założyliśmy, że nie ma takich liczb pierwszych,

• $\frac{2}{3}n < p\leq n$, gdyż wtedy $p>\sqrt{2n}$ (ponieważ $n\geq5$) i wobec tego tylko pierwszy składnik w nieskończonej sumie wyznaczającej $R(p,n)$ może być niezerowy. Ale wtedy i tak $R(p,n)=\lfloor \frac{2n}{p}\rfloor-2\lfloor \frac{n}{p}\rfloor=2-2=0$.

Zatem wszystkie liczby pierwsze w rozkładzie ${2n\choose n}$ są niewiększe niż $\frac{2}{3}n$. Liczby pierwsze $p>\sqrt{2n}$ występują tam w co najwyżej pierwszej potędze, jako że $p^{R(p,n)} < 2n$. Z kolei iloczyn $\prod p^{R(p,n)}$ przebiegający po liczbach pierwszych $p\leq\sqrt{2n}$ można oszacować z góry przez $(2n)^{\sqrt{2n}}$. Dotychczasowe oszacowania dają nam więc

$\displaystyle \frac{4^n}{2n+1}\leq{2n\choose n}\leq(2n)^{\sqrt{2n}}\prod_{p\in\mathbb{P}_{\frac{2}{3}n}}p=(2n)^{\sqrt{2n}}e^{\vartheta(\frac{2}{3}n)}.$

Z Lematu 10.13 wiemy, że $\vartheta(n) < n\cdot\ln{4}$, więc

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

Ponieważ $2n+1 < (2n)^2$ mamy

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

Z kolei $2\leq\frac{\sqrt{2n}}{3}$, bo $n\geq18$, więc

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

Logarytmując obie strony nierówności otrzymujemy

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

Podstawmy $n=2^{2t-1}$. Wtedy $\frac{2^t}{t}\leq 4$, a więc $t < 6$, co w stoi sprzeczności z $n>2048$, gdyż

$n=\frac{2^{2t}}{2} < \frac{2^{2\cdot6}}{2}=2048.$

Paulowi Erd{o}s'owi udało się uogólnić Twierdzenie Bertranda-Czebyszewa na kilka sposobów. Pokazał on np., że:

• dla każdego $k$ istnieje takie $n_0$, że dla wszystkich $n>n_0$ istnieje przynajmniej $k$ liczb pierwszych $p_1,\ldots,p_k$ w przedziale $n < p_i < 2n$,

• dla dowolnej liczby naturalnej $n>6$, między liczbami $n$ a $2n$ znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci $4k + 1$ oraz co najmniej jedna postaci $4k + 3$.

Wszystkie obserwacje o pewnej regularności rozkładu liczb pierwszych w zbiorze liczb naturalnych potwierdza (i w pewnym sensie uogólnia) Twierdzenie o Liczbach Pierwszych. Niech, jak poprzednio, $\mathbb{P}_n$ będzie zbiorem liczb pierwszych niewiększych od $n$ oraz $\pi(n)=\vert\mathbb{P}_n\vert$.

Twierdzenie 10.15 [Twierdzenie o Liczbach Pierwszych]

$\pi(n)\sim n/\ln{n}.$

Twierdzenie o Liczbach Pierwszych opisuje asymptotyczną gęstość liczb pierwszych wśród liczb naturalnych. Z grubsza, mówi ono, iż wybierając losowo liczbę w pobliżu pewnej dużej liczby $n$, mamy $\frac{1}{\ln{n}}$ szansy na to, by wylosowana liczba była pierwsza. Dla przykładu: w pobliżu $n=10 000$ mniej więcej co $9$-ta liczba jest pierwsza, tymczasem w pobliżu $n=1 000 000 000$ już co $21$-wsza liczba jest pierwsza. A więc, statystycznie, w przedziale $(n,2n)$ jest znacznie więcej liczb pierwszych niż mówią poprzednie twierdzenia. Problem polega na tym, że choć wiemy, że musi ich być bardzo dużo, to nie jesteśmy w stanie udowodnić, że dla konkretnie rozważanej liczby $n$ nie nastąpiło jakieś "lokalne zaburzenie".

Twierdzenie o Liczbach Pierwszych sformułował Adrien-Marie Legendre'a w 1796. Zostało ono udowodnione niezależnie przez Hadamarda i de la Vallée Poussina w 1896. Dowód używa złożonych metod analitycznych, wykraczających poza ramy tego wykładu. Dlatego nie przedstawimy jego pełnego dowodu. W zamian pokażemy znacznie słabsze:

Twierdzenie 10.16

$\pi(n)=O(n/\ln{n})$.

Dowód

Lemat 10.13 mówi, że $\vartheta(n) < n\cdot\ln{4}$, co równoważnie można wyrazić jako

$\displaystyle \prod_{p\in\mathbb{P}_n} < 4^n.$

Ponieważ w oczywisty sposób $\displaystyle \pi(n)!\leq \prod_{p\in\mathbb{P}_n}$, to ze wzoru Stirlinga mamy:

$\displaystyle (\frac{\pi(n)}{e})^{\pi(n)} < (\pi(n))! < \prod_{p\in\mathbb{P}_n}p < 4^n.$

Logarytmując stronami otrzymujemy $\pi(n)\cdot(\ln{\pi(n)}-1) < n\cdot\ln{4}$, co implikuje $\pi(n)=O(n/\ln{n})$.