Osupljivo obnašanje rekurzivnih zaporedij | Revija Quanta

V matematiki lahko preprosta pravila odprejo vesolja kompleksnosti in lepote. Vzemimo znamenito Fibonaccijevo zaporedje, ki je definirano takole: Začne se z 1 in 1, vsako naslednje število pa je vsota prejšnjih dveh. Prvih nekaj številk je:

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

Preprosto, da, toda ta skromni recept povzroči vzorec daljnosežnega pomena, za katerega se zdi, da je vtkan v samo tkivo naravnega sveta. Vidimo ga v vrtincih lupin navtilusa, kosteh v naših prstih in v razporeditvi listov na drevesnih vejah. Njegov matematični doseg se med drugim razteza na geometrijo, algebro in verjetnost. Osem stoletij, odkar je bilo zaporedje predstavljeno na Zahodu - indijski matematiki so ga proučevali veliko pred Fibonaccijem - števila še naprej pritegnejo zanimanje raziskovalcev, kar dokazuje, kako velika matematična globina je lahko podlaga tudi za najosnovnejše številsko zaporedje.

V Fibonaccijevem zaporedju vsak izraz temelji na tistih, ki so bili pred njim. Takšna rekurzivna zaporedja lahko kažejo širok razpon vedenj, nekatera čudovito kontraintuitivna. Vzemimo za primer nenavadno družino zaporedij, ki jih je v osemdesetih letih prejšnjega stoletja prvič opisal ameriški matematik Michael Somos.

Tako kot Fibonaccijevo zaporedje se tudi Somosovo zaporedje začne z nizom enic. Somos-k zaporedje se začne z k izmed njih. Vsako novo obdobje Somosa-k zaporedje je definirano tako, da se seznani s prejšnjimi členi, pomnoži vsak par skupaj, sešteje pare in nato deli s členom k položaje nazaj v zaporedju.

Zaporedja niso zelo zanimiva, če k enaka 1, 2 ali 3 — so samo niz ponavljajočih se enih. Ampak za k = 4, 5, 6 ali 7 imajo zaporedja čudno lastnost. Čeprav gre za veliko deljenja, se ulomki ne prikažejo.

"Običajno nimamo tovrstnega pojava," je dejal Somos. »To je varljivo preprosta ponovitev, podobna Fibonacciju. Toda za to preprostostjo je veliko.«

Drugi matematiki še naprej odkrivajo osupljive povezave med Somosovimi zaporedji in na videz nepovezanimi področji matematike. En članek, objavljen julija, jih uporablja za konstrukcijske rešitve do sistema diferencialnih enačb, ki se uporablja za modeliranje vsega, od interakcij plenilec-plen do valov, ki potujejo v visokoenergijski plazmi. Uporabljajo se tudi za preučevanje strukture matematičnih objektov, imenovanih algebre grozdov in so povezani z eliptične krivulje - ki so bili ključ do razbitja zadnjega Fermatovega izreka.

Janice Malouf, podiplomski študent na Univerzi v Illinoisu, je objavil prvi dokaz, da zaporedja Somos-4 in Somos-5 so integralni (kar pomeni, da so vsi njihovi členi cela števila) leta 1992. Drugi dokazi istega rezultata različnih matematikov se je pojavil približno ob istem času, skupaj z dokazi, da sta zaporedji Somos-6 in Somos-7 integralni.

Ta čudna lastnost Somosovih zaporedij je osupnila matematike. "Somosove sekvence so me zanimale takoj, ko sem izvedel zanje," je dejal James Propp, profesor matematike na Univerzi Massachusetts, Lowell. »Dejstvo, da Somos-4 do Somos-7 vedno daje cela števila, ne glede na to, kako daleč greste, se je zdelo kot čudež, ko ste na stvari gledali z naivne perspektive. Zato je bil potreben drugačen pogled."

Propp je v zgodnjih 2000-ih našel nov pogled, ko je s kolegi odkril, da številke v zaporedju Somos-4 dejansko nekaj štejejo. Izrazi v zaporedju ustrezajo strukturam v določenih grafih. Za nekatere grafe je možno združiti oglišča (pike) z robovi (črtami), tako da je vsako oglišče povezano z natanko enim drugim ogliščem - ni neparnih oglišč in nobeno oglišče ni povezano z več kot enim robom. Izrazi v zaporedju Somos-4 štejejo število različnih popolnih ujemanj za določeno zaporedje grafov.

Odkritje ni le ponudilo novega pogleda na zaporedja Somos, ampak je uvedlo tudi nove načine za razmišljanje in analizo transformacij grafov. Propp in njegovi učenci so slavili tako, da so rezultat uvrstili na a T-shirt.

"Zame je velik del privlačnosti matematike, ko prideš na isti cilj po različnih poteh in se zdi, kot da se dogaja nekaj čudežnega ali globokega," je dejal Propp. »Kul stvar pri teh zaporedjih je, da obstajajo različna stališča, ki pojasnjujejo, zakaj dobite cela števila. Tam so skrite globine.”

Zgodba se spremeni za zaporedja Somos z višjim številom. Prvih 18 členov Somosa-8 je celih števil, 19. člen pa je ulomek. Vsako zaporedje Somos po tem vsebuje tudi delne vrednosti.

Druga vrsta zaporedja, ki jo je razvil nemški matematik Fritz Göbel v 1970-ih, je zanimiv kontrapunkt Somosovim zaporedjem. The nčlen Göbelovega zaporedja je definiran kot vsota kvadratov vseh prejšnjih členov, plus 1, deljena z n. Tako kot Somosova zaporedja tudi Göbelovo zaporedje vključuje deljenje, zato lahko pričakujemo, da členi ne bodo ostali cela števila. Toda za nekaj časa - ko zaporedje raste ogromno - se zdi, da so.

Deseti člen v Göbelovem zaporedju je približno 10 milijona, 1.5. 11-nekaj milijard. 267. izraz je veliko prevelik za izračun - ima približno 43 milijard števk. Toda leta 178 je nizozemski matematik Hendrik Lenstra je pokazalo, da za razliko od prvih 42 členov ta 43. člen ni celo število.

Göbelova zaporedja lahko posplošimo tako, da kvadrate v vsoti nadomestimo s kockami, četrtimi potencami ali celo višjimi eksponenti. (V skladu s to konvencijo se njegovo izvirno zaporedje imenuje 2-Göbelovo zaporedje.) Ta zaporedja kažejo tudi presenetljiv trend začenjanja z razširjenim nizom celih členov. Leta 1988 je Henry Ibstedt je pokazala, da je prvih 89 členov 3-Göbelovega zaporedja (ki uporablja kocke namesto kvadratov) celih števil, 90. pa ni. Kasnejše raziskave drugih Göbelovih zaporedij so odkrile še daljše odseke. Zaporedje 31-Göbel se na primer začne z neverjetnimi 1,077 celimi členi.

Julija so matematiki z univerze Kyushu Rinnosuke Matsuhira, Toshiki Matsusaka in Koki Tsuchida delil papir ki prikazuje, da za a k-Göbel zaporedje, ne glede na izbiro k, je prvih 19 členov zaporedja vedno cela števila. K vprašanju jih je navdušila japonska manga z naslovom Seisū-tan, kar pomeni "Zgodba o celih številih." A okvir v stripu bralce pozvala, naj ugotovijo najmanjšo možno vrednost N_k, točka, na kateri a k-Göbelovo zaporedje preneha proizvajati cele člene. Trije matematiki so se lotili odgovora na vprašanje. "Nepričakovana obstojnost celih števil za tako dolgotrajno trajanje je v nasprotju z našo intuicijo," je dejal Matsusaka. "Ko pride do pojava v nasprotju z intuicijo, verjamem, da je vedno prisotna lepota."

Ugotovili so vzorec ponavljajočega se vedenja kot k poveča. Z osredotočanjem na končno število ponavljajočih se primerov so naredili izračun izvedljiv in lahko dokončali dokaz.

Podrobnejši pogled na zaporedje N_k razkriva še eno presenečenje: N_k je praštevilo veliko pogosteje, kot bi pričakovali, če bi bilo povsem naključno. »Z k-Göbelovo zaporedje ni le izjemno, da so cela števila,« je dejal Richard Green, matematik na Univerzi v Koloradu. »Nenavadno je, da se praštevila pojavljajo tako pogosto. Zaradi tega je videti, kot da se dogaja nekaj globljega."

Čeprav novi članek predstavlja dokaz, da N_k je vedno najmanj 19, ni znano, ali je vedno končna ali obstaja a k za katere zaporedje neomejeno vsebuje cela števila. “N_k se obnaša skrivnostno. … Obstaja temeljna želja po razumevanju njegovega osnovnega vzorca,« je dejal Matsusaka. »Mogoče je podobno veselju, ki sem ga čutil kot otrok, ko sem reševal uganke, ki so mi jih dali učitelji. Še zdaj v meni ostajajo tisti občutki iz tistega časa.«

Quanta izvaja vrsto anket, da bi bolje služil svojemu občinstvu. Vzemite našo anketa bralcev matematike in vključeni boste v brezplačno zmago Quanta roba.