Prímek, számítógépek és Abel-díj

Nagy öröm érte a magyar matematikai közösséget: Szemerédi Endre Abel-díjat kapott! A díjat 2003 óta évente adományozza a Norvég Tudományos Akadémia a matematika területén elért kimagasló életmű jutalmaként. A díj névadója Niels Henrik Abel norvég matematikus (1802–1829).

Mivel matematikából nincs Nobel-díj, a norvég kormány a díj összegét a Nobel-díjhoz hasonlóan állapította meg, és a Nobel-díjhoz hasonló ünnepségek keretében adja át a norvég király. 

Az Abel-díj honlapján a díjbizottság indoklását sok nyelven, köztük magyarul is közzétették. Az alábbiakban ezt az indoklást idézzük, és közben részletesen áttekintjük, mit is jelent.

„A Norvég Tudományos Akadémia (Norwegian Academy of Science and Letters) úgy határozott, hogy 2012-ben Abel-díjjal tünteti ki Szemerédi Endrét (Magyar Tudományos Akadémia Rényi Alfréd Matematikai Kutatóintézete, Budapest és Rutgers, a  New Jersey Állami Egyetem Számítástechnikai Tanszéke, USA) a diszkrét matematikához és az elméleti számítástechnikához való alapvető hozzájárulása, valamint azon mélyreható és hosszú távú hatás elismeréséül, amit ez a hozzájárulás gyakorol az additív számelméletre és az ergodelméletre.”

Mi is a diszkrét matematika, és hogyan kapcsolódik a számításelmélethez? A matematika gyors fejlődését a 18–19. században nagymértékben a fizika fejlődése motiválta, ez pedig az analízis módszereit igényelte: differenciál- és integrálszámítást, differenciálegyenleteket. Ehhez tisztázni kellett olyan alapfogalmakat, mint például a folytonosság fogalma – tehát a fizika mind elméleti, mind gyakorlati szempontból a „folytonos” matematika fejlődéséhez vezetett. A 20. század során vált nyilvánvalóvá, hogy a matematikának olyan érdekes kérdései és fontos alkalmazási területei is vannak, melyeknél nem a folytonos mozgás, változás játssza a fő szerepet, hanem egymástól elkülönített, matematikai kifejezéssel „diszkrét” dolgok, és azok egymáshoz kapcsolódása, kölcsönhatása. Az ilyen problémák körül kialakuló új elméletről a díj indoklása a következőket írja:

„A diszkrét matematika olyan struktúrákat vizsgál, mint a gráfok, a sorozatok, a permutációk és a geometriai konfigurációk. Az ilyen struktúrák matematikája képezi a számítógép-tudomány és az információelmélet alapját. Például az internethez hasonló kommunikációs hálózatok leírhatók és elemezhetők a gráfelmélet eszközeivel, és a hatékony számítási algoritmusok tervezése alapvetően a diszkrét matematika révén szerzett ismeretekre támaszkodik. A diszkrét struktúrák kombinatorikája számos tiszta matematikai terület fő komponense, beleértve a számelméletet, a valószínűség-elméletet, az algebrát, a geometriát és az analízist.” 

Magyarország a diszkrét matematika egyik őshazája, főleg a gráfelméleté. Az első gráfelméleti monográfiát Kőnig Dénes publikálta 1936-ban. Tanítványai és fiatalabb munkatársai nagyban hozzájárultak a terület fejlődéséhez. Elsősorban Erdős Pál volt meghatározó személyiség, de igen sokat tett Gallai Tibor is. Jelentős magyar matematikusok, akiknek fő kutatási területe a matematika más ága volt (Turán Pál, Hajós György, Szele Tibor és mások) fontos eredményekkel járultak hozzá a gráfelmélet fejlődéséhez is. (A díj indoklása is utal erre később.) 

Nehéz volna ezeket a fontos matematikai területeket itt ismertetni. Induljunk ki inkább Szemerédi Endre leghíresebb eredményéből, ahogyan a díj indoklása is teszi:

„1975-ben Szemerédi Endre először a híres Erdős–Turán-sejtés megoldásával vonta magára sok matematikus
figyelmét, kimutatta, hogy egész számok bármely pozitív sűrűségű halmazában tetszőleges hosszúságú számtani sorozat van. Ez meglepő volt, mivel még a 3 vagy 4 hosszú sorozatok esete is korábban jelentős erőfeszítést igényelt Klaus Roth és maga Szemerédi részéről is.”

Erről a problémáról érdemes részletesebben is írni, nemcsak magyar vonatkozásai miatt, hanem azért is, mert szépen mutatja, hogy a gondolatok és módszerek hogyan áramlanak a matematika egyik területéről a másikra, erősödve és új gondolatokkal gazdagodva. Mint olyan sok matematikai problémakör, ez is a prímszámokkal kezdődött. A prímszámok: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … olyan 1-nél nagyobb egész számok, melyeket nem lehet két, náluk kisebb pozitív egész szám szorzatára bontani. Ha egy l-nél nagyobb egész szám nem prímszám, akkor tehát fel lehet bontani két kisebb egész szám szorzatára. Ha ezek valamelyike nem prímszám, akkor azt tovább lehet bontani, és ezt addig lehet folytatni, míg végül az eredeti számot prímszámok szorzataként kapjuk meg. Ebben az értelemben a prímszámok az egész számok „építőkövei”, és tulajdonságaik igen fontosak nemcsak elméletileg, hanem gyakorlatilag is. (Például a számítástechnikából ismert RSA-kód és annak biztonsága is a prímeken alapszik.)

Igen sok mindent lehet kérdezni a prímszámokról, és gyakran olyan kérdések is felvethetők, amelyeknek gyakorlati alkalmazása nincsen, de természetesek. Ilyen például, hogy milyen számtani sorozatok állnak kizárólag prímszámokból. Például 3, 5, 7 egy ilyen háromtagú számtani sorozat. Van-e hosszabb? Igen, például 5, 11, 17, 23. Van-e még hosszabb? Hogy sok kérdésnek elébe vágjunk, elárulom, hogy a 199-cel kezdődő, 210 különbségű számtani sorozat első 10 tagja prímszám. Van-e végtelen hosszú, prímszámokból álló számtani sorozat? Nem nehéz belátni, hogy a válasz nemleges. A prímszámok között akármilyen nagy hézagok vannak (ez elemi tény), bármilyen számtani sorozat tagjai azonban állandó közökkel követik egymást, így előbb-utóbb beleesnek egy olyan hézagba, ahol nincs prímszám.

Ha végtelen hosszú nincs is, van-e akármilyen hosszú, prímszámokból álló számtani sorozat? Mondjuk, van-e 1000 tagból álló? A fenti rövid sorozatból is látszik, hogy a prímszámok meglehetősen összevissza helyezkednek el. Hogy jobban megértsük a kérdés nehézséget, írjuk fel algebrai alakban. Ha (p₁, p₂,p₃, …, p₁₀₀₀) prímszámokból álló számtani sorozat, akkor

p₂– p₁ = p₃–p₂ = … = p₁₀₀₀– p₉₉₉.

Prímszámokat szorozni természetes dolog, hiszen így kapjuk például a többi egész számot. De kivonni? Mit mond a p₂– p₁ különbségről az, hogy p₁ és p₂nem bonthatók szorzatra? Lényegében semmit, és ezért kezelhető nehezen ez a kérdés. (Több más, prímszámokra vonatkozó alapvető kérdés is hasonló okokból nehéz, mint például az ikerprím-probléma vagy a Goldbach-sejtés.) 

Most jön a jelentős ötlet: Hátha nem is kell a prímszámok sorozatáról többet tudni, mint hogy elég sűrűn vannak az egészek között? Tudjuk (ez a híres „prímszámtétel”), hogy egy n számnál nem nagyobb prímek száma jó közelítéssel n/lnn, ahol lnn az n természetes logaritmusa. Lehet, hogy ez a tény már önmagában is elég? Pontosabban, igaz-e, hogy ha bármilyen végtelen sorozatra (álljon az prímekből, vagy bármi másból) tudjuk, hogy bármely n számnál kisebb tagjainak száma legalább n/lnn, akkor ebben a sorozatban már van akármilyen hosszú számtani sorozat? 

Sajnos, erre a kérdésre máig sem tudjuk a választ. De Erdős és Turán 1936-ban azt javasolta, hogy erősítsük a feltételt: tegyük fel azt, hogy a sorozat bármely n számnál kisebb tagjainak száma legalább cn, ahol c bármilyen kicsi, de rögzített pozitív szám. Az ilyen sorozatot pozitív sűrűségűnek hívjuk. Ez a híres Erdős–Turán-probléma: igaz-e, hogy minden pozitív sűrűségű sorozat tartalmaz akármilyen hosszú számtani sorozatot? 

Erdős Pál és Szemerédi Endre

A kérdés nehéznek bizonyult, de nem reménytelenül nehéznek (ami az igazán jó tudományos probléma ismérve). Az első lépést a megoldás felé Roth angol matematikus tette, aki 1953-ban bebizonyította, hogy minden pozitív sűrűségű sorozat tartalmaz 3 tagú számtani sorozatot. Roth ehhez a Fourier-analízis eszközeit vette igénybe. (Jegyezzük meg: ez a probléma össze fogja hozni a matematika legkülönbözőbb területeit!) Szemerédi először azt bizonyította be, hogy minden pozitív sűrűségű sorozat tartalmaz 3 tagú számtani sorozatot, majd néhány évre rá bebizonyította az Erdős–Turán-sejtést. 

Térjünk vissza a díj indoklásához.

„De nem ez volt a legnagyobb meglepetés. Szemerédi bizonyítása a kombinatorikai indoklás mesterműve volt, és azonnal elismerték kivételes mélységét és fontosságát.” 

A sok oldalnyi nehéz, mély, csavaros kombinatorikai érvelésnek természetesen a kivonatát sem tudom itt adni. Van azonban a gondolatmenetnek egy fontos eleme, amit érdemes ismertetni. A matematikában, annak modern alkalmazásai között sok olyan struktúra kerül elő, mely nagyon nagy és bonyolult, és melyet szinte lehetetlen teljesen áttekinteni. Mit lehet mégis tenni? Szemerédi munkája és annak továbbfejlődése során kialakult egy általános elv. A struktúrát három összetevőre lehet bontani: van egy viszonylag egyszerűen leírható alapstruktúra; erre rárakódik egy másik, véletlenszerű struktúra; erre rárakódik egy harmadik, vékonyka és szerencsés esetben jelentéktelen struktúra, amit „hibának” tekinthetünk (nem arról van szó, hogy itt bárki hibázott volna, csak arra utal a kifejezés, hogy ezt az összetevőt el akarjuk hanyagolni). 

Talán meglepő, hogy különbséget teszünk a véletlen rész és a hiba között; első ránézésre hajlamosak volnánk a kettőt azonosítani. Pedig ami véletlen, annak nagyon is szoros törvényszerűségei vannak! (Gondoljunk csak a nagy számok törvényeire.) A számtani sorozatos kérdés máris példát ad erre. Vizsgáljuk meg azt az esetet, amikor a sorozatot véletlenszerűen alkotjuk meg, mondjuk úgy, hogy minden számhoz feldobunk egy kockát, és akkor tesszük be a számot, ha 6-ost dobunk! Azt ugyan nem tudjuk megmondani, hogy ebben a sorozatban hol lesz 10 tagú számtani sorozat, de a nagy számok törvényét használva nem nehéz belátni, hogy nagy valószínűséggel hemzsegni fognak a 10 tagú számtani sorozatok, ha eléggé messzire elmegyünk benne. 

Kombinatorikai workshopon. Lent bal oldalon Szemerédi Endre, fent jobbra Lovász László (Archives of the Mathematisches Forschungsinsinstitut Oberwolfach)

Visszatérve a három összetevőre bontás kérdésére, a nehéz­ség természetesen az, hogy hogyan definiáljuk matematikailag a fenti filozófiában előforduló szavakat. Mit jelentsen az „alapstruktúra”? Mitől lesz a második összetevő „véletlenszerű” (akkor is szükség van erre, amikor teljesen determinisztikus szabály írja le a struktúrát)? Hogyan mérjük azt, hogy a hiba „jelentéktelen”? Egyáltalában, mit jelent az, hogy „összetevőkre bontani”? A számsorozatok esetén ezekre a kérdésekre különböző válaszok adhatók, és a legutóbbi években is igen aktív kutatás folyik az egyre mélyebb (és nehezebben kezelhető) felbontások megalkotásában. 

„A bizonyításban a fő lépés az ún. Szemerédi-féle regularitási lemma, a nagy gráfok strukturális osztályozása. Idővel ez a lemma mind a gráfelmélet, mind a számítógép-tudomány központi eszközévé vált, megoldást adva a „property testing” terület jelentős problémáira és teret engedve a gráf-határérték elmélet kifejlődésének.”

Mi is ez a híres lemma? A fent leírt felbontási elvnek talán első megjelenése, nem számsorozatokra, hanem gráfokra (csúcsokból és azokat összekötő élekből álló hálózatokra). Nagyon leegyszerűsítve azt mondja ki, hogy minden nagy gráf csúcsai beoszthatók egyforma nagy osztályokba úgy, hogy az egyes osztályok közötti élek úgy helyezkednek el, mintha véletlenül lettek volna behúzva. Úgy is mondhatjuk, hogy ha két osztály között eltöröljük az éleket, és ugyanannyi véletlenül behúzott éllel helyettesítjük, akkor a kapott gráfot nehéz lesz az eredetitől megkülönböztetni. (Ne firtassuk most, hogy milyen eszközökkel próbáljuk ezeket megkülönböztetni: olyasmire gondolhatunk, hogy megszámoljuk a két gráfban a háromszögeket, négyszögeket stb.) Minél több osztályt engedünk meg, annál nehezebb lesz a megkülönböztetés. Az első összetevő az osztályok számát és a köztük futó élek számát tartalmazza, ez néhány adattal megadható; a második az egyes osztályok között behúzott élek véletlenszerű helyét; a harmadik az a hiba, aminél pontosabb számolással az első és második gráf mégis megkülönböztethető.

A regularitási lemma alapvető eszközzé vált a gráfelmélet sok területén: ha a gráf fent leírt felbontását meghatároztuk (vagy egy elméleti vizsgálatban elképzeltük), ebből nagyon sok mindenre tudunk már következtetni: részgráfok létezésére és számára, a gráf legkülönbözőbb tulajdonságaira. Szerencsére a díj indoklásában említett „property testing” és „gráf-határárték elmélet” tekintetében hivatkozhatok a Természet Világa 2007. évi 3. számában megjelent „Nagyon nagy gráfok” című cikkre. 

„Újabb meglepetések is következtek. A diszkrét matematikára és az additív számelméletre gyakorolt hatásán túl Szemerédi tétele arra ösztönözte Hillel Fürstenberget, hogy új irányokban fejlessze tovább az ergodelméletet. Fürstenberg új ergodelméleti bizonyítást adott a Szemerédi-féle tételre a többszöri ismétlődési teoréma kidolgozásával, ezzel váratlanul ösz­szekapcsolva a diszkrét matematikai kérdéseket a dinamikus rendszerek elméletével.”

Mint említettük, az Erdős–Turán-probléma sok más területhez is csatlakozik, ezek egyike a dinamikus rendszerek elmélete. Ez az elmélet Poincaré munkásságával indult, aki a 19. század végén a naprendszer hosszú távú viselkedését próbálta leírni. Hogy mindez hogy csatlakozik a számtani sorozatokhoz, azt nehéz volna elmagyarázni. Talán annyit lehet megjegyezni, hogy a közös elem a periodikusság: egy bolygó mozgása periodikus, és egy számtani sorozat is.

„Ez az alapvető összekapcsolás sok más fejleményhez vezetett, ilyen például a Green–Tao-tétel, amely szerint a prímszámok halmazában tetszőleges hosszúságú számtani sorozat van.”

Ezzel el is árultuk a kiindulásul megfogalmazott probléma végső sorsát: 2004-ben Green és Tao megoldották. (Tao 2006-ban ezért és más eredményeiért megkapta a fiatal matematikusok legmagasabb kitüntetését, a Fields-érmet.) Bizonyításuk Szemerédi bizonyításának alapgondolatát kombinálja Fürstenberg módszerével. 

Az utóbbi évtizedben Szemerédi tételére több különböző bizonyítás is született. Gowers angol matematikus (maga is Fields-érmes) felelevenítette Roth Fourier-analízisen alapuló módszerét, és így tudott pontosabb becslést mondani arra, hogy meddig is kell elmenni ahhoz, hogy egy pozitív sűrűségű sorozatban (mondjuk) 4 hosszúságú számtani sorozatot találjunk. Elek Gábor és Szegedy Balázs a matematikai logika modern eszköztárát használva adtak viszonylag rövid bizonyítást. 

(Első pillanatra nem világos, hogy mire jó az, hogy egy tételt más módszerrel újra bebizonyítunk; ettől nem lesz „igazabb”. Egy nehéz tételre adott bizonyítás azonban szinte mindig túlmutat a tételen: új módszereket, távoli területek közötti meglepő és nagyon gyümölcsöző kapcsolatokra mutat rá. Szemerédi tétele esetében ez messzemenően igaz.) 

„Szemerédi számos további mélyreható, fontos lépést tett, és nagy hatást gyakorolt mind a diszkrét matematikára, mind az elméleti számítástechnikára. A diszkrét matematikai példák sorába tartozik a Szemerédi–Trotter-tétel, az Ajtai–Komlós–Szemerédi-féle kvázi-random módszer, az Erdős–Szemerédi-féle „öszszeg-szorzat” tétel és a Balog–Szemerédi–Gowers-lemma. Az elméleti számítástechnikai példák közé tartozik az Ajtai–Komlós–Szemerédi-féle sorba rendező hálózat, Fredman–Komlós–Szemerédi „hashing” módszere és a Paul–Pippenger–Szemerédi–Trotter-féle tétel, amely szétválasztja a determinisztikus és a nem determinisztikus lineáris időt.”

Ennek a sok fontos eredménynek bármelyikéről izgalmas ismertető cikket lehetne írni (bár egyiket-másikat valószínűleg nehezebb volna elmagyarázni, mint az Erdős–Turán-sejtést). Most elégedjünk meg az idézettel, ami Szemerédi munkájának sokrétűségét és sokirányú hatását mutatja.

„A matematika Szemerédi-féle megközelítése jó példát szolgáltat az erőteljes magyar problémamegoldási hagyományra. Mi több, munkásságának elméleti hatása megváltoztatta a játékszabályokat.” 

Természet Világa