Zadziwiające zachowanie sekwencji rekurencyjnych | Magazyn Quanta

W matematyce proste zasady mogą odblokować wszechświaty złożoności i piękna. Weźmy słynny ciąg Fibonacciego, który definiuje się następująco: zaczyna się od 1 i 1, a każda kolejna liczba jest sumą dwóch poprzednich. Kilka pierwszych liczb to:

1, 1, 2, 3, 5, 8, 13, 21, 34…

To prawda, jest prosty, ale z tego niepozornego przepisu wynika wzór o dalekosiężnym znaczeniu, który wydaje się być wpleciony w samą tkankę świata przyrody. Widać to po okółkach muszli łodzików, kościach naszych palców i układzie liści na gałęziach drzew. Jej matematyczny zasięg obejmuje między innymi geometrię, algebrę i prawdopodobieństwo. Osiem wieków od wprowadzenia tej sekwencji na Zachód — indyjscy matematycy badali ją na długo przed Fibonacciem — liczby nadal cieszą się zainteresowaniem badaczy, co świadczy o tym, jak wielka matematyczna głębia może kryć się za nawet najbardziej elementarną sekwencją liczbową.

W ciągu Fibonacciego każdy termin opiera się na terminach poprzedzających. Takie sekwencje rekurencyjne mogą wykazywać szeroki zakres zachowań, niektóre cudownie sprzeczne z intuicją. Weźmy na przykład osobliwą rodzinę ciągów opisaną po raz pierwszy w latach 1980. XX wieku przez amerykańskiego matematyka Michał Somos.

Podobnie jak ciąg Fibonacciego, ciąg Somosa zaczyna się od serii jedynek. Somos-k sekwencja zaczyna się od k z nich. Każdy nowy termin Somos-k sekwencję definiuje się poprzez sparowanie poprzednich wyrazów, pomnożenie każdej pary przez siebie, dodanie par, a następnie podzielenie przez wyraz k pozycje z powrotem w sekwencji.

Sekwencje nie są zbyt interesujące, jeśli k równa się 1, 2 lub 3 — są to tylko serie powtarzających się liczb. Ale dla k = 4, 5, 6 lub 7, sekwencje mają dziwną właściwość. Mimo że zachodzi wiele podziałów, ułamki nie pojawiają się.

„Zwykle nie mamy do czynienia z tego rodzaju zjawiskiem” – powiedział Somos. „To zwodniczo prosty powrót, podobny do Fibonacciego. Ale za tą prostotą kryje się wiele.”

Inni matematycy nadal odkrywają zaskakujące powiązania między ciągami Somosa a pozornie niezwiązanymi dziedzinami matematyki. Wykorzystuje je jeden z artykułów opublikowanych w lipcu konstruować rozwiązania po układ równań różniczkowych wykorzystywanych do modelowania wszystkiego, od interakcji drapieżnik-ofiara po fale przemieszczające się w plazmie wysokoenergetycznej. Wykorzystuje się je także do badania struktury obiektów matematycznych tzw algebry skupień i są połączone krzywe eliptyczne - które były kluczem do złamania Ostatniego Twierdzenia Fermata.

Janice Malouf, absolwent Uniwersytetu Illinois, opublikował pierwszy dowód na istnienie sekwencji Somos-4 i Somos-5 są integralne (co oznacza, że ​​wszystkie ich terminy są liczbami całkowitymi) w 1992 r. Inne dowody tego samego wyniku przez różnych matematyków pojawił się mniej więcej w tym samym czasie, wraz z dowodami na to, że ciągi Somos-6 i Somos-7 są całkowe.

Ta dziwna właściwość ciągów Somosa zdumiała matematyków. „Sekwencje Somosa zaintrygowały mnie, gdy tylko się o nich dowiedziałem” – powiedział Jamesa Proppa, profesor matematyki na Uniwersytecie Massachusetts w Lowell. „Fakt, że Somos-4 do Somos-7 zawsze podaje liczby całkowite, bez względu na to, jak daleko się posuniesz, wydawał się cudem, gdy patrzyłeś na wszystko z naiwnej perspektywy. Potrzebna była więc inna perspektywa.”

Propp znalazł nową perspektywę na początku XXI wieku, kiedy wraz z kolegami odkrył, że liczby w sekwencji Somos-2000 w rzeczywistości coś zliczają. Terminy w sekwencji odpowiadają strukturom występującym na niektórych grafach. W przypadku niektórych grafów możliwe jest łączenie wierzchołków (kropek) z krawędziami (liniami) w taki sposób, że każdy wierzchołek jest połączony z dokładnie jednym innym wierzchołkiem — nie ma wierzchołków niesparowanych ani wierzchołków połączonych z więcej niż jedną krawędzią. Terminy w sekwencji Somos-4 liczą liczbę różnych doskonałych dopasowań dla określonej sekwencji grafów.

Odkrycie nie tylko dało nowe spojrzenie na sekwencje Somosa, ale także wprowadziło nowe sposoby myślenia i analizowania transformacji grafów. Propp i jego uczniowie uczcili wynik, umieszczając go na a Koszulka.

„Duża część uroku matematyki polega na tym, że różnymi ścieżkami docierasz do tego samego celu i wydaje ci się, że dzieje się coś cudownego lub głębokiego” – powiedział Propp. „Fajną rzeczą w tych ciągach jest to, że istnieją różne punkty widzenia, które wyjaśniają, dlaczego otrzymujesz liczby całkowite. Tam są ukryte głębiny.”

Historia zmienia się w przypadku sekwencji Somos o wyższych numerach. Pierwsze 18 wyrazów Somos-8 to liczby całkowite, ale 19-ty wyraz to ułamek. Każda następna sekwencja Somosa zawiera również wartości ułamkowe.

Inny typ ciągu, opracowany przez niemieckiego matematyka Fritza Göbela w latach 1970. XX wieku, stanowi interesujący kontrapunkt dla ciągów Somosa. The nwyraz ciągu Göbela definiuje się jako sumę kwadratów wszystkich poprzednich wyrazów plus 1 podzieloną przez n. Podobnie jak sekwencje Somosa, sekwencja Göbela obejmuje dzielenie, więc możemy się spodziewać, że wyrazy nie pozostaną liczbami całkowitymi. Ale przez chwilę – w miarę jak sekwencja staje się ogromna – wydaje się, że tak jest.

Dziesiąty wyraz ciągu Göbela wynosi około 10 miliona, jedenasty 1.5 – jakiś miliard. 11. wyraz jest o wiele za duży, aby go obliczyć — ma około 267 miliardów cyfr. Ale w 43 roku holenderski matematyk Henryk Lenstra pokazało, że w przeciwieństwie do pierwszych 42 wyrazów, ten 43. wyraz nie jest liczbą całkowitą.

Sekwencje Göbela można uogólnić, zastępując kwadraty sumy kostkami, czwartymi potęgami lub nawet wyższymi wykładnikami. (Zgodnie z tą konwencją jego pierwotna sekwencja nazywana jest sekwencją 2-Göbela.) Sekwencje te również wykazują zaskakującą tendencję rozpoczynania od rozszerzonego odcinka wyrażeń całkowitych. W 1988 roku Henryk Ibstedt pokazał że pierwsze 89 wyrazów ciągu 3-Göbela (w którym zamiast kwadratów używa się sześcianów) jest liczbami całkowitymi, ale 90. nie. Późniejsze badania innych sekwencji Göbela wykazały jeszcze dłuższe odcinki. Na przykład sekwencja 31-Göbela rozpoczyna się od aż 1,077 wyrazów całkowitych.

W lipcu matematycy z Uniwersytetu Kiusiu, Rinnosuke Matsuhira, Toshikiego Matsusaki i Koki Tsuchida udostępnił papier pokazując to dla A k-Sekwencja Göbela, bez względu na wybór k, pierwsze 19 wyrazów ciągu jest zawsze liczbami całkowitymi. Do zbadania tej kwestii zainspirowała ich japońska manga pt Seisū-tan, co można przetłumaczyć jako „Opowieść o liczbach całkowitych”. A ramka w komiksie poprosił czytelników o obliczenie minimalnej możliwej wartości N_k, moment, w którym a k-Sekwencja Göbela przestaje dawać wyrazy całkowite. Trzej matematycy postanowili odpowiedzieć na to pytanie. „Nieoczekiwane utrzymywanie się liczb całkowitych przez tak długi czas jest sprzeczne z naszą intuicją” – powiedział Matsusaka. „Kiedy zjawiska zachodzą wbrew intuicji, uważam, że zawsze jest w nich piękno”.

Znaleźli wzór powtarzającego się zachowania, np k wzrasta. Koncentrując się na skończonej liczbie powtarzających się przypadków, sprawili, że obliczenia stały się wykonalne i byli w stanie ukończyć dowód.

Bliższe spojrzenie na sekwencję N_k odkrywa kolejną niespodziankę: N_k jest liczbą pierwszą znacznie częściej, niż można by się spodziewać, gdyby była czysto losowa. „Z k-Sekwencja Göbela Nie tylko niezwykłe jest to, że są to liczby całkowite” – powiedział Ryszard Green, matematyk z Uniwersytetu w Kolorado. „Niezwykłe jest to, że liczby pierwsze pojawiają się tak często. To sprawia, że ​​wygląda na to, że może wydarzyć się coś głębszego.

Choć nowy artykuł stanowi na to dowód N_k zawsze wynosi co najmniej 19, nie wiadomo, czy zawsze jest skończone, czy też istnieje a k dla których ciąg zawiera liczby całkowite w nieskończoność. „N_k zachowuje się tajemniczo. […] Istnieje fundamentalna potrzeba zrozumienia leżącego u jego podstaw wzorca” – powiedział Matsusaka. „Może to przypominać radość, jaką odczuwałam jako dziecko, rozwiązując zagadki zadawane przez nauczycieli. Nawet teraz wspomnienia z tamtych czasów pozostają we mnie.”

Quanta przeprowadza serię ankiet, aby lepiej służyć naszym odbiorcom. Weź nasze ankieta dla czytelników matematyki i zostaniesz wpisany, aby wygrać za darmo Quanta towar.