A rekurzív szekvenciák elképesztő viselkedése | Quanta Magazin

A matematikában az egyszerű szabályok bonyolult és gyönyörű univerzumokat nyithatnak meg. Vegyük a híres Fibonacci sorozatot, amelynek meghatározása a következő: 1-gyel és 1-gyel kezdődik, és minden további szám az előző kettő összege. Az első néhány szám a következő:

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

Igen, egyszerű, de ez az igénytelen recept egy messzemenő jelentőségű mintát hoz létre, amely úgy tűnik, mintha beleszőtt volna a természeti világba. Ez látható a nautilus kagylók örvényeiben, az ujjaink csontjain és a levelek elrendezésén a faágakon. Matematikai hatóköre kiterjed többek között a geometriára, az algebrára és a valószínűségszámításra. Nyolc évszázaddal a sorozat nyugati bevezetése óta – az indiai matematikusok már jóval Fibonacci előtt tanulmányozták – a számok továbbra is felkeltik a kutatók érdeklődését, bizonyítva, hogy mekkora matematikai mélység állhat még a legelemibb számsorozat hátterében is.

A Fibonacci-sorozatban minden kifejezés az előtte lévőkre épül. Az ilyen rekurzív szekvenciák a viselkedések széles skáláját mutathatják, némelyik csodálatosan ellentétes az intuitív hatásokkal. Vegyünk például egy furcsa sorozatcsaládot, amelyet először egy amerikai matematikus írt le az 1980-as években. Somos Mihály.

A Fibonacci-sorozathoz hasonlóan a Somos-szekvencia is egyek sorozatával kezdődik. Egy Somos-k a sorozat ezzel kezdődik k tőlük. Minden új kifejezés egy Somos-k a sorozatot úgy határozzuk meg, hogy az előző kifejezéseket összepárosítjuk, minden párat összeszorozunk, összeadjuk a párokat, majd elosztjuk a taggal k vissza a sorrendben.

A képsorok nem túl érdekesek, ha k egyenlő 1-vel, 2-vel vagy 3-mal – ezek csak ismétlődő sorozatok. De érte k = 4, 5, 6 vagy 7 a sorozatok furcsa tulajdonságokkal rendelkeznek. Annak ellenére, hogy sok felosztásról van szó, a törtek nem jelennek meg.

„Általában nálunk nincs ilyen jelenség” – mondta Somos. „Ez egy megtévesztően egyszerű ismétlődés, hasonlóan Fibonaccihoz. De sok minden van e mögött az egyszerűség mögött.”

Más matematikusok továbbra is megdöbbentő kapcsolatokat fedeznek fel a Somos-sorozatok és a matematika látszólag nem kapcsolódó területei között. Egy júliusban közzétett újság erre használja őket megoldásokat konstruálni egy differenciálegyenlet-rendszerre, amellyel mindent modelleznek, a ragadozó-zsákmány kölcsönhatástól a nagy energiájú plazmákban haladó hullámokig. Az úgynevezett matematikai objektumok szerkezetének tanulmányozására is használják őket klaszteralgebrák és hozzá vannak kötve elliptikus görbék – amelyek kulcsot jelentettek Fermat utolsó tételének feltöréséhez.

Janice Malouf, az Illinoisi Egyetem végzős hallgatója közzétette az első bizonyítékot arra, hogy a Somos-4 és a Somos-5 szekvenciák szervesek (azaz minden kifejezés egész szám) 1992-ben. Egyéb bizonyítékok A különböző matematikusok ugyanazon eredménye nagyjából ugyanabban az időben jelent meg, a Somos-6 és a Somos-7 sorozatok integritásának bizonyítékaival együtt.

A Somos sorozatoknak ez a furcsa tulajdonsága megdöbbentette a matematikusokat. „A Somos sorozatok felkeltették az érdeklődésemet, amint megtudtam róluk” – mondta James Propp, a Massachusettsi Egyetem matematikaprofesszora, Lowell. „Az a tény, hogy a Somos-4-től a Somos-7-ig mindig egész számokat ad, akármilyen messzire is mész, csodának tűnt, ha naiv szemszögből nézed a dolgokat. Tehát más nézőpontra volt szükség.”

Propp a 2000-es évek elején talált egy új perspektívát, amikor kollégáival felfedezték, hogy a Somos-4 sorozatban szereplő számok valóban számítanak valamit. A sorozatban szereplő kifejezések bizonyos grafikonokon található struktúráknak felelnek meg. Egyes gráfok esetében lehetőség van csúcsok (pontok) és élek (vonalak) párosítására úgy, hogy minden csúcs pontosan egy másik csúcshoz kapcsolódjon – nincsenek párosítatlan csúcsok, és nincs egynél több élhez kapcsolódó csúcs sem. A Somos-4 szekvenciában lévő kifejezések egy adott gráfsorozathoz számolják a különböző tökéletes illeszkedések számát.

A felfedezés nemcsak új perspektívát kínált a Somos-szekvenciákra, hanem új módszereket is bemutatott a gráftranszformációk gondolkodására és elemzésére. Propp és tanítványai azzal ünnepeltek, hogy az eredményt a Póló.

„Számomra a matematika vonzerejének nagy része az, amikor különböző utakon érkezünk ugyanahhoz a célhoz, és úgy tűnik, valami csodálatos vagy mély dolog történik” – mondta Propp. „Az a klassz ezekben a sorozatokban, hogy vannak különböző nézőpontok, amelyek megmagyarázzák, miért kapunk egész számokat. Vannak ott rejtett mélységek.”

A sztori megváltozik a magasabb sorszámú Somos-szekvenciákhoz. A Somos-18 első 8 tagja egész szám, de a 19. tag tört. Minden ezután következő Somos sorozat törtértékeket is tartalmaz.

Egy másik típusú sorozat, amelyet Fritz Göbel német matematikus fejlesztett ki az 1970-es években, érdekes ellenpontja a Somos-sorozatoknak. A nA Göbel-sorozat e-dik tagja az összes előző tag négyzeteinek összege, plusz 1, osztva n. A Somos-sorozatokhoz hasonlóan a Göbel-sorozat is osztást tartalmaz, így arra számíthatunk, hogy a kifejezések nem maradnak egész számok. De egy darabig – ahogy a sorozat hatalmasra nő – úgy tűnik, hogy azok.

A Göbel-sorozat 10. tagja körülbelül 1.5 millió, a 11. 267-néhány milliárd. A 43. tag túl nagy ahhoz, hogy kiszámoljuk – körülbelül 178 milliárd számjegyből áll. De 1975-ben a holland matematikus Hendrik Lenstra megmutatta, hogy az első 42 taggal ellentétben ez a 43. tag nem egész szám.

A Göbel-sorozatok általánosíthatók, ha az összegben szereplő négyzeteket kockákra, negyedik hatványokra vagy akár magasabb kitevőkre cseréljük. (E konvenció értelmében az eredeti sorozatát 2-Göbel sorozatnak nevezik.) Ezek a sorozatok is meglepő tendenciát mutatnak, amikor egész tagok kiterjesztett szakaszával kezdődnek. 1988-ban Henry Ibstedt kimutatta, hogy a 89-Göbel sorozat első 3 tagja (amely négyzetek helyett kockákat használ) egész szám, de a 90. nem. Más Göbel-szekvenciákon végzett későbbi kutatások még hosszabb szakaszokat találtak. A 31-Göbel sorozat például óriási 1,077 egész számmal indul.

Júliusban a Kyushu Egyetem matematikusai, Rinnosuke Matsuhira, Toshiki Matsusaka és Koki Tsuchida megosztott egy újságot megmutatva, hogy a k-Göbel szekvencia, választástól függetlenül k, a sorozat első 19 tagja mindig egész szám. Egy japán manga ihlette őket, hogy megvizsgálják a kérdést Seisū-tan, ami azt jelenti: „Az egész számok meséje”. A keret a képregényben arra kérte az olvasókat, hogy találják ki a minimális lehetséges értéket N_k, az a pont, ahol a k-A Göbel sorozat nem termel egész számokat. A három matematikus nekilátott, hogy válaszoljon a kérdésre. „Az egész számok ilyen hosszú ideig tartó váratlan fennmaradása ellentmond az intuíciónknak” – mondta Matsusaka. „Amikor a jelenségek az intuícióval ellentétesek, úgy gondolom, hogy mindig jelen van a szépség.”

Megtalálták az ismétlődő viselkedés mintáját, mint k növeli. Véges számú ismétlődő esetre összpontosítva követhetővé tették a számítást, és be tudták fejezni a bizonyítást.

A sorrend közelebbi pillantása N_k újabb meglepetéssel szolgál: N_k sokkal gyakrabban prím, mint azt várná, ha pusztán véletlenszerű lenne. "A ... val k-Göbel sorozat, nem csak az figyelemre méltó, hogy ezek egész számok” – mondta Richard Green, a Colorado Egyetem matematikusa. „A figyelemre méltó, hogy a prímszámok olyan gyakran megjelennek. Emiatt úgy tűnik, hogy valami mélyebb dolog történhet.”

Bár az új lap ezt bizonyítja N_k mindig legalább 19, nem tudni, hogy mindig véges-e, vagy létezik-e a k amelyekre a sorozat korlátlanul tartalmaz egész számokat. "N_k titokzatosan viselkedik. … Alapvető vágy van a mögöttes mintázat megértésére” – mondta Matsusaka. „Lehet, hogy ez hasonlít ahhoz az örömhöz, amit gyerekként éreztem, amikor a tanárok által adott rejtvényeket megoldottam. Még most is bennem élnek az akkori érzések.”

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket matematika olvasói felmérés és ingyenesen nyerhetsz Quanta árut.