Den forbløffende oppførselen til rekursive sekvenser | Quanta Magazine

I matematikk kan enkle regler låse opp universer av kompleksitet og skjønnhet. Ta den berømte Fibonacci-sekvensen, som er definert som følger: Den begynner med 1 og 1, og hvert påfølgende tall er summen av de to foregående. De første tallene er:

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

Enkelt, ja, men denne upretensiøse oppskriften gir opphav til et mønster av vidtrekkende betydning, et mønster som ser ut til å være vevd inn i selve stoffet i den naturlige verden. Det sees i nautilus-skjellsvirvler, bein i fingrene våre og arrangementet av blader på tregrener. Dens matematiske rekkevidde strekker seg til blant annet geometri, algebra og sannsynlighet. Åtte århundrer siden sekvensen ble introdusert for Vesten – indiske matematikere studerte den lenge før Fibonacci – fortsetter tallene å tiltrekke seg interesse fra forskere, et bevis på hvor mye matematisk dybde som kan ligge til grunn for selv den mest elementære tallsekvensen.

I Fibonacci-sekvensen bygger hvert begrep på de som kom før det. Slike rekursive sekvenser kan vise et bredt spekter av atferd, noen fantastisk kontraintuitive. Ta for eksempel en nysgjerrig familie av sekvenser som først ble beskrevet på 1980-tallet av den amerikanske matematikeren Michael Somos.

I likhet med Fibonacci-sekvensen starter en Somos-sekvens med en serie av enere. En Somos-k sekvensen starter med k av dem. Hvert nye begrep i en Somos-k sekvens er definert ved å sammenkoble tidligere ledd, multiplisere hvert par sammen, legge sammen parene og deretter dele på leddet k posisjoner tilbake i sekvensen.

Sekvensene er ikke særlig interessante hvis k tilsvarer 1, 2 eller 3 — de er bare en serie med gjentakende. Men for k = 4, 5, 6 eller 7 sekvensene har en merkelig egenskap. Selv om det er mye divisjon involvert, vises ikke brøker.

"Vanligvis har vi ikke denne typen fenomen," sa Somos. "Det er en villedende enkel gjentakelse, lik Fibonacci. Men det er mye bak denne enkelheten.»

Andre matematikere fortsetter å avdekke oppsiktsvekkende sammenhenger mellom Somos-sekvenser og tilsynelatende ubeslektede områder av matematikken. En avis postet i juli bruker dem til bygge løsninger til et system med differensialligninger som brukes til å modellere alt fra rovdyr-byttedyr-interaksjoner til bølger som reiser i høyenergiplasmaer. De brukes også til å studere strukturen til matematiske objekter kalt klyngealgebraer og er koblet til elliptiske kurver - som var nøkkelen til å knekke Fermats siste teorem.

Janice Malouf, en doktorgradsstudent ved University of Illinois, publiserte det første beviset på at Somos-4 og Somos-5 sekvenser er integrerte (som betyr at alle termene deres er heltall) i 1992. Andre bevis av det samme resultatet av forskjellige matematikere dukket opp omtrent samtidig, sammen med bevis på at Somos-6- og Somos-7-sekvensene er integrerte.

Denne merkelige egenskapen til Somos-sekvenser forbløffet matematikere. "Somos-sekvenser fascinerte meg så snart jeg lærte om dem," sa James Propp, professor i matematikk ved University of Massachusetts, Lowell. «Det faktum at Somos-4 til Somos-7 alltid gir heltall, uansett hvor langt du går, virket som et mirakel når du så på ting fra et naivt perspektiv. Så et annet perspektiv var nødvendig."

Propp fant et nytt perspektiv på begynnelsen av 2000-tallet, da han og kollegene oppdaget at tallene i Somos-4-sekvensen faktisk teller noe. Begrepene i sekvensen tilsvarer strukturer som finnes i visse grafer. For noen grafer er det mulig å sammenkoble toppunkter (prikker) med kanter (linjer) slik at hvert toppunkt er koblet til nøyaktig ett annet toppunkt - det er ingen uparrede toppunkter, og ingen toppunkt koblet til mer enn én kant. Begrepene i Somos-4-sekvensen teller antall forskjellige perfekte samsvar for en bestemt sekvens med grafer.

Oppdagelsen ga ikke bare et nytt perspektiv på Somos-sekvenser, men introduserte også nye måter å tenke på og analysere graftransformasjoner. Propp og elevene hans feiret ved å få resultatet satt på en T-skjorte.

"For meg er en stor del av forlokkelsen med matematikk når du ankommer samme destinasjon ad forskjellige veier og det virker som om noe mirakuløst eller dypt skjer," sa Propp. "Det kule med disse sekvensene er at det er forskjellige synspunkter som forklarer hvorfor du får heltall. Det er skjulte dybder der."

Historien endres for høyere nummererte Somos-sekvenser. De første 18 leddene i Somos-8 er heltall, men det 19. leddet er en brøkdel. Hver Somos-sekvens etter det inneholder også brøkverdier.

En annen type sekvens, utviklet av den tyske matematikeren Fritz Göbel på 1970-tallet, er et interessant motstykke til Somos-sekvensene. De nleddet i Göbel-sekvensen er definert som summen av kvadratene til alle de foregående leddene, pluss 1, delt på n. I likhet med Somos-sekvensene involverer Göbel-sekvensen divisjon, så vi kan forvente at termer ikke forblir heltall. Men for en stund - ettersom sekvensen vokser seg enorm - ser de ut til å være det.

Det 10. leddet i Göbel-sekvensen er omtrent 1.5 millioner, det 11. 267-noen milliarder. Den 43. termen er altfor stor til å beregne – den har rundt 178 milliarder sifre. Men i 1975, den nederlandske matematikeren Hendrik Lenstra viste at i motsetning til de første 42 leddene, er ikke dette 43. leddet et heltall.

Göbel-sekvenser kan generaliseres ved å erstatte kvadratene i summen med terninger, fjerde potenser eller enda høyere eksponenter. (Under denne konvensjonen kalles den opprinnelige sekvensen hans en 2-Göbel-sekvens.) Disse sekvensene viser også en overraskende trend med å starte med en utvidet strekning av heltallsledd. I 1988, Henry Ibstedt viste at de første 89 leddene i 3-Göbel-sekvensen (som bruker terninger i stedet for kvadrater) er heltall, men den 90. er det ikke. Etterfølgende forskning på andre Göbel-sekvenser fant enda lengre strekninger. Den 31-Göbel-sekvensen, for eksempel, starter med hele 1,077 heltallsledd.

I juli, Kyushu University matematikere Rinnosuke Matsuhira, Toshiki Matsusaka og Koki Tsuchida delte et papir viser at for en k-Göbel-sekvens, uansett valg av k, de første 19 leddene i sekvensen er alltid heltall. De ble inspirert til å se på spørsmålet av en japansk manga kalt Seisū-tan, som kan oversettes til «The Tale of Integers». EN ramme i tegneserien ba leserne finne ut den minste mulige verdien av N_k, punktet der en k-Göbel-sekvensen slutter å produsere heltallsledd. De tre matematikerne satte seg fore å svare på spørsmålet. "Den uventede utholdenheten til heltall i en så lang varighet motsier vår intuisjon," sa Matsusaka. "Når fenomener oppstår i motsetning til intuisjon, tror jeg at det alltid er skjønnhet til stede."

De fant et mønster av gjentatt oppførsel som k øker. Ved å fokusere på et begrenset antall gjentatte tilfeller, gjorde de beregningen gjennomførbar, og de var i stand til å fullføre beviset.

En nærmere titt på sekvensen N_k avslører en annen overraskelse: N_k er prime langt oftere enn du ville forvente hvis det var rent tilfeldig. "Med k-Göbel-sekvensen det er ikke bare bemerkelsesverdig at de er heltall, sa han Richard Green, en matematiker ved University of Colorado. «Det som er bemerkelsesverdig er at primtallene dukker opp så ofte. Det får det til å se ut som om noe dypere kan være på gang."

Selv om det nye papiret presenterer et bevis på det N_k er alltid minst 19, det er ikke kjent om det alltid er endelig, eller om det finnes en k hvor sekvensen inneholder heltall på ubestemt tid. "N_k oppfører seg mystisk. … Det er et grunnleggende ønske om å forstå det underliggende mønsteret, sa Matsusaka. «Det kan være beslektet med gleden jeg følte som barn da jeg løste oppgaver gitt av lærere. Selv nå henger disse følelsene fra den tiden i meg.»

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår matematikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta varer.