Den forbløffende opførsel af rekursive sekvenser | Quanta Magasinet

I matematik kan enkle regler låse op for universer af kompleksitet og skønhed. Tag den berømte Fibonacci-sekvens, som er defineret som følger: Den begynder med 1 og 1, og hvert efterfølgende tal er summen af ​​de to foregående. De første par tal er:

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

Enkelt, ja, men denne beskedne opskrift giver anledning til et mønster af vidtrækkende betydning, et mønster, der ser ud til at være vævet ind i selve den naturlige verdens stof. Det ses i hvirvlerne af nautilus-skaller, knoglerne i vores fingre og arrangementet af blade på grene. Dens matematiske rækkevidde strækker sig til blandt andet geometri, algebra og sandsynlighed. Otte århundreder siden sekvensen blev introduceret til Vesten - indiske matematikere studerede den længe før Fibonacci - fortsætter tallene med at tiltrække forskernes interesse, et vidnesbyrd om, hvor meget matematisk dybde, der kan ligge til grund for selv den mest elementære talrække.

I Fibonacci-sekvensen bygger hvert udtryk på dem, der kom før det. Sådanne rekursive sekvenser kan udvise en bred vifte af adfærd, nogle vidunderligt kontraintuitive. Tag for eksempel en kuriøs familie af sekvenser, som først blev beskrevet i 1980'erne af den amerikanske matematiker Michael Somos.

Ligesom Fibonacci-sekvensen starter en Somos-sekvens med en række af enere. En Somos-k sekvens starter med k af dem. Hvert nyt udtryk i en Somos-k sekvens er defineret ved at parre tidligere led, gange hvert par sammen, lægge parrene sammen og derefter dividere med udtrykket k positioner tilbage i rækkefølgen.

Sekvenserne er ikke særlig interessante hvis k er lig med 1, 2 eller 3 - de er blot en række gentagelser. Men for k = 4, 5, 6 eller 7 sekvenserne har en mærkelig egenskab. Selvom der er en masse division involveret, vises brøker ikke.

"Normalt har vi ikke denne form for fænomen," sagde Somos. "Det er en vildledende simpel gentagelse, der ligner Fibonacci. Men der ligger meget bag den enkelthed.”

Andre matematikere fortsætter med at afsløre overraskende forbindelser mellem Somos-sekvenser og tilsyneladende ikke-relaterede områder af matematikken. Et papir udsendt i juli bruger dem til konstruere løsninger til et system af differentialligninger, der bruges til at modellere alt fra rovdyr-bytte-interaktioner til bølger, der rejser i højenergiplasmaer. De bruges også til at studere strukturen af ​​matematiske objekter kaldet klynge algebraer og er forbundet til elliptiske kurver - som var nøglen til at knække Fermats sidste sætning.

Janice Malouf, en kandidatstuderende ved University of Illinois, udgav det første bevis på, at Somos-4 og Somos-5 sekvenser er integrerede (hvilket betyder, at alle deres udtryk er heltal) i 1992. Andre beviser af det samme resultat af forskellige matematikere dukkede op omkring samme tid, sammen med beviser for, at Somos-6- og Somos-7-sekvenserne er integrerede.

Denne mærkelige egenskab ved Somos-sekvenser forbløffede matematikere. "Somos-sekvenser fascinerede mig, så snart jeg lærte om dem," sagde James Propp, professor i matematik ved University of Massachusetts, Lowell. "Det faktum, at Somos-4 til Somos-7 altid giver heltal, uanset hvor langt man går, virkede som et mirakel, når man så tingene fra et naivt perspektiv. Så et andet perspektiv var påkrævet."

Propp fandt et nyt perspektiv i begyndelsen af ​​2000'erne, da han og hans kolleger opdagede, at tallene i Somos-4-sekvensen faktisk tæller noget. Udtrykkene i rækkefølgen svarer til strukturer, der findes i visse grafer. For nogle grafer er det muligt at parre knudepunkter (prikker) med kanter (linjer), så hvert knudepunkt er forbundet med nøjagtigt et andet knudepunkt - der er ingen uparrede knudepunkter og intet knudepunkt forbundet til mere end én kant. Termerne i Somos-4-sekvensen tæller antallet af forskellige perfekte matchninger for en bestemt sekvens af grafer.

Opdagelsen tilbød ikke kun et nyt perspektiv på Somos-sekvenser, men introducerede også nye måder at tænke på og analysere graftransformationer på. Propp og hans elever fejrede ved at få resultatet sat på en T-shirt.

"For mig er en stor del af tiltrækningen ved matematik, når du ankommer til den samme destination ad forskellige veje, og det ser ud til, at der foregår noget mirakuløst eller dybt," sagde Propp. "Det fede ved disse sekvenser er, at der er forskellige synspunkter, der forklarer, hvorfor du får heltal. Der er skjulte dybder der.”

Historien ændres for højere nummererede Somos-sekvenser. De første 18 led i Somos-8 er heltal, men det 19. led er en brøkdel. Hver Somos-sekvens derefter indeholder også brøkværdier.

En anden type sekvens, udviklet af den tyske matematiker Fritz Göbel i 1970'erne, er et interessant modspil til Somos-sekvenserne. Det nled i Göbel-sekvensen er defineret som summen af ​​kvadraterne af alle de foregående led, plus 1, divideret med n. Ligesom Somos-sekvenserne involverer Göbel-sekvensen division, så vi kan forvente, at termer ikke forbliver heltal. Men i et stykke tid - efterhånden som sekvensen vokser enormt - ser de ud til at være det.

Det 10. led i Göbel-sekvensen er omkring 1.5 millioner, det 11. 267 - nogle milliarder. Den 43. term er alt for stor til at beregne - den har omkring 178 milliarder cifre. Men i 1975, den hollandske matematiker Hendrik Lenstra viste, at i modsætning til de første 42 led, er dette 43. led ikke et heltal.

Göbel-sekvenser kan generaliseres ved at erstatte kvadraterne i summen med terninger, fjerde potenser eller endnu højere eksponenter. (I henhold til denne konvention kaldes hans oprindelige sekvens en 2-Göbel-sekvens.) Disse sekvenser viser også en overraskende tendens til at starte med en udvidet strækning af heltalstermer. I 1988, Henry Ibstedt viste at de første 89 led i 3-Göbel-sekvensen (som bruger terninger i stedet for kvadrater) er heltal, men den 90. er det ikke. Efterfølgende forskning på andre Göbel-sekvenser fandt endnu længere strækninger. Den 31-Göbel-sekvens, for eksempel, starter med hele 1,077 heltal.

I juli, Kyushu University matematikere Rinnosuke Matsuhira, Toshiki Matsusaka og Koki Tsuchida delte et papir viser det for en k-Göbel sekvens, uanset valget af k, de første 19 led i sekvensen er altid heltal. De blev inspireret til at undersøge spørgsmålet af en japansk manga kaldet Seisū-tan, som kan oversættes til "The Tale of Integers". EN ramme i tegneserien bedt læserne om at finde ud af den mindst mulige værdi af N_k, det punkt, hvor a k-Göbel-sekvensen holder op med at producere heltalsled. De tre matematikere satte sig for at besvare spørgsmålet. "Den uventede vedholdenhed af heltal i så lang en varighed modsiger vores intuition," sagde Matsusaka. "Når fænomener opstår i modsætning til intuition, tror jeg, at der altid er skønhed til stede."

De fandt et mønster af gentagen adfærd som k stiger. Ved at fokusere på et begrænset antal gentagne tilfælde gjorde de beregningen gennemførlig, og de var i stand til at fuldføre beviset.

Et nærmere kig på rækkefølgen N_k afslører en anden overraskelse: N_k er prime langt oftere, end du ville forvente, hvis det var rent tilfældigt. "Med k-Göbel-sekvens det er ikke bare bemærkelsesværdigt, at de er heltal,” sagde Richard Green, en matematiker ved University of Colorado. ”Det bemærkelsesværdige er, at primtallene dukker op så ofte. Det får det til at se ud, som om noget dybere kan være i gang."

Selvom det nye papir præsenterer et bevis på det N_k er altid mindst 19, det vides ikke, om det altid er endeligt, eller om der findes en k hvor sekvensen indeholder heltal på ubestemt tid. “N_k opfører sig mystisk. … Der er et grundlæggende ønske om at forstå dets underliggende mønster,” sagde Matsusaka. "Det kan måske svare til den glæde, jeg følte som barn, da jeg løste gåder givet af lærere. Selv nu hænger disse følelser fra dengang i mig."

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores matematiklæserundersøgelse og du vil være med til at vinde gratis Quanta merch.