Afiliacja: Instytut Informatyki, Uniwersytet Warszawski; Max Planck Institute for Software Systems, Kaiserslautern
W niniejszym artykule będziemy przyglądać się tzw. funkcji Collatza, która jest zdefiniowana następująco. Dla liczby naturalnej \(n,\) \[c(n) \coloneqq \begin{cases} 3n+1 & \text{jeśli } n \text{ jest nieparzyste,} \\ \frac{n}{2} & \text{jeśli } n \text{ jest parzyste.} \end{cases}\] Dla wygody \(i\)-krotne złożenie funkcji Collatza będziemy oznaczać przez \(c^i,\) przykładowo \(c^2(5) = 8.\) Funkcję Collatza można iterować dowolnie wiele razy, bo dla dowolnego naturalnego \(n\) mamy \(c(n) \geq 1.\) Na przykład dla \(n = 5\) ciąg Collatza to \(5, 16, 8, 4, 2, 1, 4, 2, 1, \ldots,\) cykl \((4, 2, 1)\) powtarza się tu w nieskończoność. Na rysunku 1 możemy zobaczyć więcej przykładów.
Na przykład \(c(5) = 16\) oraz \(c(16) = 8.\)
19 9 58 28 29 14 15 88 7 7 46 44 22 22 23 22 11 11 11 70 11 34 34 34 35 34 17 17 17 106 17 17 52 52 52 53 52 52 26 26 26 160 26 26 13 13 13 13 80 13 13 40 40 40 40 40 40 40 20 20 20 20 20 20 20 21 10 10 10 10 10 10 10 64 5 5 5 5 5 5 5 32 16 16 16 16 16 16 16 16 8 8 8 8 8 8 8 8 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) Rys. 1. Ciągi Collatza dla wybranych wartości początkowych
W świetle tych przykładów wydaje się, że startując z dowolnej liczby, w końcu osiągniemy cykl \((4, 2, 1).\) To jest dokładnie Hipoteza Collatza. Formalnie rzecz biorąc, hipoteza ta mówi, że dla dowolnej liczby \(n\) istnieje \(k\) takie, że \(c^k(n) = 1.\)
Udowodnienie hipotezy Collatza jest jednym ze sławnych problemów otwartych w matematyce. Hipotezę przypisuje się przede wszystkim Lotharowi Collatzowi (1937), jednak istnieje kilka twierdzeń powiązanych z jej pierwotnym autorem. W związku z tym hipoteza funkcjonuje pod wieloma nazwami, takimi jak: ciąg liczb gradowych, problem \((3n+1)\), problem syrakuzjański, hipoteza Thwaitesa, hipoteza Ulama czy hipoteza Kakutaniego.
Opóźnieniem liczby \(n\) nazwiemy liczbę iteracji funkcji Collatza przed zbiegnięciem do 1, oznaczamy je \(d(n).\) Precyzyjnie: \(d(n)\) to najmniejsze \(k\) takie, że \(c^k(n) = 1.\) Przykładowo \(d(5) = 5.\) Łatwo zauważyć, że \(d(2n) = d(n) + 1,\) bo \(2n\) jest zawsze parzyste. Co ciekawe, nawet małe wartości startowe mogą mieć olbrzymie opóźnienia: ciąg Collatza startujący z \(n = 27\) osiąga po drodze 9232, nim ostatecznie trafi do 1 po \(d(27) = 111\) iteracjach. Liczba \(n\) jest rekordem opóźnienia, jeśli jej opóźnienie \(d(n)\) jest większe niż opóźnienie każdej liczby mniejszej niż \(n.\) Dla przykładu 7 jest rekordem opóźnienia, bo opóźnienia 1, 2, 3, 4, 5 i 6 są mniejsze niż \(d(7) = 16.\) Tabelę rekordów opóźnienia możemy zobaczyć na rysunku 2.
\(n\) \(d(n)\) maks. 1 0 1 2 1 2 3 7 16 6 8 16 7 16 52 9 19 52 18 20 52 23 25 160 27 111 9232 54 112 9232 73 115 9232 97 118 9232 129 121 9232 \(\vdots\) \(\vdots\) \(\vdots\) 871 178 190996 1161 181 190996 \(\vdots\) \(\vdots\) \(\vdots\) 6171 261 975400 10971 267 975400 \(\vdots\) \(\vdots\) \(\vdots\) 77031 350 21933016 106239 353 104674192 \(\vdots\) \(\vdots\) \(\vdots\) 837799 524 2974984576 Rys. 2. Wybrane rekordy opóźnienia oraz maksymalne wartości ich ciągów Collatza, dla \(n < 2^{20}\)
Zaskakująca natura funkcji Collatza, która objawia się podobieństwami pomiędzy ciągami Collatza na rysunku 1 oraz wydaje się losowymi wartościami opóźnień na rysunku 2, sugeruje, że udowodnienie hipotezy Collatza nie będzie proste! Faktycznie, wielu znanych matematyków pracowało nad tym problemem, sporo już wiemy, ale pełny dowód nie został (jeszcze) znaleziony. Jeffrey Lagarias, znawca hipotezy Collatza, mówi: To jest wyjątkowo trudny problem, zupełnie poza zasięgiem dzisiejszej matematyki. Może bardziej znane jest powiedzenie Paula Erdősa, który zapytany o hipotezę Collatza odpowiedział: Matematyka nie jest jeszcze gotowa na takie problemy.
Tak jak przy każdym problemie otwartym, mamy dwie naturalne linie ataku: udowodnić hipotezę lub ją obalić. W pozostałej części tego artykułu skupimy się na twierdzeniach i argumentach, które wspierają tezę, że hipoteza jest prawdziwa. Nim to jednak zrobimy, rozważmy możliwość istnienia kontrprzykładu. Są dwa potencjalne typy kontrprzykładów. Pierwszy typ to jakiś cykl, który nie jest trywialnym cyklem \((4,2,1),\) a drugi typ to ciąg Collatza, który jest rozbieżny do nieskończoności. Hipoteza Collatza była intensywnie sprawdzana przez komputerowe testy. Od maja 2025 roku wiadomo, że dla wszystkich startowych \(n \leq 2^{71}\) ciąg Collatza rzeczywiście osiąga \(1.\) Jeśli chodzi o cykle, to pokazano, że o ile istnieje jakiś nietrywialny cykl będący kontrprzykładem, to jego długość musi wynosić co najmniej \({355\,504\,839\,929 \approx 2^{38}}.\) Jak widać dane sugerują, że zapewne hipoteza Collatza faktycznie jest prawdziwa!
Nim pójdziemy dalej, wprowadźmy zmodyfikowaną wersję funkcji Collatza: \[s(n) \coloneqq \begin{cases} \frac{3n+1}{2} & \text{jeśli } n \text{ jest nieparzyste,} \\ \frac{n}{2} & \text{jeśli } n \text{ jest parzyste.} \end{cases}\] Ta definicja jest zasadniczo równoważna oryginalnej wersji funkcji Collatza. Jeśli \(n\) jest nieparzyste, to \(3n+1\) musi być parzyste, a więc po każdym kroku zastosowanym do liczby nieparzystej następuje krok \(\frac{n}{2}.\)
Wyobraźmy sobie na chwilę, że weryfikujemy hipotezę i sprawdziliśmy już, że dla wszystkich \(n \leq 1000\) ciąg Collatza osiąga 1. Teraz chcemy zobaczyć, co się dzieje dla \(n = 1001.\)
Szybowania są bardzo przydatne w praktyce. Powiedzmy, że sprawdziliśmy hipotezę Collatza aż do \(n-1.\) Jak omówiliśmy powyżej, jeśli istnieje \(k\) takie, że \(s^k(n) \in \{1, \ldots, n-1\},\) to wówczas dla \(n\) ciąg również zbiega do 1. Jak widać więc, procedura testująca po prawej jest o wiele bardziej efektywna niż ta po lewej.
Zauważmy, że nie musimy pracowicie liczyć, że \(s(1001) = 1502,\) \(s(1502) = 751,\) \(s(751) = 1127,\) … aż napotkamy 1, bo wystarczy, że ciąg zejdzie poniżej 1001. Wtedy już wiemy, że w końcu osiągnie 1, tak jak dla wszystkich liczb \(n \leq 1000.\) Korzystając z tej obserwacji, zdefiniujmy szybowanie liczby \(n,\) oznaczane przez \(g(n),\) jako liczbę iteracji, do czasu gdy zmodyfikowany ciąg Collatza \(s^k(n)\) spadnie poniżej początkowej wartości. Formalnie \(g(n)\) to najmniejsza liczba \(k\) taka, że \(s^k(n) < n.\) Przykładowo wystarczą tylko dwie iteracje zmodyfikowanej funkcji Collatza dla \(n = 1001,\) aby osiągnąć 751, więc \(g(1001) = 2.\) Na marginesie możemy zobaczyć, jak użyć pojęcia szybowania do bardziej efektywnego testowania hipotezy Collatza.
Co prawda dane wskazują na to, że hipoteza Collatza jest prawdziwa, ale dowodu wciąż nie ma. Znane jest natomiast zbliżone twierdzenie, które używa frazy „prawie wszystkie”. Konkretnie: w roku 1976 Rino Terras udowodnił, że prawie wszystkie liczby naturalne mają skończone szybowanie. Rozszyfrujmy najpierw sformułowanie „prawie wszystkie”. Oznacza ono, że gdy \(N\) rośnie do nieskończoności, to frakcja ciągów Collatza startujących z \(n \leq N,\) które spadają poniżej startowej wartości, dąży do 1. Bardziej precyzyjnie, \[\lim_{N \to \infty} \frac{ |\{ n \text{ takie, że } n \leq N \text{ oraz } g(n) < \infty\}|}{N} = 1.\] Żeby zobaczyć, dlaczego twierdzenie Terrasa jest ważne, przyjrzyjmy się, co by się stało, gdybyśmy usunęli frazę „prawie” i udowodnili silniejsze sformułowanie: „wszystkie liczby naturalne mają skończone szybowanie”. Mając taki fakt, byłoby już łatwo udowodnić hipotezę Collatza przez indukcję. Przypuśćmy, że wszystkie ciągi Collatza zaczynające się liczbami \(1, \ldots, n\) zbiegają do 1. Dzięki wzmocnionej wersji twierdzenia Terrasa wiemy, że \(n+1\) ma skończone szybowanie. A zatem istnieje \(k\) takie, że \(s^k(n+1) \leq n.\) To jednak oznacza, że ciąg Collatza zaczynający się w \(n+1\) po \(k\) krokach osiągnie liczbę z zakresu \(1, \ldots, n,\) a więc ostatecznie również zbiegnie do 1. Skoro to wzmocnienie jest równoważne hipotezie Collatza, to pozostańmy przy rozważaniu oryginalnej wersji twierdzenia Terrasa. Dla jasności: nie wiadomo nic o tym, żeby twierdzenie Terrasa implikowało hipotezę Collatza.
W pozostałej części artykułu naszkicujemy dowód twierdzenia Terrasa. Na początek rozważmy pięć pierwszych elementów zmodyfikowanego ciągu Collatza startującego z \(19,\) są to: \(19, 29, 44, 22, 11.\) Jego ciąg parzystości to ciąg zer i jedynek odpowiadający parzystościom odpowiednich wyrazów: \(\mathbf{p}_5 = (1, 1, 0, 0, 1).\) Liczba \(5\) odpowiada długości ciągu parzystości. Zaobserwujmy najpierw dwa eleganckie fakty na temat ciągów parzystości.
niep. 19 51 83 115 147 179 niep. 29 77 125 173 221 269 parz. 44 116 188 260 332 404 parz. 22 58 94 130 166 202 niep. 11 29 47 65 83 101 ??? 17 44 71 98 125 152 \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) Przykład dla pierwszego faktu, \(k = 5\) i \(b = 19.\) Następujące liczby mają te same ciągi parzystości w pierwszych pięciu krokach (patrz tabela powyżej). \[\begin{aligned} 2 0\cdot 2^5+19 & = 19, \ \ \ & 1\cdot 2^5+19 & = 51, \\ 2\cdot 2^5+19 & = 83, \ \ \ & 3\cdot 2^5+19 & = 115, \\ 4\cdot 2^5+19 & = 147,\ \ \ & 5\cdot 2^5+19 & = 179. \end{aligned}\]
Pierwszy fakt mówi, że jeśli \(b\) ma ustaloną wartość, to wszystkie ciągi startujące w liczbach \(0\cdot 2^k +b, 1\cdot2^k + b, 2\cdot2^k + b, 3\cdot2^k+b, \ldots\) mają te same ciągi parzystości \(\mathbf{p}_k\) długości \(k\) (patrz przykład na marginesie). Drugi fakt mówi, że dla każdego ciągu parzystości \(\mathbf{p}_k\) długości \(k\) istnieje liczba \(n\) z ciągiem parzystości równym dokładnie \(\mathbf{p}_k\) (patrz margines). Oba fakty mogą być stosunkowo nietrudno wykazane przez indukcję, ale teraz zajmiemy się ciekawszymi sprawami.
Drugi fakt mówi nam, że wszystkie ciągi parzystości są możliwe. Na przykład łatwo zauważyć, że \((0, 0, 0, 0, 0)\) jest ciągiem parzystości dla liczby \(32\): \(32, 16, 8, 4, 2.\) Natomiast znalezienie ciągu o parzystości \((1, 1, 1, 1, 1)\) jest mniej oczywiste, ale on również istnieje i zaczyna się od liczby \(31\): \(31, 47, 71, 107, 161.\)
Łącząc oba fakty, uzasadnimy następującą obserwację. Niech \(n\) oraz \(n'\) będą dwoma startowymi liczbami i niech \(\mathbf{p}_k\) oraz \(\mathbf{p}'_k\) będą ciągami parzystości długości \(k\) odpowiednio dla liczb \(n\) oraz \(n'.\) Wówczas \(\mathbf{p}_k = \mathbf{p}'_k\) wtedy i tylko wtedy, gdy różnica \(n - n'\) jest podzielna przez \(2^k.\) Po pierwsze, jeśli \(n-n'\) jest podzielne przez \(2^k,\) to mamy \(n = a 2^k + b\) oraz \(n' = a' 2^k + b\) dla pewnych \(a, a', b \in \mathbb N\) i wówczas z pierwszego faktu wynika, że istotnie \(\mathbf{p}_k = \mathbf{p}'_k.\) Z drugiej strony dla każdego ciągu parzystości istnieje liczba startowa, która daje ten ciąg parzystości. Ponieważ jest \(2^k\) różnych ciągów parzystości długości \(k\) oraz \(2^k\) różnych reszt modulo \(2^k\) (tzn. wyborów wartości \(b\)), to musi istnieć bijekcja pomiędzy ciągami parzystości a resztami. A zatem, jeśli \(n\) oraz \(n'\) mają te same ciągi parzystości, to \(n\) oraz \(n'\) muszą mieć równe reszty modulo \(2^k.\)
Będziemy teraz przybliżać zmodyfikowany ciąg Collatza. Przyjrzyjmy się przykładowi dla ciągu parzystości \((1,1,0,0,1).\) Po pierwszym kroku wartość \({n = 19}\) wzrosła do \(\frac{3n+1}{2} = 29,\) a po drugim wzrosła ponownie do \(\frac{9n+5}{4} = 44.\) Następnie dwa razy zmalała dwukrotnie do \(\frac{9n+5}{8} = 22\) oraz \(\frac{9n+5}{16} = 11.\) Ostatecznie wartość wzrosła do \(\frac{27n+31}{32} = 17.\) Możemy przybliżyć z dołu wartość zmodyfikowanego ciągu Collatza, ignorując stałe wartości w licznikach.
Ponieważ usunęliśmy jedynie stałe wartości w licznikach, to ta aproksymacja przybliża prawdziwą wartość z dobrą dokładnością. Powiemy, że ciąg parzystości \(\mathbf{p}_k\) jest zbieżny, jeśli przybliżony ciąg Collatza spada poniżej wartości początkowej. Precyzyjniej mówiąc, jeśli istnieje taki prefiks \(\mathbf{p}_k\) długości \(\ell,\) o \(d\) nieparzystych krokach, że \(3^d < 2^\ell,\) to \(\mathbf{p}_k\) jest zbieżny. Dla liczby \(n\) o zbieżnym ciągu parzystości \(\mathbf{p}_k\) mówimy, że minimalne \(\ell \leq k\) takie, że \(3^d < 2^\ell,\) jest przybliżonym szybowaniem dla \(n,\) oznaczamy je \(\widetilde{g}(n).\)
Żeby zobaczyć, dlaczego ciąg parzystości \((1, 1, 0, 0, 1)\) zbiega, rozważmy prefiks \((1, 1, 0, 0),\) który ma \(d=2\) nieparzyste kroki spośród \(\ell = 4.\) Przybliżoną wartością \(s^4(n)\) jest \(\frac{3^2 n}{2^4}.\) Ponieważ \(3^2 < 2^4,\) to przybliżona wartość spadła poniżej startowej wartości, czyli \(\frac{3^2 n}{2^4} < n.\) A zatem również dla każdego \(n\) o tym ciągu parzystości przybliżone szybowanie wynosi \(4\) (\(\tilde{g}(n) = 4\)).
Przybliżone szybowanie okazuje się całkiem dokładne. Przyjrzyjmy się ciągowi parzystości \(\mathbf{p}_k,\) który zbiega w \(k\)-tym kroku. Ponieważ zbiega on w ostatnim kroku, to dowolna liczba \(n\) o tym ciągu parzystości spełnia \(\widetilde{g}(n) = k.\) Pokażemy teraz, że dla dużych liczb \(n\) o ciągu parzystości \(\mathbf{p}_k\) szybowanie oraz przybliżone szybowanie są równe.
Przybliżone szybowanie jest tak dokładne, że nawet nie jest znana liczba \(n\) taka, że \(g(n) \neq \tilde{g}(n).\) Co więcej, stawiana jest hipoteza, że zawsze \(\tilde{g}(n)\) jest równe \(g(n)\)!
Po pierwsze \(g(n) \geq \widetilde{g}(n).\) Przypomnijmy, że przybliżona wartość zmodyfikowanej funkcji Collatza nigdy nie jest większa niż wartość zmodyfikowanej funkcji Collatza. A zatem jeśli \(\widetilde{g}(n) = k,\) to wartości przybliżonego ciągu są powyżej \(n\) przez \(k-1\) pierwszych kroków, a więc również i prawdziwe wartości zmodyfikowanego ciągu Collatza są powyżej \(n\) przez \(k-1\) pierwszych kroków. A to oznacza, że \(g(n) \geq k.\)
Z drugiej strony pokażemy, że \(g(n) \leq \widetilde{g}(n).\) Jeśli \(\widetilde{g}(n) = k,\) to wiemy, że \(k\)-ty krok przybliżonego ciągu, czyli \(\frac{3^d n}{2^k},\) schodzi poniżej wartości \(n,\) a więc \(\frac{3^d}{2^k} < 1.\) Wiemy, że istnieje stała \(C\) taka, że \(s^k(n) = \frac{3^d n + C}{2^k}\) (np. dla \(n= 19\) stała \(C\) wynosi \(31\)). A zatem różnica między wartością \(s^k(n)\) a jej przybliżoną wartością jest stałą, która nie zależy od \(n\): \[s^k(n) - \frac{3^d n}{2^k} = \frac{3^d n + C}{2^k} - \frac{3^d n}{2^k} = \frac{C}{2^k}.\] Spójrzmy teraz na różnicę pomiędzy przybliżoną wartością zmodyfikowanej funkcji Collatza po \(k\) krokach a początkową wartością \(n\): \(n - \frac{3^d n}{2^k} = n (1 - \frac{3^d}{2^k}).\) Ponieważ \(\frac{3^d}{2^k} < 1,\) więc oczywiście \(1 - \frac{3^d}{2^k} > 0.\) Dla każdej stałej \(C' \geq 0\) istnieje dostatecznie duże \(n\) takie, że \(n - \frac{3^d n}{2^k} > C'.\) A zatem dla \(C' = \frac{C}{2^k}\) otrzymujemy, że dla dostatecznie dużych \(n\) zachodzi: \[s^k(n) = \frac{3^d n}{2^k} + \frac{C}{2^k} < n.\] To oznacza, że dla takich \(n\) szybowanie \(g(n)\) jest równe przybliżonemu szybowaniu \(\widetilde{g}(n).\) Na marginesie przedstawiamy przykład dla \(n=19.\)
Wiemy, że dla każdego \(n\) o ciągu parzystości \((1,1,0,0,1)\) zachodzi \(s^5(n) = \frac{3^3n+31}{2^5}.\) Pytamy, kiedy \(s^5(n) < n.\) Jest to równoważne \(\frac{3^3n+31}{2^5} < n,\) czyli również \(n > \frac{31}{5} = 6{,}2.\) A więc dla wszystkich \(n > 6{,}2\) przybliżone szybowanie \(n\) jest równe szybowaniu \(n.\) Ponieważ \(19\) ma taki właśnie ciąg parzystości oraz \(19 > 6{,}2,\) to \(g(19) = \tilde{g}(19).\)
Ponieważ dla każdego ciągu parzystości \(\mathbf{p}_k\) istnieje próg, powyżej którego szybowanie oraz przybliżone szybowanie są równe, to w szczególności dla ustalonego ciągu parzystości istnieje jedynie skończenie wiele liczb \(n\) o tym ciągu parzystości, dla których \(g(n)\) jest różne od \(\widetilde{g}(n).\)
długość \(k\) #zbieżnych %zbieżnych 1 1 50 2 3 75 3 6 75 4 13 81.25 5 28 87.5 6 56 87.5 7 115 89.84 8 237 92.58 9 474 92.58 10 960 93.75 \(\vdots\) \(\vdots\) ⋮ 20 1 021 248 97.39 \(\vdots\) \(\vdots\) ⋮ 30 1 060 970 550 98.81 Rys. 3. Liczba oraz frakcja (zaokrąglona do 2 cyfr po przecinku) zbieżnych ciągów parzystości. Zauważmy, że jest \(2^k\) ciągów parzystości długości \(k\)
Uzasadnimy teraz, że prawie wszystkie ciągi parzystości są zbieżne. Rysunek 3 pokazuje frakcję zbieżnych ciągów parzystości dla różnych długości ciągu. Zauważmy, że jeśli ciąg parzystości \(\mathbf{p}_k\) zawiera taką samą liczbę parzystych i nieparzystych kroków, to jest zbieżny. Wynika to z faktu, że każdy parzysty krok mnoży liczbę \(n\) przez \(1/2,\) a każdy nieparzysty krok przez \(3/2,\) więc jeśli w ciągu będzie \(k\) kroków parzystych i \(k\) nieparzystych, to ostateczna wartość wyniesie \(\frac{3^k}{2^{2k}} n = \frac{3^k}{4^k} n < n.\) Można też na sprawę spojrzeć nieco inaczej: okazuje się, że losowo wybrany ciąg parzystości prawdopodobnie jest zbieżny. Żeby ciąg parzystości długości \(k\) nie był zbieżny, to musi on zawierać przynajmniej \({d \geq \frac{k}{\log_2(3)} > 0{,}6 k}\) nieparzystych kroków. Jest tak dlatego, że po \(k-d\) parzystych
krokach i \(d\) nieparzystych krokach przybliżona wartość wynosi \(\frac{3^d n}{2^k}.\) A więc żeby \(\frac{3^d n}{2^k} \geq n\) zachodziło, to liczba nieparzystych kroków musi spełniać \(d \geq \frac{k}{\log_2(3)}.\) Możemy teraz zastosować nierówność Chernoffa, żeby zaargumentować, że prawie wszystkie ciągi parzystości zawierają mniej niż \(\frac{k}{\log_2(3)}\) nieparzystych kroków. Tak naprawdę użyjemy uproszczonej wersji nierówności Chernoffa, którą można sformułować następująco: dla dowolnego \(0 < \alpha \leq \frac{1}{2}\) prawdopodobieństwo, że na \(k\) rzutów uczciwą monetą wypadnie co najmniej \({(\frac{1}{2} + \alpha) k}\) orłów, wynosi co najwyżej \(e^{-2\alpha^2 k}.\) Ponieważ \({\frac{1}{\log_2(3)} - \frac{1}{2} > 0{,}1},\) to możemy wziąć \(\alpha = 0{,}1\) i dostajemy, że prawdopodobieństwo, że losowy ciąg parzystości długości \(k\) jest zbieżny z prawdopodobieństwem co najmniej \({1 - e^{-2(0,1)^2 k} = 1 - e^{-\frac{k}{50}}}.\) Dla \(k\) dążącego do nieskończoności to prawdopodobieństwo dąży do \(1,\) czyli faktycznie prawie wszystkie ciągi parzystości są zbieżne.
Podsumujmy teraz i połączmy w całość wszystkie kawałki dowodu twierdzenia Terrasa. Pokazaliśmy właśnie, że frakcja ciągów parzystości \(\mathbf{p}_k,\) które nie zbiegają, dąży do zera, gdy długość \(k\) dąży do nieskończoności. Przypomnijmy, że jeśli \(\mathbf{p}_k\) jest zbieżny, to wtedy wszystkie liczby \(n\) o tym ciągu parzystości spełniają \(\widetilde{g}(n) \leq k < \infty.\) Dodatkowo wiemy z poprzednich rozważań, że dla danego ciągu parzystości istnieje tylko skończenie wiele liczb \(n\) takich, że \(g(n) \neq \widetilde{g}(n).\) Łącząc te fakty, możemy wywnioskować, że dla prawie wszystkich \(n\) zachodzi \(g(n) = \widetilde{g}(n) < \infty.\) Innymi słowy, prawie wszystkie liczby mają skończone szybowanie.
Okazuje się, że znane są nawet wyniki silniejsze niż twierdzenie Terrasa. Dwa tego typu twierdzenia mówią, że minimalna wartość ciągu Collatza \(n, c(n), c^2(n), \ldots\) jest prawie zawsze równa co najwyżej \(n^\theta.\) Zauważmy, że jeśli \(\theta < 1,\) to wtedy \(n^\theta < n,\) czyli szybowanie \(n\) jest skończone. Pierwsze z tych twierdzeń udowodnił Allouche (w roku 1979) dla \(\theta \approx 0{,}8691.\) Następnie wynik ten poprawił Korec (w roku 1994) dla \(\theta \approx 0{,}7924.\) Niedawno, w 2019 roku, Terrence Tao udowodnił podobny rezultat: dla dowolnej funkcji \(f: \mathbb{N} \to \mathbb{R}_+\) takiej, że \(f(n)\) dąży do nieskończoności przy \(n\) rosnącym do nieskończoności, minimalna wartość ciągu Collatza startującego z \(n\) jest prawie zawsze\(^*\) mniejsza niż \(f(n).\) A więc wybierzmy naszą ulubioną funkcję, która dąży do nieskończoności – może to być przykładowo \(\log(\log(\log(n)))\) – i wówczas wiemy, że prawie wszystkie liczby \(n\) osiągają wartość mniejszą niż \(\log(\log(\log(n))),\) imponujące!
\(^*\)Pewną wadą wyniku Tao jest to, że „prawie wszystkie” jest tu używane zgodnie z logarytmicznym rozkładem miary, a nie typowym, naturalnym rozkładem.
Chociaż wydaje się, że już jesteśmy „prawie na miejscu”, to jednak luka pomiędzy twierdzeniami Terrasa, Allouche’a, Koreca czy Tao a udowodnieniem hipotezy Collatza wydaje się wymagać istotnie nowego podejścia, spostrzeżeń i pomysłów. Nie wiadomo, czy któreś ze wspomnianych twierdzeń może być użyte do dowodu, że prawie wszystkie liczby startowe mają skończone opóźnienie. Przypomnijmy, że opóźnienie to liczba kroków do czasu osiągnięcia \(1,\) w odróżnieniu od szybowania, które jest liczbą kroków do osiągnięcia liczby mniejszej niż startowa. Nawet jeśli ktoś pokazałby, że prawie wszystkie liczby startowe mają skończone opóźnienie, to wciąż nie wiadomo byłoby, czy rzeczywiście wszystkie (a nie prawie wszystkie) liczby startowe mają skończone opóźnienie. Inaczej mówiąc, nawet jeśli pokażemy wersję hipotezy Collatza dla „prawie wszystkich liczb”, to wciąż pozostaje sporo pracy do udowodnienia pełnej hipotezy Collatza. A swoją drogą, jest całkiem możliwe, że w ogóle hipoteza Collatza jest fałszywa, a odkrycie minimalnego kontrprzykładu tuż za rogiem!
Przetłumaczone z języka angielskiego przez Wojciecha CZERWIŃSKIEGO