Prímek és sejtautomaták

Gregory Chaitin amerikai matematikus egyenesen azt mondja, hogy „nem nagyon érdekelnek a prímszámok”, és hivatkozik Ramanudzsanra is, aki szerint lehet, hogy helyettük inkább a „maximálisan osztható”, vagyis a lehető legtöbb osztóval rendelkező számokkal kellene foglalkoznunk. Ehhez Chaitin azt is hozzáteszi, hogy az egész kérdésnek leginkább filozófiai jelentősége van, vagyis az, hogy „még egy ilyen egyszerű matematikai területen is azonnal olyan kérdésekbe ütközünk, amelyek megválaszolásának hogyanját senki sem tudja”, és innentől kezdve két megoldás képzelhető el ezekkel a bizonyos csak eggyel és önmagukkal osztható számokkal kapcsolatban.

Vagy az, hogy vannak még számunkra ismeretlen mintázatok/szabályszerűségek, és előbb-utóbb ha nem bukkanunk is rájuk szükségképpen, legalább elvileg rájuk bukkanhatunk majd a jövőben;
vagy pedig a prímszámok (és más matematikai jelenségek) esetében nem léteznek ilyen szabályszerűségek – bármennyire meglepően is hangozzék ez elsőre.

Mely utóbbi feltételezéssel összhangban Stephen Wolfram az Újfajta tudományban a sejtautomatákból kiindulva két megállapítást tesz: hogy

• egyszerű rendszereket létrehozva hamar átlépünk egy küszöböt, és ezt követően a rendszer előre jelezhetetlenül kezd viselkedni; illetve, hogy
• a további, komplexebb szabályok általában nem vezetnek növekvő komplexitású jelenségekhez.

Majd pedig a példák között a prímeket is megemlíti, ahol egyszerű szabályok (oszthatóság) előre jelezhetetlen viselkedést (előre jelezhetetlen módon megjelenő prímek) eredményeznek. Amiből nem mellékesen az is következik, hogy bármiféle szabálykeresés, ideértve pl. az Ulam-spirált is, eleve kudarcra van ítélve.
Ugyanis az ilyen rendszerekben csak úgy lehet kideríteni, hogy a sejtautoma egy adott helyén van-e valami vagy nincs (illetve, hogy egy adott szám prím-e), hogy megvizsgáljuk a szóban forgó esetet – de nincs valamiféle szabályból következő válasz. Az pedig, hogy az Ulam-spirál szabályszerűséget látszik mutatni, egyáltalán nem meglepő: Wolfram számos példát mutat ilyesmire a sejtautomatáknál.
Amennyiben elfogadjuk az érvelését (márpedig én elfogadom), akkor legalább három kérdést tehetünk fel.

• Egyfelől azt, hogy vajon csupán ez az egyetlen komplexitási küszöb létezik-e, vagy pedig azért nem bukkantunk még újabbakra, mert a Wolfram által használt egyszerű sejtautomaták nem elég bonyolultak ahhoz, hogy elvezessenek hozzájuk?
• Másfelől: eddig lehet, hogy túlságosan is a „szabályok tudományának” tartottuk a matematikát, és amivel nem boldogultunk, azt egyszerűen még meg nem oldott problémának tekintettük, noha elképzelhető, hogy jó néhányat közülük nem is lehet a hagyományos értelemben megoldani.
• Végezetül a kiindulási problémánkhoz visszakanyarodva: úgy tűnik (és azért fogalmazok ilyen óvatosan, mert itt, lévén nem a matematika hagyományos megközelítéséről szó, a hagyományos bizonyosságnak sincs helye), hogy az összeadás és kivonás (miként korábbi blogbejegyzésekben már érintettem) nem elég bonyolult ahhoz, hogy olyan szabálytanul viselkedő jelenségeket hozzon létre, mint amilyennek a szorzás és osztás „magasságában”, azt a bizonyos komplexitási küszöböt átlépve a prímszámok bizonyulnak.  Viszont jó lenne tudni, hogy vajon milyen más, nem szorzáson és osztáson alapuló matematikai rendszereket építhetnénk rá az összeadásra és kivonásra, ahol hasonlóan összetett és előre jelezhetetlen eredmények lépnének fel, mint most?

A Nagy Fermat-tétel és "a könyvből" származó bizonyítások

Az utóbbi évtizedek talán legnagyobb matematikai szenzációja a Nagy Fermat-tétel bebizonyítása volt – a történet azonban korántsem olyan egyszerű, mint amilyennek látszik.
Egyfelől ugyanis felmerülhet a kérdés, hogy miért éppen ez, és azt válaszolhatjuk rá, hogy minden bizonnyal jelentős mértékben történeti okokból. Az például, hogy léteznek-e tökéletes páratlan számok (ahol a szám osztóinak összege magának a számnak mint osztónak az elhagyásával azonos a számmal), minden bizonnyal nem nehezebben megérthető probléma; nekem nem tűnik kevésbé izgalmasnak; és nem is újabb. Viszont mégsem foglalkoztatja az emberek túlnyomó többségét. De említhetnénk más példákat is: elvégre ne feledjük, hogy (bizonyos határokon belül) mindig szubjektív, hogy mi számít fontosnak és mi nem.
Viszont amikor Paul Wolfskethl darmstadti gyáros szerelmi bánat miatt öngyilkosságot akart lekövetni a 19. század második felében, akkor elhatározta, hogy ezt pontosan éjfélkor fogja megtenni – ám a könyvtárában rábukkanva Fermat állítására, annyira belemerült az olvasásba, hogy elmulasztotta az időpontot. Úgyhogy hálája jeléül díjat alapított a bizonyítás honorálására, és göttingeni egyetem csak az első évben 621 „megoldást” kapott. Még egy szabványválaszt is kénytelenek voltak rendszeresíteni, mely szerint
„Kedves… Úr/asszony!
Köszönettel vettük a Fermat-sejtés megoldásáról szóló kéziratát. Az első hiba a …-dik oldalon, a …-dik sorban található. Ebből kifolyólag a bizonyítása nem értékelhető.”
Ám David Hilbert 1900-ban ennek ellenére még ha a bevezetőben megemlítette is, mégsem vette fel a korszak 23 legfontosabb matematikai problémájának a listájára – és miért is tette volna. Fermat állítása mindössze annyi volt, hogy az a^n+b^n=c^n-nek nincs megoldása, ha n 2-nél nagyobb, pozitív egész szám – ami kétségkívül érdekes állítás ugyan, de még akkor sem több ennél, ha ma többek között arra szokás hivatkozni, hogy a bebizonyításához vezető kutatások során számos érdekes és fontos eredmény született. Csak éppen bármelyik nehéznek bizonyuló bizonyításnak ez lett volna az eredménye: elvégre amennyiben nem triviális, úgy sokat kell dolgozni vele.
Ráadásul ott van Carl Linderholm, aki a Mathematics Made Difficult című 1972-es könyvében azt kérdezi, hogy mivel folytatódhat az 1,2,3,4,5 számsor. Meg a 2,4,6,8,10; az 1,4,9,16,25 és még néhány másik. Majd pedig megmutatja, hogy a Lagrange-féle interpolációs képlet mindegyikre a 19-et adja ki. Értsd: ugyanazt a (matematikai) jelenséget többféleképpen is lehet magyarázni, és persze az sem kétséges, hogy bizonyítani is több úton-módon lehet. Elisha Scott Loomis 1940 körül például nem csupán 370 bizonyítást gyűjtött össze a Pitagorasz-tételre, de eközben 4 csoportba is sorolta őket: algebrai bizonyítások (109); geometriai (255); a komplex vektortereken alapuló kvaternionikusak (4) és a dinamikán alapulóak (2).
De hogy visszatérjünk a Fermat-tételhez: ráadásul Wiles valójában nem is ezt bizonyította be (és a dolgozatában ezért nem is említi Fermat nevét), hanem az ennél általánosabb Taniyama – Shimura sejtést, amelyből viszont következik a Fermat-tétele is.
Végül pedig egy további példaként ott van Klein ún. erlangeni programja is, mely szerint „a geometria nem más, mint csoportelmélet”. Amiből pedig az következik, hogy  egy régóta tanulmányozott területet adott esetben vissza lehet vezetni egy újra; és így új megoldások bizonyítások is születhetnek – akár egy régi sejtésre, akár pedig egy olyanra, amely korábban fel sem merült.
Semmi okunk sincs tehát feltételezni, hogy a jövőben ne találhatnánk más bizonyításokat a Fermat-tételre is; illetve, hogy ezek egyike-másika nem lehetne jóval egyszerűbb a Wiles-félénél, amely több mint 100 oldalra rúg, és a világon alig néhányan képesek megérteni. Erdős Pál nagyon szerette mondogatni, ha egy bizonyítás nagyon tetszett neki, hogy az „a könyvből” való; valójában azonban nem egy könyv van, hanem egy egész könyvtár, és ebből egyes műveket még el sem kezdtünk írni.

Túl a kvantumkomputeren?

A hagyományos titkosításra három dolog jelenthet veszélyt: az, ahogyan a társadalom; ahogyan a matematika és végül ahogyan a fizika működik. De ez egyben lehetőségeket is jelenthet.

1. Ami az elsőt illeti, itt lényegében arra  érdemes gondolnunk, hogy egy emberek által fenntartott rendszer annyira megbízható, mint amennyire azok, akik fenntartják. A social engineering ezt használja ki, és teljesen mindegy, hogy mennyire jó egy kód, ha valaki nem elég gondosan kezeli az információkat, és pl. hozzá tudunk jutni a kettős kulcsú titkosításban használt privát kulcsához.
2. A matematika azért érdekes a számunkra, mert ismét csak a kettős kulcsú titkosítás azon a feltételezésen alapul, hogy vannak dolgok, amelyeket az egyik irányba nagyon könnyű elvégezni, míg a másik irányba a számok növekedésével exponenciálisan válik nehezebbé. Ilyen lenne például két prímszám összeszorzása (amit bárki meg tud csinálni), majd pedig annak kikeresése, hogy az adott szám melyik két prímszám szorzata - ez utóbbi kellőképpen nagy számok esetében hatalmas számítási kapacitást igényel. Vagy legalábbis azzal a feltételezéssel szoktunk élni, hogy így van, és ezért biztonságos a két prímszám összeszorzásán alapuló titkosítás. De akadnak olyanok is, akik úgy vélik, hogy kell valamilyen szabályosságnak lennie a prímszámok eloszlása mögött. Vagyis egyes matematikusok intuíciója az egyik, másoké a másik álláspontot támogatja, de eddig sem az egyiket, sem a másikat nem sikerült bebizonyítani, és így bátran kijelenthetjük, hogy  a modern kriptográfia egy alá nem támasztott matematikai meggyőződésen alapul (amely ennek megfelelően vagy igaz, vagy nem).
3. Majdnem végezetül ott vannak az egyelőre nem különösebben hatékony kvantumkomputerek. Ezek azt használnák ki, hogy a kvantumszinten mások a fizikai törvények, mint a makroszkopikus testek világában, és a Peter Shor amerikai matematikus által által 1994-ben közzétett algoritmus megfelelő (egyelőre leginkább nem létező) kvantumszámítógépeken alkalmazva lehetővé tenné, hogy pillanatok alatt megtaláljuk az adott titkosításban használt prímszámokat.
4. A Fred Adams – Greg Laughlin csillagász szerzőpáros a The Five Ages of the Universe című könyvben azt írja, hogy az Univerzumra „négy ablak” nyílik: a bolygók, a naprendszerek, a galaxisok és az egész világmindenség szintje. Sir Martin Rees, a Royal Society jelenlegi elnöke néhány évvel ezelőtt arról beszélt, hogy egy, a galaxisok közötti térben, minden nagy tömegtől távol lebegő laboratórium kutatója nem lenne képes kimutatni a gravitáció létezését, és ennek analógiájára élhetünk azzal a feltételezéssel, hogy léteznek olyan természeti törvények, amelyek olyan kis lépték mellett, mint amennyire az emberiség tapasztalatai jelenleg kiterjednek, hasonlóképpen nem mutatható ki. Illetve feltehetjük azt a kérdést is, hogy vajon nem lehetséges-e, hogy a bolygószintnél magasabb szinteken a természeti törvények ugyanúgy másfajta logika szerint működnek, mint a kvantumszinten is, és ezeket felhasználva esetleg ugyanúgy a hagyományostól eltérő elven működő számítógépeket lehetne építeni, mint ahogyan a kvantumfizika sajátosságainak kihasználásával is?