Twierdzenie Czebyszewa o funkcji π(n)

Z Henryk Dąbrowski
Przejdź do nawigacji Przejdź do wyszukiwania
07.11.2021



Oznaczenia

Będziemy stosowali następujące oznaczenia:

[math]\displaystyle{ \mathbb{Z} }[/math] — zbiór liczb całkowitych
[math]\displaystyle{ \mathbb{Z}_+ }[/math] — zbiór liczb całkowitych dodatnich
[math]\displaystyle{ \mathbb{N} }[/math] — zbiór liczb naturalnych [math]\displaystyle{ \mathbb{N} = \mathbb{Z}_{+} }[/math]
[math]\displaystyle{ \mathbb{N}_0 }[/math] — zbiór liczb całkowitych nieujemnych [math]\displaystyle{ \mathbb{N}_0 = \mathbb{Z}_{+} \cup \left \{ 0 \right \} }[/math]
[math]\displaystyle{ \mathbb{R} }[/math] — zbiór liczb rzeczywistych
[math]\displaystyle{ d \mid n }[/math] — czytaj: d dzieli n ([math]\displaystyle{ d }[/math] jest dzielnikiem liczby [math]\displaystyle{ n }[/math])
[math]\displaystyle{ d \nmid n }[/math] — czytaj: d nie dzieli n ([math]\displaystyle{ d }[/math] nie jest dzielnikiem liczby [math]\displaystyle{ n }[/math])
[math]\displaystyle{ p_n }[/math] — [math]\displaystyle{ n }[/math]-ta liczba pierwsza
[math]\displaystyle{ \pi (n) }[/math] — ilość liczb pierwszych nie większych od [math]\displaystyle{ n }[/math]
[math]\displaystyle{ P(n) }[/math] — iloczyn liczb pierwszych nie większych od [math]\displaystyle{ n }[/math]
[math]\displaystyle{ \lfloor x \rfloor }[/math] — największa liczba całkowita nie większa od [math]\displaystyle{ x }[/math]
[math]\displaystyle{ {\small\binom{n}{m}} }[/math] — współczynnik dwumianowy (symbol Newtona), [math]\displaystyle{ {\small\binom{n}{m}} = {\small\frac{n!}{m! \cdot (n - m) !}} }[/math]
[math]\displaystyle{ \log (x) }[/math] — logarytm naturalny liczby [math]\displaystyle{ x \gt 0 }[/math]
[math]\displaystyle{ W_p (n) }[/math] — wykładnik, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia na czynniki pierwsze liczby [math]\displaystyle{ n }[/math]
[math]\displaystyle{ n }[/math] — oznacza zawsze liczbę naturalną
[math]\displaystyle{ p }[/math] — oznacza zawsze liczbę pierwszą


Przykładowe wartości niektórych wypisanych wyżej funkcji:

[math]\displaystyle{ p_2 = 3 }[/math],   [math]\displaystyle{ p_{10} = 29 }[/math],   [math]\displaystyle{ p_{100} = 541 }[/math]
[math]\displaystyle{ \pi (10) = 4 }[/math],   [math]\displaystyle{ \pi (100) = 25 }[/math],   [math]\displaystyle{ \pi (541) = 100 }[/math]
[math]\displaystyle{ P(5) = 30 }[/math],   [math]\displaystyle{ P(10) = 210 }[/math],   [math]\displaystyle{ P(50) = 614889782588491410 }[/math]
[math]\displaystyle{ \lfloor 1.2 \rfloor = 1 }[/math],   [math]\displaystyle{ \lfloor 2.8 \rfloor = 2 }[/math],   [math]\displaystyle{ \lfloor - 1.5 \rfloor = - 2 }[/math]
[math]\displaystyle{ {\small\binom{5}{2}} = 10 }[/math],   [math]\displaystyle{ {\small\binom{10}{5}} = 252 }[/math],   [math]\displaystyle{ {\small\binom{9}{3}} = 84 }[/math]
[math]\displaystyle{ W_2 (8) = 3 }[/math],   [math]\displaystyle{ W_3 (18) = 2 }[/math],   [math]\displaystyle{ W_7 (28) = 1 }[/math]


Funkcje te są zaimplementowane w PARI/GP[1]

[math]\displaystyle{ p_n }[/math] = prime(n)
[math]\displaystyle{ \pi (n) }[/math] = primepi(n)
[math]\displaystyle{ P(n) }[/math] = prodeuler(p=2, n, p)
[math]\displaystyle{ \lfloor x \rfloor }[/math] = floor(x)
[math]\displaystyle{ {\small\binom{n}{m}} }[/math] = binomial(n, m)
[math]\displaystyle{ W_p (n) }[/math] = valuation(n, p)



Twierdzenie Czebyszewa

W 1852 roku rosyjski matematyk Czebyszew[2][3] udowodnił, że dla funkcji [math]\displaystyle{ \pi (n) }[/math] prawdziwe jest następujące oszacowanie

[math]\displaystyle{ a \cdot {\small\frac{n}{\log n}} \: \underset{n \geqslant 11}{\lt } \: \pi (n) \: \underset{n \geqslant 96098}{\lt } \: b \cdot {\small\frac{n}{\log n}} }[/math]

gdzie

[math]\displaystyle{ a = \log (2^{1 / 2} \cdot 3^{1 / 3} \cdot 5^{1 / 5} \cdot 30^{- 1 / 30}) = 0.921292022 \qquad \quad b = \tfrac{6}{5} a = 1.105550428 }[/math]


Dziwnym zrządzeniem losu rezultat ten określany jest jako nierówności Czebyszewa (których nie należy mylić z nierównościami udowodnionymi przez Czebyszewa w teorii prawdopodobieństwa), a twierdzeniem Czebyszewa nazywany jest łatwy wniosek z tych nierówności. Stąd tytuł tego artykułu: „Twierdzenie Czebyszewa o funkcji [math]\displaystyle{ \pi (n) }[/math]”

Twierdzenie Czebyszewa o funkcji [math]\displaystyle{ \pi (n) }[/math] nabrało nowego życia, gdy w 1936 Erdos[4] zelementaryzował jego dowód. Elementarny dowód daje mniej dokładne oszacowania, ale pozwala zapoznać się z tym pięknym twierdzeniem nawet uczniom szkoły podstawowej.


Czytelnik powinien mieć świadomość, że rezultat ten ma już jedynie znaczenie historyczne – dzisiaj dysponujemy znacznie lepszymi oszacowaniami[5][6][7][8] funkcji [math]\displaystyle{ \pi (n) }[/math] oraz [math]\displaystyle{ p_n }[/math]


[math]\displaystyle{ {\small\frac{n}{\log n}} \left( 1 + {\small\frac{1}{\log n}} \right) \underset{n \geqslant 599}{\lt } \pi (n) \underset{n \geqslant 2}{\lt } {\small\frac{n}{\log n}} \left( 1 + {\small\frac{1.28}{\log n}} \right) }[/math]


[math]\displaystyle{ n (\log n + \log \log n - 1) \underset{n \geqslant 2}{\lt } p_n \underset{n \geqslant 6}{\lt } n (\log n + \log \log n) }[/math]


Przedstawimy tutaj elementarny dowód twierdzenia Czebyszewa o funkcji [math]\displaystyle{ \pi (n) }[/math] oraz analogiczne oszacowanie dla funkcji [math]\displaystyle{ p_n }[/math].


Twierdzenie A1
Prawdziwe są następujące oszacowania:


[math]\displaystyle{ 0.72 \cdot n \log n \underset{n \geqslant 1}{\lt } p_n \underset{n \geqslant 3}{\lt } 2n \log n }[/math]


[math]\displaystyle{ {\small\frac{2}{3}} \cdot {\small\frac{n}{\log n}} \underset{n \geqslant 3}{\lt } \pi (n) \underset{n \geqslant 2}{\lt } {\small\frac{2 n}{\log n}} }[/math]


Dowód powyższego twierdzenia jest łatwy, ale wymaga udowodnienia kolejno wielu, przeważnie bardzo prostych, twierdzeń pomocniczych.



Oszacowanie [math]\displaystyle{ p_n }[/math] od dołu i [math]\displaystyle{ \pi (n) }[/math] od góry

Rozpoczniemy od oszacowania liczby [math]\displaystyle{ {\small\binom{2n}{n}} }[/math]. Badanie właściwości tego współczynnika dwumianowego jest kluczowe dla naszego dowodu.

Twierdzenie A2
Niech [math]\displaystyle{ n, k \in \mathbb{N} }[/math]. Współczynnik dwumianowy [math]\displaystyle{ {\small\binom{n}{k}} }[/math] jest zawsze liczbą całkowitą dodatnią.

Dowód


Twierdzenie A3
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Współczynnik dwumianowy [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] jest liczbą parzystą.

Dowód


Twierdzenie A4
Prawdziwe są następujące oszacowania współczynnika dwumianowego [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math]

[math]\displaystyle{ 3.8^{n + 1} \underset{n \geqslant 80}{\lt } {\small\binom{2 n}{n}} \underset{n \geqslant 5}{\lt } 4^{n - 1} }[/math]
Dowód


Twierdzenie A5
Dla [math]\displaystyle{ n \geqslant 12 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ p_n \gt 3 n }[/math].

Dowód


Twierdzenie A6
Ciąg [math]\displaystyle{ a_n = \left( 1 + {\small\frac{1}{n}} \right)^n }[/math] jest rosnący i ograniczony. Dla wyrazów ciągu [math]\displaystyle{ (a_n) }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ 2 \leqslant a_n \lt 3 }[/math].

Dowód


Twierdzenie A7
Prawdziwe są następujące oszacowania:

[math]\displaystyle{ n^n \underset{n \geqslant 13}{\lt } p_1 p_2 \cdot \ldots \cdot p_n \underset{n \geqslant 3}{\lt } (n \log n)^n }[/math]
Dowód


Twierdzenie A8
Dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ {\small\frac{P (2 n)}{P (n)}} \lt 4^{n - 1} }[/math], gdzie [math]\displaystyle{ P (n) }[/math] oznacza iloczyn wszystkich liczb pierwszych nie większych od [math]\displaystyle{ n }[/math].

Dowód


Twierdzenie A9
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ P(n) \lt 4^n }[/math]

Dowód


Twierdzenie A10
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ p_n \gt {\small\frac{1}{2 \log 2}} \cdot n \log n }[/math].

Dowód


Twierdzenie A11
Dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \pi (2 n) - \pi (n) \lt 2 \log 2 \cdot {\small\frac{n}{\log n}} }[/math].

Dowód


Twierdzenie A12
Dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \pi (n) \lt 2 \cdot {\small\frac{n}{\log n}} }[/math].

Dowód



Wykładnik, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] występuje w [math]\displaystyle{ n! }[/math]

Uzyskanie kolejnych oszacowań wymaga znalezienia wykładnika, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia współczynnika dwumianowego [math]\displaystyle{ {\small\binom{2 n}{n}} = {\small\frac{(2 n) !}{(n!)^2}} }[/math].


Definicja A13
Funkcję [math]\displaystyle{ \lfloor x \rfloor }[/math] (czytaj: całość z [math]\displaystyle{ x }[/math]) definiujemy jako największą liczbę całkowitą nie większą od [math]\displaystyle{ x }[/math]. Operacyjnie możemy ją zdefiniować następująco: niech liczby [math]\displaystyle{ x, \varepsilon \in \mathbb{R} }[/math], liczba [math]\displaystyle{ k \in \mathbb{Z} }[/math] oraz [math]\displaystyle{ 0 \leqslant \varepsilon \lt 1 }[/math], jeżeli [math]\displaystyle{ x = k + \varepsilon }[/math], to [math]\displaystyle{ \lfloor x \rfloor = \lfloor k + \varepsilon \rfloor = k }[/math].


Twierdzenie A14
Dla [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math], [math]\displaystyle{ x \in \mathbb{R} }[/math] jest [math]\displaystyle{ \left \lfloor {\small\frac{x}{n}} \right\rfloor = \left \lfloor {\small\frac{\left \lfloor x \right \rfloor}{n}} \right \rfloor }[/math].

Dowód


Twierdzenie A15
Niech [math]\displaystyle{ x \in \mathbb{R} }[/math]. Liczba [math]\displaystyle{ \lfloor 2 x \rfloor - 2 \lfloor x \rfloor }[/math] przyjmuje wartości [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math].

Dowód


Bardzo istotnym rezultatem (z punktu widzenia przyszłych obliczeń) będzie znalezienie wykładnika, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] występuje w iloczynie [math]\displaystyle{ 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = n! }[/math]


Definicja A16
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą, zaś [math]\displaystyle{ a }[/math] dowolną liczbą naturalną. Jeżeli liczba pierwsza [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia liczby naturalnej [math]\displaystyle{ n \geqslant 2 }[/math] na czynniki pierwsze z wykładnikiem [math]\displaystyle{ a }[/math], to powiemy, że funkcja [math]\displaystyle{ W_p (n) }[/math] przyjmuje wartość [math]\displaystyle{ a }[/math]. Fakt ten możemy zapisać następująco

[math]\displaystyle{ W_p (n) = a \qquad\qquad \iff \qquad\qquad p^{a} \mid n \qquad \text{i} \qquad p^{a + 1} \nmid n }[/math]


Przykład A17
[math]\displaystyle{ W_5 (100) = 2 }[/math],   [math]\displaystyle{ W_7 (42) = 1 }[/math],   ponieważ [math]\displaystyle{ 11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11 }[/math], to [math]\displaystyle{ W_3 (11!) = 4 }[/math]


Wprost z definicji funkcji [math]\displaystyle{ W_p (n) }[/math] wynikają następujące właściwości:


Twierdzenie A18

Podstawowe własności funkcji [math]\displaystyle{ W_p (n) }[/math]

  1. [math]\displaystyle{ \;\; W_p (n \cdot m) = W_p (n) + W_p (m) }[/math]
  2. [math]\displaystyle{ \;\; W_p (n \cdot p^a) = a + W_p (n) }[/math]
  3. [math]\displaystyle{ \;\; W_{p}\left ( {\small\frac{n}{m}} \right ) = W_{p}\left ( n \right ) - W_{p}\left ( m \right ) \quad \text{o ile} \quad {\small\frac{n}{m}}\in \mathbb{Z}_{+} }[/math]
  4. [math]\displaystyle{ \;\; p \nmid n \quad\quad \iff \quad\quad W_p (n) = 0 }[/math]


Twierdzenie A19
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Ilość liczb podzielnych przez [math]\displaystyle{ p }[/math] i występujących w ciągu [math]\displaystyle{ 1, 2, 3, \ldots, n }[/math] wynosi [math]\displaystyle{ r = \left\lfloor {\small\frac{n}{p}} \right\rfloor }[/math].

Dowód


Przykład A20
Ilość liczb całkowitych dodatnich podzielnych przez [math]\displaystyle{ 5 }[/math] i nie większych od [math]\displaystyle{ 63 }[/math] wynosi [math]\displaystyle{ \left\lfloor {\small\frac{63}{5}} \right\rfloor = 12 }[/math]. Liczby te to [math]\displaystyle{ 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60 }[/math].


Twierdzenie A19 umożliwi nam określenie wykładnika, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] występuje w [math]\displaystyle{ n! }[/math]

Twierdzenie A21
Liczba pierwsza [math]\displaystyle{ p }[/math] występuje w iloczynie [math]\displaystyle{ n! }[/math] z wykładnikiem [math]\displaystyle{ W_p (n!) = \sum_{k = 1}^{\infty} \left\lfloor {\small\frac{n}{p^k}} \right\rfloor }[/math]

Dowód


Uwaga A22
Łatwo zauważymy, że liczba sumowań jest skończona, gdy powyższy wzór zapiszemy w postaci

[math]\displaystyle{ W_p (n!) = \sum_{k = 1}^B \left\lfloor {\small\frac{n}{p^k}} \right\rfloor }[/math]

gdzie [math]\displaystyle{ B = \lfloor \log_2 (n) \rfloor }[/math]. Jest tak dlatego, że jeżeli [math]\displaystyle{ k }[/math] przekroczy [math]\displaystyle{ \lfloor \log_2 (n) \rfloor }[/math], to dla liczby pierwszej [math]\displaystyle{ p = 2 }[/math], jak również dla wszystkich innych liczb pierwszych, mamy

[math]\displaystyle{ {\small\frac{n}{p^k}} \lt 1 }[/math]

czyli dla [math]\displaystyle{ k \gt B }[/math] sumujemy same zera.


Przykład A23
Niech [math]\displaystyle{ n = 30 }[/math], [math]\displaystyle{ p = 3 }[/math]

[math]\displaystyle{ W_3 (30!) = W_3 (1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot 30) = }[/math]
[math]\displaystyle{ \quad = W_3 (3\cdot 6 \cdot 9 \cdot 12 \cdot 15 \cdot 18 \cdot 21 \cdot 24 \cdot 27 \cdot 30) = }[/math]
[math]\displaystyle{ \quad = W_3 (3^{10} \cdot 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) = }[/math]
[math]\displaystyle{ \quad = 10 + W_3 (1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) = }[/math]
[math]\displaystyle{ \quad = 10 + W_3 (3 \cdot 6 \cdot 9) = }[/math]
[math]\displaystyle{ \quad = 10 + W_3 (3^3 \cdot 1 \cdot 2 \cdot 3) = }[/math]
[math]\displaystyle{ \quad = 10 + 3 + W_3 (1 \cdot 2 \cdot 3) = }[/math]
[math]\displaystyle{ \quad = 10 + 3 + W_3 (3) = }[/math]
[math]\displaystyle{ \quad = 10 + 3 + 1 = }[/math]
[math]\displaystyle{ \quad = 14 }[/math]

Co jest zgodne ze wzorem:

[math]\displaystyle{ W_3 (30!) = \left\lfloor {\small\frac{30}{3}} \right\rfloor + \left\lfloor {\small\frac{30}{3^2}} \right\rfloor + \left\lfloor {\small\frac{30}{3^3}} \right\rfloor = 10 + 3 + 1 = 14 }[/math]



Podobnie jak w poprzednim podrozdziale będziemy badali współczynnik dwumianowy postaci [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math]. Teraz już łatwo możemy policzyć wykładnik, z jakim liczba pierwsza [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia na czynniki pierwsze tego współczynnika dwumianowego.


Twierdzenie A24
Liczba pierwsza [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia na czynniki pierwsze liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] z wykładnikiem

[math]\displaystyle{ u = \sum^{\infty}_{k = 1} \left( \left \lfloor {\small\frac{2n}{p^{k}}} \right \rfloor - 2 \left \lfloor {\small\frac{n}{p^{k}}} \right \rfloor \right) }[/math]
Dowód


Twierdzenie A25
Liczby pierwsze spełniające warunek [math]\displaystyle{ p \gt \sqrt{2 n} }[/math] występują w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze z wykładnikiem [math]\displaystyle{ u = 1 }[/math] lub [math]\displaystyle{ u = 0 }[/math].

Dowód


Twierdzenie A26
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Jeżeli [math]\displaystyle{ p^a \biggr\rvert {\small\binom{2 n}{n}} }[/math], to [math]\displaystyle{ p^a \leqslant 2 n }[/math].

Dowód



Oszacowanie [math]\displaystyle{ p_n }[/math] od góry i [math]\displaystyle{ \pi (n) }[/math] od dołu

Z twierdzenia A26 wynika natychmiast


Twierdzenie A27
Niech [math]\displaystyle{ {\small\binom{2 n}{n}} = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math] będzie rozkładem współczynnika dwumianowego na czynniki pierwsze. Dla każdej liczby pierwszej [math]\displaystyle{ q_i }[/math], [math]\displaystyle{ i = 1, \ldots, s }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ q^{\alpha_i}_i \leqslant 2 n }[/math].

Uwaga: w powyższym twierdzeniu [math]\displaystyle{ q_i }[/math] nie oznacza [math]\displaystyle{ i }[/math]-tej liczby pierwszej, a pewną liczbą pierwszą o indeksie [math]\displaystyle{ i }[/math] ze zboru liczb pierwszych [math]\displaystyle{ q_1, \ldots q_s }[/math], które wchodzą do rozkładu współczynnika dwumianowego na czynniki pierwsze z wykładnikiem większym od zera.


Twierdzenie A28
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwe jest następujące oszacowanie współczynnika dwumianowego [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math]

[math]\displaystyle{ {\small\binom{2 n}{n}} \leqslant (2 n)^{\pi (2 n)} \lt (2 n + 1)^{\pi (2 n + 1)} }[/math]
Dowód


Twierdzenie A29
Dla [math]\displaystyle{ n \geqslant 3 }[/math] prawdziwe jest następujące oszacowanie

[math]\displaystyle{ \pi (n) \gt {\small\frac{2}{3}} \cdot {\small\frac{n}{\log n}} }[/math]
Dowód


Twierdzenie A30
Niech [math]\displaystyle{ n \geqslant 3 }[/math]. Dla [math]\displaystyle{ n }[/math]-tej liczby pierwszej [math]\displaystyle{ p_n }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ p_n \lt 2 n \log n }[/math]

Dowód






Dowód twierdzenia A30 kończy dowód całego twierdzenia A1. Możemy teraz dokończyć dowód twierdzenia A7 i pokazać, że dla [math]\displaystyle{ n \geqslant 3 }[/math] prawdziwe jest oszacowanie:

[math]\displaystyle{ p_1 \cdot \ldots \cdot p_n \lt (n \log n)^n }[/math]
Dowód



Uwagi do dowodu

Wydłużając znacząco czas obliczeń, moglibyśmy nieco poprawić uzyskane wyżej oszacowanie i udowodnić


Twierdzenie A31
Niech [math]\displaystyle{ n \geqslant 3 }[/math]. Dla [math]\displaystyle{ n }[/math]-tej liczby pierwszej [math]\displaystyle{ p_n }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ p_n \lt 1.875 \cdot n \log n }[/math]

Dowód


Twierdzenie A32
Niech [math]\displaystyle{ n \geqslant 2 }[/math]. Dla funkcji [math]\displaystyle{ \pi (n) }[/math] prawdziwe jest oszacowanie

[math]\displaystyle{ \pi (n) \lt 1.733 \cdot {\small\frac{n}{\log n}} }[/math]
Dowód


Uwaga A33
Dowód twierdzenia A31 wymagał wykorzystania polecenia PARI/GP, w którym wielokrotnie była wywoływana funkcja prime(n). Analogiczna sytuacja miała miejsce w przypadku twierdzenia A32 – tam musieliśmy wielokrotnie wywoływać funkcję primepi(n). Znacznie lepiej w takim przypadku jest napisać krótki program, który zamiast wielokrotnie wywoływać te funkcje, będzie je obliczał w sposób ciągły w całym testowanym przedziale wartości. Taka zmiana znacząco skraca czas obliczeń. Podane niżej programy Test1(n) i Test2(n) wywołane z parametrami n = 520000 i odpowiednio n = 8*10^6 odpowiadają poleceniom 

for(s = 1, 520000, if( prime(s) >= s^(5/4), print(s) ))

for(n = 2, 8 * 10^6, if( primepi(n) >= 1.733 * n / log(n), print(n) ))

ale wykonywane są znacznie szybciej. 

Test1(n) = 
\\ test oszacowania: prime(k) >= k^(5/4) dla 1 <= k <= n
\\ bez bezpośredniego odwoływania się do funkcji prime(k)
{
local(p, k);
k = 1;
p = 2;
while( k <= n,
       if( p >= k^(5/4), print(k) );
       k = k + 1;
       p = nextprime(p + 1);  \\ liczba p ma wartość prime(k)
     );
}

Test2(n) = 
\\ test oszacowania: primepi(k) < 1.733*k/log(k) dla 2 <= k <= n 
\\ bez bezpośredniego odwoływania się do funkcji primepi(k)
{
local(s, k);
s = 1;
k = 2;
while( k <= n,
       if( s >= 1.733 * k / log(k), print(k) );
       k = k + 1;
       s = s + isprime(k);  \\ dla kolejnych k liczba s ma wartość primepi(k)
     );
}


Uwaga A34
Czytelnik nie powinien mieć złudzeń, że postępując podobnie, uzyskamy istotne polepszenie oszacowania funkcji [math]\displaystyle{ \pi (n) }[/math] lub [math]\displaystyle{ p_n }[/math]. Już osiągnięcie tą drogą oszacowania [math]\displaystyle{ p_n \lt 1.6 \cdot n \log n }[/math] przekracza możliwości obliczeniowe współczesnych komputerów. Wystarczy zauważyć, że nierówność

[math]\displaystyle{ \log x \lt {\small\frac{2}{3}} \cdot x^{1 / 16} }[/math]

jest prawdziwa dla [math]\displaystyle{ x \gt 7.671 \cdot 10^{32} }[/math].



Zastosowania

Ciekawy rezultat wynika z twierdzenia A7, ale wcześniej musimy udowodnić twierdzenie o średniej arytmetycznej i geometrycznej.

Twierdzenie A35
Dla dowolnych liczb dodatnich [math]\displaystyle{ a_1, a_2, \ldots, a_n }[/math] średnia arytmetyczna jest nie mniejsza od średniej geometrycznej

[math]\displaystyle{ {\small\frac{a_1 + a_2 + \ldots + a_n}{n}} \geqslant \sqrt[n]{a_1 a_2 \cdot \ldots \cdot a_n} }[/math]
Dowód


Twierdzenie A36
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwa jest nierówność [math]\displaystyle{ p_1 + p_2 + \ldots + p_n \gt n^2 }[/math].

Dowód


Twierdzenie A1 pozwala nam udowodnić różne oszacowania funkcji [math]\displaystyle{ \pi (n) }[/math] i [math]\displaystyle{ p_n }[/math], które byłyby trudne do uzyskania inną drogą. Wykorzystujemy do tego znany fakt, że dla dowolnego [math]\displaystyle{ \varepsilon \gt 0 }[/math] istnieje takie [math]\displaystyle{ n_0 }[/math], że dla każdego [math]\displaystyle{ n \gt n_0 }[/math] prawdziwa jest nierówność [math]\displaystyle{ \log x \lt x^{\varepsilon} }[/math]. Inaczej mówiąc, funkcja [math]\displaystyle{ \log x }[/math] rośnie wolniej niż najwolniej rosnąca funkcja potęgowa. Nim przejdziemy do dowodu takich przykładowych oszacowań, udowodnimy pomocnicze twierdzenie, które wykorzystamy przy szacowaniu.


Twierdzenie A37
Prawdziwe są następujące nierówności:

1.    [math]\displaystyle{ e^x \gt x \qquad \qquad \qquad \quad \:\, }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R} }[/math]
2.    [math]\displaystyle{ e^x \geqslant x + 1 \qquad \qquad \quad \;\:\, }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R} }[/math]   (równość zachodzi wtedy i tylko wtedy, gdy [math]\displaystyle{ x = 0 }[/math])
3.    [math]\displaystyle{ e^x \gt 2 x \qquad \qquad \qquad \;\;\,\, }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R} }[/math]
4.    [math]\displaystyle{ \log x \lt n \cdot x^{1 / n} \qquad \quad \;\;\: }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R}_+ }[/math] i dowolnego [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]
5.    [math]\displaystyle{ \log x \lt \tfrac{1}{2} n \cdot x^{1 / n} \qquad \quad }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R}_+ }[/math] i dowolnego [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]
6.    [math]\displaystyle{ \log x \leqslant n (x^{1 / n} - 1) \qquad }[/math] dla każdego [math]\displaystyle{ x \in \mathbb{R}_+ }[/math] i dowolnego [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]   (równość zachodzi wtedy i tylko wtedy, gdy [math]\displaystyle{ x = 1 }[/math])
Dowód


Zadanie A38
Niech [math]\displaystyle{ x \in \mathbb{R}_+ }[/math]. Pokazać, że dla dowolnego [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math] istnieje takie [math]\displaystyle{ x_0 }[/math], że dla każdego [math]\displaystyle{ x \gt x_0 }[/math] jest [math]\displaystyle{ \log x \lt x^{1 / n} }[/math].

Rozwiązanie


Twierdzenie A39
Dla funkcji [math]\displaystyle{ p_n }[/math] i [math]\displaystyle{ \pi (n) }[/math] prawdziwe są następujące oszacowania:

[math]\displaystyle{ 10 n \underset{n \geqslant 6473}{\lt } p_n \underset{n \geqslant 2}{\lt } n^2 }[/math]
[math]\displaystyle{ \sqrt{n} \underset{n \geqslant 5}{\lt } \pi (n) \underset{n \geqslant 64721}{\lt } {\small\frac{n}{10}} }[/math]
Dowód


Twierdzenie A40
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwe jest oszacowanie

[math]\displaystyle{ p_1 p_2 \cdot \ldots \cdot p_n \gt (p_{n^2})^{n / 3} }[/math]
Dowód


Zadanie A41
Korzystając z twierdzenia A40 pokazać, że

  •    [math]\displaystyle{ p_1 p_2 \cdot \ldots \cdot p_n \gt (p_{n + 1})^2 \qquad \qquad \text{dla } \; n \geqslant 4 }[/math]
  •    [math]\displaystyle{ p_1 p_2 \cdot \ldots \cdot p_n \gt (p_{2 n})^3 \qquad \qquad \;\; \text{dla } \; n \geqslant 7 }[/math]
Rozwiązanie


Twierdzenie A42
Każda liczba pierwsza [math]\displaystyle{ p }[/math] taka, że [math]\displaystyle{ p \in \left( {\small\frac{n}{2}}, n \right] }[/math] występuje w rozwinięciu [math]\displaystyle{ n! }[/math] na czynniki pierwsze z wykładnikiem równym jeden.

Dowód


Rezultat uzyskany w twierdzeniu A25 zainspirował nas do postawienia pytania: jakie warunki musi spełniać liczba pierwsza [math]\displaystyle{ p }[/math], aby występowała w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze z wykładnikiem równym jeden lub równym zero? Twierdzenia A43 i A45 udzielają na to pytanie precyzyjnej odpowiedzi. Przykłady A44 i A46 to tylko twierdzenia A43 i A45 dla wybranych wartości liczby [math]\displaystyle{ k }[/math]. Jeśli Czytelnik nie miał problemów ze zrozumieniem dowodów twierdzeń A43 i A45, to może je pominąć.


Twierdzenie A43
Niech [math]\displaystyle{ k }[/math] będzie dowolną ustaloną liczbą naturalną. Jeżeli [math]\displaystyle{ n \geqslant 2 (k + 1) \left( k + \tfrac{1}{2} \right) }[/math] i liczba pierwsza [math]\displaystyle{ p \in \left( {\small\frac{n}{k + 1}}, {\small\frac{n}{k + \tfrac{1}{2}}} \right] }[/math], to [math]\displaystyle{ p }[/math] występuje w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze z wykładnikiem równym jeden.

Dowód


Przykład A44
Jeżeli [math]\displaystyle{ n \geqslant 6 }[/math] i liczba pierwsza [math]\displaystyle{ p \in \left( {\small\frac{n}{2}}, {\small\frac{2 n}{3}} \right] }[/math], to [math]\displaystyle{ p }[/math] występuje w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze z wykładnikiem równym jeden.

Dowód


Twierdzenie A45
Niech [math]\displaystyle{ k }[/math] będzie dowolną ustaloną liczbą całkowitą dodatnią. Jeżeli liczba pierwsza [math]\displaystyle{ p \in \left( {\small\frac{n}{k + \tfrac{1}{2}}}, {\small\frac{n}{k}} \right] }[/math], to dla [math]\displaystyle{ n \geqslant 2 k (k + \tfrac{1}{2}) }[/math] liczba [math]\displaystyle{ p }[/math] nie występuje w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze.

Dowód


Przykład A46
Jeżeli [math]\displaystyle{ n \geqslant 8 }[/math] i liczba pierwsza [math]\displaystyle{ p \in \left( {\small\frac{2 n}{5}}, {\small\frac{n}{2}} \right] }[/math], to [math]\displaystyle{ p }[/math] nie występuje w rozwinięciu liczby [math]\displaystyle{ {\small\binom{2 n}{n}} }[/math] na czynniki pierwsze.

Dowód


Uwaga A47
Z przykładu A44 nie wynika, że w przedziale [math]\displaystyle{ \left( {\small\frac{n}{2}}, {\small\frac{2 n}{3}} \right] }[/math] znajduje się choćby jedna liczba pierwsza [math]\displaystyle{ p }[/math]. Analogiczna uwaga jest prawdziwa w przypadku przykładu A46 oraz twierdzeń A43 i A45. Istnienie liczby pierwszej w określonym przedziale będzie tematem kolejnego artykułu.


Przykład A48
Pokazujemy i omawiamy wynik zastosowania twierdzeń A43 i A45 do współczynnika dwumianowego [math]\displaystyle{ {\small\binom{2 \cdot 3284}{3284}} }[/math]. Można udowodnić, że granicę stosowalności obu twierdzeń bardzo dokładnie opisuje warunek [math]\displaystyle{ p \gt \sqrt{2 n} }[/math], co w naszym przypadku daje [math]\displaystyle{ p \gt \sqrt{2 \cdot 3284} \approx 81.04 }[/math].

Pokaż przykład








Przypisy

  1. ↑ Wikipedia, PARI/GP, (Wiki-en)
  2. ↑ Wikipedia, Pafnuty Czebyszew (1821 - 1893), (Wiki-pl), (Wiki-ru)
  3. ↑ P. L. Chebyshev, Mémoire sur les nombres premiers, J. de Math. Pures Appl. (1) 17 (1852), 366-390, (LINK)
  4. ↑ P. Erdos, Beweis eines Satzes von Tschebyschef, Acta Litt. Sci. Szeged 5 (1932), 194-198, (LINK1), (LINK2)
  5. ↑ P. Dusart, The [math]\displaystyle{ k^{th} }[/math] prime is greater than [math]\displaystyle{ k (\ln k + \ln \ln k - 1) }[/math] for [math]\displaystyle{ k \geqslant 2 }[/math], Math. Of Computation, Vol. 68, Number 225 (January 1999), pp. 411-415.
  6. ↑ P. Dusart, Sharper bounds for [math]\displaystyle{ \psi }[/math], [math]\displaystyle{ \theta }[/math], [math]\displaystyle{ \pi }[/math], [math]\displaystyle{ p_k }[/math], Rapport de recherche no. 1998-06, Université de Limoges
  7. ↑ P. Dusart, Estimates of some functions over primes without R.H., (2010), (LINK)
  8. ↑ P. Dusart, Explicit estimates of some functions over primes, Ramanujan Journal. 45 (1) (January 2018) pp. 225-234.
  9. ↑ Wikipedia, Wzór Stirlinga, (Wiki-pl), (Wiki-en)
  10. ↑ Wikipedia, Twierdzenie o zbieżności ciągu monotonicznego, (LINK)
  11. ↑ Skocz do: 11,0 11,1 Wikipedia, Characterizations of the exponential function, (Wiki-en)
  12. ↑ Wikipedia, Cauchy product, (Wiki-en)
  13. ↑ Wikipedia, Szereg (matematyka) - Działania, (Wiki-pl)






 

Źródło: „https://henryk-dabrowski.pl/index.php?title=Twierdzenie_Czebyszewa_o_funkcji_π(n)&oldid=843”