Det häpnadsväckande beteendet hos rekursiva sekvenser | Quanta Magazine

I matematik kan enkla regler låsa upp universum av komplexitet och skönhet. Ta den berömda Fibonacci-sekvensen, som definieras enligt följande: Den börjar med 1 och 1, och varje efterföljande tal är summan av de två föregående. De första siffrorna är:

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

Enkelt, ja, men detta anspråkslösa recept ger upphov till ett mönster av långtgående betydelse, ett mönster som verkar vara invävt i själva väven i den naturliga världen. Det syns i nautilus-skalens virvlar, benen i våra fingrar och arrangemanget av löv på trädgrenar. Dess matematiska räckvidd sträcker sig till bland annat geometri, algebra och sannolikhet. Åtta århundraden sedan sekvensen introducerades i väst - indiska matematiker studerade den långt före Fibonacci - fortsätter siffrorna att locka forskarnas intresse, ett bevis på hur mycket matematiskt djup som kan ligga till grund för även den mest elementära talsekvensen.

I Fibonacci-sekvensen bygger varje term på de som kom före den. Sådana rekursiva sekvenser kan uppvisa ett brett spektrum av beteenden, vissa underbart kontraintuitiva. Ta till exempel en nyfiken familj av sekvenser som först beskrevs på 1980-talet av den amerikanske matematikern Michael Somos.

Liksom Fibonacci-sekvensen börjar en Somos-sekvens med en serie ettor. En Somos-k sekvensen börjar med k av dem. Varje ny term av en Somos-k sekvens definieras genom att para ihop tidigare termer, multiplicera varje par tillsammans, lägga ihop paren och sedan dividera med termen k positioner tillbaka i sekvensen.

Sekvenserna är inte särskilt intressanta om k är lika med 1, 2 eller 3 — de är bara en serie upprepade. Men för k = 4, 5, 6 eller 7 sekvenserna har en konstig egenskap. Även om det är mycket division inblandat, visas inte bråk.

"Normalt har vi inte den här typen av fenomen," sa Somos. "Det är en bedrägligt enkel upprepning, liknande Fibonacci. Men det ligger mycket bakom den enkelheten.”

Andra matematiker fortsätter att avslöja häpnadsväckande samband mellan Somos-sekvenser och till synes orelaterade områden inom matematiken. En tidning som publicerades i juli använder dem till bygga lösningar till ett system av differentialekvationer som används för att modellera allt från interaktioner mellan rovdjur och bytesdjur till vågor som färdas i högenergiplasma. De används också för att studera strukturen hos matematiska objekt som kallas klusteralgebror och är anslutna till elliptiska kurvor — som var nyckeln till att knäcka Fermats sista sats.

Janice Malouf, en doktorand vid University of Illinois, publicerade det första beviset på att Somos-4 och Somos-5 sekvenser är integrerade (vilket betyder att alla deras termer är heltal) 1992. Andra bevis av samma resultat av olika matematiker dök upp ungefär samtidigt, tillsammans med bevis på att Somos-6- och Somos-7-sekvenserna är integrerade.

Denna märkliga egenskap hos Somos-sekvenser förvånade matematiker. "Somos-sekvenser fascinerade mig så fort jag lärde mig om dem," sa James Propp, professor i matematik vid University of Massachusetts, Lowell. "Det faktum att Somos-4 till Somos-7 alltid ger heltal, oavsett hur långt ut man går, verkade som ett mirakel när man såg saker ur ett naivt perspektiv. Så det krävdes ett annat perspektiv.”

Propp hittade ett nytt perspektiv i början av 2000-talet, när han och hans kollegor upptäckte att siffrorna i Somos-4-sekvensen faktiskt räknar något. Termerna i sekvensen motsvarar strukturer som finns i vissa grafer. För vissa grafer är det möjligt att para ihop hörn (punkter) med kanter (linjer) så att varje vertex är ansluten till exakt en annan vertex - det finns inga oparade hörn och ingen vertex ansluten till mer än en kant. Termerna i Somos-4-sekvensen räknar antalet olika perfekta matchningar för en viss sekvens av grafer.

Upptäckten erbjöd inte bara ett nytt perspektiv på Somos-sekvenser, utan introducerade också nya sätt att tänka på och analysera graftransformationer. Propp och hans elever firade med att få resultatet på ett T-shirt.

"För mig är en stor del av tjusningen med matematik när du anländer till samma destination på olika vägar och det verkar som om något mirakulöst eller djupt pågår," sa Propp. "Det coola med dessa sekvenser är att det finns olika synpunkter som förklarar varför du får heltal. Det finns dolda djup där.”

Berättelsen ändras för högre numrerade Somos-sekvenser. De första 18 termerna i Somos-8 är heltal, men den 19:e termen är en bråkdel. Varje Somos-sekvens efter det innehåller också bråkvärden.

En annan typ av sekvens, utvecklad av den tyske matematikern Fritz Göbel på 1970-talet, är en intressant motpol till Somos-sekvenserna. De nGöbelsekvensens:e term definieras som summan av kvadraterna av alla föregående termer, plus 1, dividerat med n. Liksom Somos-sekvenserna involverar Göbel-sekvensen division, så vi kan förvänta oss att termer inte kommer att förbli heltal. Men ett tag – när sekvensen växer enormt – verkar de vara det.

Den 10:e termen i Göbel-sekvensen är cirka 1.5 miljoner, den 11:e 267-någon miljard. Den 43:e termen är alldeles för stor för att beräknas – den har cirka 178 miljarder siffror. Men 1975, den holländska matematikern Hendrik Lenstra visade att till skillnad från de första 42 termerna är denna 43:e term inte ett heltal.

Göbelsekvenser kan generaliseras genom att ersätta kvadraterna i summan med kuber, fjärde potenser eller ännu högre exponenter. (Under denna konvention kallas hans ursprungliga sekvens en 2-Göbel-sekvens.) Dessa sekvenser visar också en överraskande trend att börja med en utökad sträcka av heltalstermer. 1988, Henry Ibstedt visade att de första 89 termerna i 3-Göbel-sekvensen (som använder kuber istället för kvadrater) är heltal, men den 90:e är det inte. Efterföljande forskning om andra Göbel-sekvenser fann ännu längre sträckor. 31-Göbel-sekvensen, till exempel, startar med hela 1,077 XNUMX heltalstermer.

I juli, Kyushu University matematiker Rinnosuke Matsuhira, Toshiki Matsusaka och Koki Tsuchida delade ett papper visar det för en k-Göbel sekvens, oavsett val av k, de första 19 termerna i sekvensen är alltid heltal. De inspirerades att undersöka frågan av en japansk manga som heter Seisū-tan, som översätts till "The Tale of Integers". A ram i serietidningen bad läsarna att räkna ut det minsta möjliga värdet av N_k, den punkt vid vilken a k-Göbelsekvensen upphör att producera heltalstermer. De tre matematikerna gav sig i kast med att svara på frågan. "Den oväntade beständigheten av heltal under en så lång varaktighet motsäger vår intuition," sa Matsusaka. "När fenomen uppstår i motsats till intuition, tror jag att det alltid finns skönhet närvarande."

De hittade ett mönster av upprepat beteende som k ökar. Genom att fokusera på ett begränsat antal upprepade fall gjorde de beräkningen genomförbar och de kunde slutföra beviset.

En närmare titt på sekvensen N_k avslöjar en annan överraskning: N_k är prime mycket oftare än du skulle förvänta dig om det var rent slumpmässigt. "Med k-Göbel-sekvens det är inte bara anmärkningsvärt att de är heltal”, sa Richard Green, en matematiker vid University of Colorado. ”Det som är anmärkningsvärt är att primtalen dyker upp så ofta. Det gör att det ser ut som att något djupare kan vara på gång."

Även om den nya tidningen presenterar ett bevis på det N_k är alltid minst 19, det är inte känt om det alltid är ändligt eller om det finns en k för vilken sekvensen innehåller heltal på obestämd tid. "N_k beter sig mystiskt. ... Det finns en grundläggande önskan att förstå dess underliggande mönster, säger Matsusaka. "Det kan likna den glädje jag kände som barn när jag löste pussel från lärare. Även nu finns de känslorna från den tiden kvar inom mig.”

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår matematikläsarundersökning och du kommer att delta för att vinna gratis Quanta merch.