Ciąg EKG, czyli zaskakująca zabawa z teorią liczb

Teoria liczb w wielu miejscach jest zaskakująca i nieprzewidywalna, co – na poziomie elementarnym – objawia się przede wszystkim przez nieregularne i trudne do opisania rozmieszczenie liczb pierwszych w zbiorze liczb naturalnych. Wraz z Piotrem Hofmanem zmierzyliśmy się z tym fenomenem, badając tzw. ciąg EKG: prosty do zdefiniowania, a z bardzo ciekawymi właściwościami.

Ciąg EKG $\text{[math]}$ określamy następująco: $\text{[math]}$ $\text{[math]}$ i dalej $\text{[math]}$ jest najmniejszą liczbą całkowitą dodatnią niewystępującą wcześniej w ciągu, taką że $\text{[math]}$ Jako pierwszy zajmował się tym ciągiem Ayres, następnie badali go Lagarias, Rains i Sloane.

Skąd nazwa ciąg EKG? Pierwsze $\text{[math]}$ wyrazów ciągu nam może tego nie powie:

$1 2 4 6 3 9 12 8 10 5 15 18 14 7 21 24 16 20 22 11 33 27 30 25 35 28 26 13 39 36 32 34 17 51 42 38 19 57 45 40$

ale jeśli narysujemy wykres pierwszych

\text{[math]}

wyrazów (Rys. 1), to zobaczymy coś ciekawego. Nasuwa się pytanie: czemu zawdzięczamy te „skoki” na wykresie, przypominające zachowanie elektrokardiogramu? Prześledzenie wyrazów ciągu EKG pokazuje, że te skoki to trójki kolejnych wyrazów postaci

\text{[math]}

dla liczb pierwszych

\text{[math]}

Lagarias, Rains i Sloane wykazali, między innymi, że ciąg

\text{[math]}

jest permutacją liczb całkowitych dodatnich, że liczby pierwsze pojawiają się w nim w kolejności rosnącej i że asymptotycznie zachowuje się on liniowo (dokładniej,

\text{[math]}

dla każdego

\text{[math]}

). Rysunek 2, pokazujący pierwszych

\text{[math]}

wyrazów ciągu EKG, sugeruje, że powinniśmy potrafić udowodnić dużo dokładniejsze ograniczenia: poza skokami,

\text{[math]}

jest równe prawie dokładnie

\text{[math]}

Oznaczmy

\text{[math]}

jeśli

\text{[math]}

lub

\text{[math]}

dla liczby pierwszej

\text{[math]}

\text{[math]}

w przeciwnym przypadku. Ta definicja „łagodzi” skoki. Spodziewamy się więc, że będzie

\text{[math]}

tj.

\text{[math]}

Bazując na eksperymentach numerycznych, Lagarias, Rains i Sloane postawili następujące hipotezy:

Hipoteza 1. W ciągu EKG każda liczba pierwsza $\text{[math]}$ występuje w trójce $\text{[math]}$

Hipoteza 2. $\text{[math]}$ a dokładniej $\text{[math]}$

Wraz z Piotrem Hofmanem udowodniliśmy pierwszą hipotezę i częściowo drugą: wykazaliśmy, że istnieje taka stała uniwersalna $\text{[math]}$ że

display-math

co oczywiście implikuje $\text{[math]}$ Dowód powyższego oszacowania jest żmudny i wymaga wielu drobnych technicznych kroków. Za to dowód pierwszej hipotezy jest dość krótki i przedstawię go w dalszej części artykułu.

Dowód hipotezy 1. Jeśli $\text{[math]}$ jest liczbą pierwszą dzielącą zarówno $\text{[math]}$ jak i $\text{[math]}$ to $\text{[math]}$ nazywamy liczbą sterującą wyrazu $\text{[math]}$ (to nie jest definicja jednoznaczna, dla jednego $\text{[math]}$ możemy mieć wiele liczb sterujących). Zauważmy, że $\text{[math]}$ jest najmniejszą liczbą niewystępującą wcześniej w ciągu, a podzielną przez $\text{[math]}$ Kluczowe jest następujące spostrzeżenie. Ustalmy liczbę rzeczywistą $\text{[math]}$ Wówczas, dla każdej liczby pierwszej $\text{[math]}$ istnieje co najwyżej jeden taki wyraz ciągu $\text{[math]}$ że $\text{[math]}$ i $\text{[math]}$ jest liczbą sterującą $\text{[math]}$ Istotnie, zauważmy, iż jeśli $\text{[math]}$ jest liczbą sterującą $\text{[math]}$ i $\text{[math]}$ to wszystkie liczby mniejsze od $\text{[math]}$ podzielne przez $\text{[math]}$ wystąpiły wcześniej w ciągu. Czyli jeśli dla pewnego $\text{[math]}$ mamy $\text{[math]}$ to $\text{[math]}$ nie dzieli $\text{[math]}$ a więc nie może być liczbą sterującą $\text{[math]}$ Załóżmy, że pewna liczba pierwsza $\text{[math]}$ pojawia się w ciągu niepoprzedzona wyrazem $\text{[math]}$ czyli $\text{[math]}$ $\text{[math]}$ dla pewnych całkowitych $\text{[math]}$ i $\text{[math]}$ Lagarias, Rains i Sloane udowodnili, że wówczas $\text{[math]}$ jest pierwszym wyrazem ciągu podzielnym przez $\text{[math]}$ W szczególności oznacza to, że $\text{[math]}$ nie wystąpiło w ciągu przed pozycją $\text{[math]}$

Rozpatrzmy zbiory

display-math

Zauważmy, że $\text{[math]}$ gdyż $\text{[math]}$ i $\text{[math]}$ Doprowadzimy do sprzeczności, dowodząc, że jeśli $\text{[math]}$ i $\text{[math]}$ jest wystarczająco duże, to zbiór $\text{[math]}$ jest dużo większy niż $\text{[math]}$ Jak wykazali Lagarias, Rains i Sloane, liczby pierwsze pojawiają się w ciągu EKG w kolejności rosnącej, czyli przed pozycją $\text{[math]}$ nie pojawiła się liczba pierwsza większa niż $\text{[math]}$ Jeśli $\text{[math]}$ jest liczbą sterującą wyrazu $\text{[math]}$ i $\text{[math]}$ to $\text{[math]}$ jest kandydatem na wyraz $\text{[math]}$ więc pojawia się w ciągu na pozycji $\text{[math]}$ lub wcześniejszej. Wnioskujemy stąd, że wszystkie liczby sterujące do pozycji $\text{[math]}$ są mniejsze niż $\text{[math]}$ Z podanego przed chwilą „kluczowego spostrzeżenia” wiemy, że dla każdej liczby pierwszej $\text{[math]}$ istnieje co najwyżej jeden taki indeks $\text{[math]}$ że $\text{[math]}$ i $\text{[math]}$ jest liczbą sterującą $\text{[math]}$ Liczb pierwszych nie większych niż $\text{[math]}$ jest nie więcej niż $\text{[math]}$ dla pewnej stałej uniwersalnej $\text{[math]}$ czyli

display-math

Spójrzmy teraz na zbiór $\text{[math]}$ Niech $\text{[math]}$ będzie liczbą sterującą wyrazu $\text{[math]}$ ; oczywiście $\text{[math]}$ jest dzielnikiem $\text{[math]}$ Wobec tego liczby $\text{[math]}$ dla $\text{[math]}$ musiały pojawić się w ciągu wcześniej. Oznaczmy

display-math

Indeksy wszystkich parzystych wyrazów postaci $\text{[math]}$ (podzielnych przez 4, jeśli $\text{[math]}$ ), większych od $\text{[math]}$ należą do $\text{[math]}$ wobec tego

display-math

Z drugiej strony, jeśli $\text{[math]}$ to $\text{[math]}$ jest potencjalnym kandydatem na wyraz $\text{[math]}$ czyli $\text{[math]}$ Mamy więc $\text{[math]}$ zatem

display-math

Wobec tego dla odpowiednio dużych $\text{[math]}$ mamy $\text{[math]}$ Wyliczywszy dokładnie stałe w powyższym rozumowaniu, można dowieść, że $\text{[math]}$ już dla $\text{[math]}$ Teza dla mniejszych wartości $\text{[math]}$ została sprawdzona numerycznie przez Lagariasa, Rainsa i Sloane’a, więc hipoteza została udowodniona dla wszystkich $\text{[math]}$