Comportamentul uimitor al secvențelor recursive | Revista Quanta

În matematică, regulile simple pot debloca universuri de complexitate și frumusețe. Luați celebra succesiune Fibonacci, care este definită după cum urmează: începe cu 1 și 1, iar fiecare număr ulterior este suma celor două anterioare. Primele numere sunt:

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

Simplu, da, dar această rețetă modestă dă naștere unui model de o semnificație de anvergură, unul care pare să fie țesut în însăși țesătura lumii naturale. Se vede în spiralele scoicilor de nautilus, oasele din degetele noastre și aranjarea frunzelor pe ramurile copacilor. Aria sa matematică se extinde la geometrie, algebră și probabilitate, printre alte domenii. La opt secole de când secvența a fost introdusă în Occident – ​​matematicienii indieni au studiat-o cu mult înainte de Fibonacci – numerele continuă să atragă interesul cercetătorilor, o dovadă a cât de multă profunzime matematică poate sta la baza chiar și a celei mai elementare secvențe de numere.

În secvența Fibonacci, fiecare termen se bazează pe cei care au fost înainte. Astfel de secvențe recursive pot prezenta o gamă largă de comportamente, unele minunat contraintuitive. Luați, de exemplu, o familie curioasă de secvențe descrise pentru prima dată în anii 1980 de matematicianul american Michael Somos.

Ca și succesiunea Fibonacci, o secvență Somos începe cu o serie de unii. A Somos-k secvența începe cu k dintre ei. Fiecare nou termen al unui Somos-k secvența este definită prin împerecherea termenilor anteriori, înmulțirea fiecărei perechi împreună, adunarea perechilor și apoi împărțirea la termen k poziții înapoi în succesiune.

Secvențele nu sunt foarte interesante dacă k este egal cu 1, 2 sau 3 — sunt doar o serie de repetări. Dar pentru k = 4, 5, 6 sau 7 secvențele au o proprietate ciudată. Chiar dacă există o mulțime de diviziuni implicate, fracțiile nu apar.

„În mod normal, nu avem acest tip de fenomen”, a spus Somos. „Este o recurență înșelător de simplă, similară cu Fibonacci. Dar în spatele acestei simplități se află multe.”

Alți matematicieni continuă să descopere conexiuni uimitoare între secvențele Somos și domeniile aparent neînrudite ale matematicii. O ziare postată în iulie le folosește construiți soluții la un sistem de ecuații diferențiale folosite pentru a modela totul, de la interacțiunile prădător-pradă până la valuri care călătoresc în plasme de înaltă energie. Ele sunt, de asemenea, folosite pentru a studia structura obiectelor matematice numite algebre de clustere și sunt conectate la curbe eliptice — care au fost cheia pentru a sparge Ultima Teoremă a lui Fermat.

Janice Malouf, un student absolvent la Universitatea din Illinois, a publicat prima dovadă că secvențele Somos-4 și Somos-5 sunt integrale (adică toți termenii lor sunt numere întregi) în 1992. Alte dovezi a aceluiași rezultat de către diferiți matematicieni a apărut cam în același timp, împreună cu dovezi că secvențele Somos-6 și Somos-7 sunt integrale.

Această proprietate ciudată a secvențelor Somos i-a uimit pe matematicieni. „Secvențele Somos m-au intrigat de îndată ce am aflat despre ele”, a spus James Propp, profesor de matematică la Universitatea din Massachusetts, Lowell. „Faptul că Somos-4 prin Somos-7 oferă întotdeauna numere întregi, indiferent cât de departe ai merge, mi s-a părut un miracol când ai privit lucrurile dintr-o perspectivă naivă. Deci a fost nevoie de o perspectivă diferită.”

Propp a găsit o nouă perspectivă la începutul anilor 2000, când el și colegii săi au descoperit că numerele din secvența Somos-4 contează de fapt ceva. Termenii din succesiune corespund structurilor găsite în anumite grafice. Pentru unele grafice, este posibil să împerechezi vârfuri (puncte) cu muchii (linii), astfel încât fiecare vârf să fie conectat exact la un alt vârf - nu există vârfuri nepereche și nici un vârf conectat la mai mult de o muchie. Termenii din secvența Somos-4 numără numărul de potriviri perfecte diferite pentru o anumită secvență de grafice.

Descoperirea nu numai că a oferit o nouă perspectivă asupra secvențelor Somos, dar a introdus și noi moduri de a gândi și de a analiza transformările grafice. Propp și studenții săi au sărbătorit punând rezultatul pe a Tricou.

„Pentru mine, o mare parte a atracției matematicii este atunci când ajungi la aceeași destinație pe căi diferite și pare că se întâmplă ceva miraculos sau profund”, a spus Propp. „Lucrul tare la aceste secvențe este că există diverse puncte de vedere care explică de ce obții numere întregi. Sunt adâncimi ascunse acolo.”

Povestea se schimbă pentru secvențele Somos cu numere mai mari. Primii 18 termeni ai lui Somos-8 sunt numere întregi, dar al 19-lea termen este o fracție. Fiecare secvență Somos după aceea conține și valori fracționale.

Un alt tip de secvență, dezvoltat de matematicianul german Fritz Göbel în anii 1970, este un contrapunct interesant la secvențele Somos. The nal treilea termen al secvenței Göbel este definit ca suma pătratelor tuturor termenilor anteriori, plus 1, împărțit la n. La fel ca și secvențele Somos, și secvența Göbel implică divizare, așa că ne-am putea aștepta ca termenii să nu rămână numere întregi. Dar pentru o vreme - pe măsură ce secvența devine enormă - par să fie.

Cel de-al 10-lea termen din secvența Göbel este de aproximativ 1.5 milioane, al 11-lea 267 - câteva miliarde. Al 43-lea termen este mult prea mare pentru a fi calculat - are aproximativ 178 de miliarde de cifre. Dar în 1975, matematicianul olandez Hendrik Lenstra a arătat că, spre deosebire de primii 42 de termeni, acest al 43-lea termen nu este un număr întreg.

Secvențele Göbel pot fi generalizate prin înlocuirea pătratelor din sumă cu cuburi, puteri a patra sau chiar exponenți mai mari. (În conformitate cu această convenție, secvența sa originală este numită secvență 2-Göbel.) Aceste secvențe prezintă, de asemenea, o tendință surprinzătoare de a începe cu o extensie extinsă de termeni întregi. În 1988, Henry Ibstedt a arătat că primii 89 de termeni ai secvenței 3-Göbel (care utilizează cuburi în loc de pătrate) sunt numere întregi, dar al 90-lea nu este. Cercetările ulterioare asupra altor secvențe Göbel au găsit întinderi și mai lungi. Secvența de 31 de Göbel, de exemplu, începe cu 1,077 de termeni întregi.

În iulie, matematicienii de la Universitatea Kyushu Rinnosuke Matsuhira, Toshiki Matsusaka și Koki Tsuchida a împărtășit o hârtie arătând că pentru a k-Secvența Göbel, indiferent de alegere k, primii 19 termeni ai șirului sunt întotdeauna numere întregi. Ei au fost inspirați să analizeze această întrebare de o manga japoneză numită Seisū-tan, care se traduce prin „Povestea numerelor întregi”. A cadru în cartea de benzi desenate a cerut cititorilor să-și dea seama de valoarea minimă posibilă a N_k, punctul în care a k-Secvența Göbel încetează să producă termeni întregi. Cei trei matematicieni și-au propus să răspundă la întrebare. „Persistența neașteptată a numerelor întregi pentru o perioadă atât de lungă contrazice intuiția noastră”, a spus Matsusaka. „Când fenomene apar contrar intuiției, cred că există întotdeauna frumusețe prezentă.”

Au găsit un model de comportament repetat ca k crește. Concentrându-se pe un număr finit de cazuri repetate, ei au făcut calculul tratabil și au putut finaliza demonstrația.

O privire mai atentă asupra secvenței N_k dezvăluie o altă surpriză: N_k este prim mult mai des decât v-ați aștepta dacă ar fi pur aleatoriu. "Cu k-Secvența Göbel nu este doar remarcabil că sunt numere întregi”, a spus Richard Green, un matematician la Universitatea din Colorado. „Ceea ce este remarcabil este că numerele prime apar atât de des. Asta face să pară că s-ar putea întâmpla ceva mai profund.”

Deși noua lucrare prezintă o dovadă că N_k este întotdeauna cel puțin 19, nu se știe dacă este întotdeauna finit sau dacă există a k pentru care șirul conține numere întregi pe termen nelimitat. „N_k se comportă în mod misterios. … Există o dorință fundamentală de a înțelege modelul său de bază”, a spus Matsusaka. „Ar putea fi asemănător cu bucuria pe care am simțit-o în copilărie când rezolvam puzzle-uri oferite de profesori. Chiar și acum, acele sentimente din acea vreme persistă în mine.”

Cuante efectuează o serie de sondaje pentru a servi mai bine publicul nostru. Ia-ne sondaj pentru cititorii de matematică și vei fi înscris pentru a câștiga gratuit Cuante Merch.