Endre Szemeredi darbų esmė „ant pirštų“. Lithuanian

Endre Szemeredi 2012 m. buvo paskirta Abelio premija už „indėlį diskrečiajai matematikai ir informatikai bei jo gilaus ir kaip ilgalaikio indėlio į adityvinę skaičių teoriją ir ergodiką pripažinimo ženklą“ (žr. >>>>>).
Čia pabandysime paaiškinti jo darbų esmę.

Endre Szemeredi yra iškilus specialistas kombinatorikoje su svariu indėliu ekstremalios kombinatorikos srityje. Labiausiai žinomas 1975 m. įrodyta dešimtmečių senumo (suformuluotą 1936 m.) Erdošo¹⁾ ir Turano²⁾ teiginį (dabar vadinamos Szemeredi teorema). Taip pat jis įrodė Szemeredi reguliarumo lemą, panaudotą Szemeredi teoremos įrodymui, tačiau tapusią svarbiu įrankiu ekstremalioje kombinatorikoje. Be šių pasiekimų, jis paskelbė per 200 straipsnių, daugelyje kurių padarė nemažą pažangą.

Gerai, tai kas ta kombinatorika? Vienas galimų apibrėžimų yra tas, kad tai diskrečių struktūrų tyrinėjimas. Gerai, o kas yra jos? „Diskretus“ paprastai priešpastatomas „tolydžiam“: tolydus sklandžiai slysta per struktūrą, tuo tarpu Grafas

diskretus priverstas šokčioti per elementus. Pvz., skysčių srauto matematinės struktūros yra tolydžios, o štai kompiuterio vidinė struktūra yra iš 0 ir 1. Kita diskrečiąja svarbia kombinatorikoje struktūra yra grafas (t.y. taškai, kuriuos jungia kažkiek linijų). Galima pagalvoti, kad grafas irgi yra tolydi struktūra, nes galima tolydžiai slinkti jo briaunomis – tačiau iš tikro tai tik pavaizdavimas (brėžinys), kuriuo galima slinkti, o ne pats grafas. Mus jame tedomina – kurias viršūnes jungia briauna, o tai galima perteikti paprastu išvardijančiu sąrašu.

Ne visus diskrečių struktūrų tyrinėjimus galima apibūdinti kaip kombinatoriką. Kita būdinga srities charakteristika yra ta, kad daugumą jos problemų gerokai lengviau suprasti nei kitose matematikos srityse. O ir įrodymai neretai yra elementarūs – t.y. nereikalauja kokių nors specialių koncepcijų ar nesiremia ankstesniais sunkiai pasiektais rezultatais. Bet tai nereiškia, kad įrodymas yra lengvas – ir kai kurie „elementarūs“ įrodymai yra vieni sudėtingiausių matematikoje. Szemeredi teorema yra puikus to įrodymas.

Tai apie ką ji? Ji susijusi su aritmetine progresija - skaičių seka, kurioje tarp skaičių yra vienodas tarpas, pvz., 3, 9, 15, 21, 27, 33, ...., nes žingsnis sekoje yra 6. Suprasti teoremos esmę padės toks žaidimas. Jums pasako vieną mažą skaičių (tarkim 5) ir vieną didelį skaičių (tarkim 10000). Jums reikia pasirinkti kuo galima daugiau skaičių tarp 1 ir 10000, tačiau turite laikytis vienos taisyklės – iš savo pasirinktų skaičių negalite sudaryti 5-ių (tai pirmas jums pasakytas skaičius) narių ilgio aritmetinės progresijos. Tad jei, tarkim, pasirinksite skaičius 101, 1103, 2105, 3107 ir 4109 – pralošite, nes žingsnis tarp jų yra 1002.

Žaidimas yra pasmerktas – anksčiau ar vėliau turėsite pasirinkti visus skaičius tarp 1 ir 10000, tarp kurių bus daug 5-ių narių ilgio aritmetinių progresijų. Tačiau Szemeredi teorema teigia kažką įdomaus: kad net žaidžiant gerai, pralaimėsite jau ilgai iki to, nei būsite arti visų skaičių pasirinkimo.

Tegu k yra progresijos ilgis, o n - skaičių, tarp kurių galime rinktis, kiekis. S(k,n) pažymėkime didžiausią kiekį skaičių, kuriuos galima pasirinkti išlaikant k ilgio progresijos nesudarymo taisyklę. Tada Szemeredi teorema įrodo, kad kai n yra pakankamai didelis, S(k,n) sudaro tik mažą n procentą. O kokio mažumo? Gerai jau, tokį mažą, kokio tik norite – jei tik n yra pakankamai didelis.

Pvz., jei stengiamės išvengti 23 ilgio progresijų, Szemeredi teorema mums sako, kad yra toksai n (kuris gali būti be galo didelis, tačiau esmė ta, kad jis egzistuoja), kad jei žaisime žaidimą su n skaičių, tai negalime rinktis daugiau kaip n/1000 skaičių (t.y. 0,1%) iki pralaimint. Ir tai teisinga bet kokio ilgio progresijai ir bet kokiam kitam procentui.

Neaiškinsiu, kaip tai įrodoma. Tik priminsiu, kad tai elementaru technine prasme, tačiau kad tai sudėtinga, pailiustruosiu diagrama Szemeredi straipsnio:
Irodymo diagrama

Ši diagrama demonstruoja apytikslį Szemeredi teoremos įrodymo procesą. Įvairūs simboliai turi savo reikšmę: F_k=Fact k; L_k=Lema k; T=Teorema;C=Išvada; D – B, S, P, a, b ir kt. apibrėžimai; t^m - t^m apibrėžimas; vdW – van der Waerden teorema; F₀ - “jei f:R⁺ -> R⁺ yra subadityvi, tada egzistuoja

”.

Sunku rasti situaciją, kada realiame gyvenime prisireiktų 10-ies narių ilgio aritmetinės progresijos? Ir net jei tokia situacija kiltų, pagal Szemeredi teoremą n būtų didesnis už atomų skaičių Visatoje. Tad ši teorema yra už praktinio panaudojimo ribų. Tai kodėl ja taip žavisi matematikai?

Viena iš priežasčių – teiginio paprastumas ir įrodymo sudėtingumas. Taip jau nutinka, kad laikas nuo laiko iškyla klausimai, kad niekas netiki, kad juos galima išspręsti turimomis priemonėmis (pvz, ar e+p yra iracionalus skaičius).
Kita priežastis: Szemeredi teorema turi matematinius pritaikymus. Iš jų pažymėtina Ben Green'o³⁾ ir Terence Tao⁴⁾ teorema, teigianti, kad įmanoma rasti kokio nori ilgio aritmetines progresijas, į kurias įeina tik pirminiai skaičiai. Ji tiesiogiai neseka iš Szemeredi teoremos, tačiau Green ir Tao rado gudrų būdą transformuoti teiginį į formą, leidžiančią panaudoti Szemeredi teoremą.

Jei vis tik rūpi praktiniai taikymai, tada dar ne viskas prarasta, jei tenkina netiesioginiai taikymai. Matematikoje dažnai būna, kad pasiektas rezultatas nėra toks įdomus, kaip metodai, panaudoti jo pasiekimui. Sprendimas dažnai reikalauja naujo įrankio sukūrimo. Tai labai tinka kombinatorikai - ir Szemeredi teorema puiki to iliustracija.

O kas tai ekstremalioji kombinatorika? Štai klausimas iš ekstremaliosios grafų teorijos: jei grafas turi n viršūnių, kiek jame gali būti briaunų neleidžiant jokioms trims sudaryti trikampį? Bendrai imant, ekstremaliojoje kombinatorikoje klausiama, kokio didumo gali būti dydžiai prieš tai, kol kažkas turi įvykti. Tarkim, Szemeredi teorema atsako į klausimą, kiek skaičių galite rinktis tarp 1 in n iki tol, kol būsite priversti įtraukti k ilgio aritmetinę progresiją.

Tokie klausimai natūraliai skirstosi į dvi dalis. Vieni jų ieško struktūrų, kurios leistų kažko išvengti taip, kad dominantis dydis yra kiek gali didesnis. Kiti siekia parodyti, kad jei dydis pasiekia tam tikrą ribą, kai ko neįmanoma išvengti. Erdošo įžvalga buvo ta, kad daugeliu atvejų puikus būdas pasirinkti pirmą dalį yra atsitiktinai rinktis struktūras. Pvz., jei struktūra yra grafas su n viršūnių, yra klausimų, kai gerą atsakymą, ar sujungti dvi viršūnes briauna, duoda monetos metimas. Tačiau daug galime atsakyti, jei klausiame apie tai, kas „beveik tikra“. Ir to pakanka: jei galime tarti, kad atsitiktinai oasirinkta struktūra beveik tikrai turi norimas savybes, tada galima daug silpnesnė išvada, kad bent viena struktūra turi norimas savybes.

Ergošo įžvalga davė pradžią atsitiktinei grafų teorijai, tapusią pagrindiniu kombinatorikos poskyriu. Rezultate atsitiktiniai grafai nelaikomi chaotiškais objektais, objektais, kurie daugeliu atvejų lengvai suprantami. Ne, nereikia sakyti, kad atsitiktinė grafų teorija yra lengva: uždavus labai detalų klausimą atsakymui tenka imtis sudėtingų tikimybinių įverčių. Tačiau vis tik tam tikra prasme atsitiktiniai grafai yra (beveik visad) nuspėjami ir geros elgsenos.

Šis įvadas padės suprasti Szemeredi reguliarumo lemą, iki kurios grafai buvo laikomi nestruktūrizuoti objektai. Mat kai apibrėžiate grafą, visai laisvai pasirenkate kurias viršūnes sujungti. Tačiau Szemeredi nustatė, kad galite visiškai atsitiktiniam grafui suteikti naudingą struktūrinį aprašymą. Grubiai idėja tokia. Duotam grafui yra būdas jo viršūnes paskirstyti į nedidelį aibių kiekį taip, kad jei briaunos jungia bet kurias dvi aibes, jos atrodo tarsi būtų parinktos atsitiktinai. Trumpiau sakant, kiekvienas grafas sudarytas iš nedidelio kiekio panašių į atsitiktinius subgrafų.

Taigi, mes galime pateikti neblogą grafo aprašą panaudojant nedidelį duomenų kiekį. Paskirsčius viršūnes kaip nurodo lema, galime apytiksliai pasakyti, kiek briaunų yra tarp kiekvienos aibių poros ir kad tos briaunos yra paskirstytos taip, kad atrodytų kaip atsitiktinės. Tai mums nenurodo, kaip tiksliai grafas atrodo, tačiau daugeliu atvejų skirtumas tarp dviejų grafų, atrodančių kaip atsitiktiniai, nėra svarbus.

Szemeredi reguliarumo lema greitai tapo ir lieka pagrindiniu ekstremalių grafų teorijos įrankiu, o netiesioginiai, per modifikacijas ir apibendrinimus, dar plačiau.

Szemeredi yra viena trečioji AKS (kiti du – Miklos Ajtai⁶⁾ ir Janos Komlos⁷⁾). Jie kartu sprendė nemažai uždavinių.

Sena tema kompiuterių moksle yra rūšiavimo algoritmai. Tikslas - padaryti tai su kuo mažesniu palyginimų skaičiumi. Jei turite n objektų, palyginimų kiekis yra bent log₂n! (galimų išsidėstymų skaičius yra n!). log n! yra apytiksliai lygu n log n. O štai AKS sukūrė gudrų rūšiavimo algoritmą, reikalaujantį tik log n palyginimų (kitaip sakant, AKS sukūrė greitą lygiagretų rūšiavimo algoritmą). Esmė – objektai atsitiktinai pakartotinai dalijami į dvi grupes.

Trikampis grafas yra grafas, kurio visos trys vršūnės yra tarpusavyje sujungtos. Nepriklausomas subgrafas yra sudarytas iš viršūnių, kuri nė viena nėra sujungta. Grafas su k² viršūnių privalo turėti apimti arba trikampį grafą arba k dydžio nepriklausomą subgrafą. Teisingas ir griežtesnis teiginys: tam užtenka ir k(k-1) +1 viršūnės. Bet ar egzistuoja grafai su k(k-1) viršūne, kurie neturėtų trikampio subgrafo ar nepriklausomo k dydžio subgrafo? Jei ne, tai su kiek viršūnių būtų toks grafas? Didžiausias toks galimas skaičius vadinamas Ramzio skaičiumi R(3,k).

AKS 1980 m. įrodė, kad R(3,k) yra daugiausiai k²/log k. Šį rezultatą buvo labai sunku pagerinti. Ir tik po 15 m. (1995 m.) Jeong Han Kim⁵⁾ įrodė, kad tasai rezultatas yra geriausias, t.y. kad R(3,k) ir yra k²/log k.

¹⁾ Palas Erdošas (Pal Erdos, 1913-1996) – ekscentriškas vengrų matematikas, sėkmingai darbavęsis įvairiose srityse: kombinatorikoje, grafų, skaičių teorijose, matematinėje analizėje, aibių ir tikimybių teorijoje ir t.t. Daugelio apdovanojimų laureatas ir pats įsteigęs Erdošo premiją. Parašė per 1500 straipsnių (vienas ir su bendraautoriais) – kas palyginama tik su Oilerio straipsnių skaičiumi.
Jį galima pavadinti „klajojančiu matematiku“ – gyvenimą praleido keliaudamas po konferencija ir kolegų namus. Jis pasirodydavo ant slenksčio su žodžiais „mano smegenys atviri“ ir likdavo, kol parengdavo bendrus straipsnius. Mielai su kitais dalinosi savo idėjomis. Į žurnalistų klausimą ar ne per daug jis pesimistiškas, atsakė: „Žmogus gyvena neilgai ir ilgam miršta“. Jis piktnaudžiavo stipria kava ir amfetaminais. Mirė nuo insulto Lenkijoje; kišenėje jau buvo bilietas į Vilnių, kur turėjo dalyvauti kitoje konferencijoje.
Taip pat skaitykite >>>>>

²⁾ Palas Turanas (Pal Turan, 1910-1976) – žydų kilmės vengrų matematikas, daugiausia dirbęs skaičių teorijos srityje. Sukūrė ekstremalią grafų teoriją – joje jo teorema apie briaunų kiekį viena svarbiausių. 1934 m. įrodė Hardi-Ramanudžano teoremą apie skaičiaus n skirtingų pirminių daliklių kiekį. Taip pat sukūrė galių sumavimo metodą dirbant su Rymano hipoteze. Ilgai (46 m.) bendradarbiavo su P. Erdošu ir bendrai parašė 28 straipsnius. Erdošo-Turano teiginys susijęs su pirminiais skaičiais aritmetinėje progresijoje.

³⁾ Benas Grynas (Ben Joseph Green, g. 1977 m.) – britų matematikas, kurio specializacija kombinatorika ir skaičių teorija; Oksfordo profesorius. 2004 m. kartu su T. Tao įrodė, kad tarp pirminių skaičių yra be galo daug duoto ilgio aritmetinių progresijų (teiginys suformuotas kažkur po 1770 m.). Tas įrodymas yra Szemeredi teoremos išplėtimas.

⁴⁾ Terensas Tao (Terence Chi-Shen Tao, g. 1975 m.) – australų kilmės amerikiečių matematikas, dirbantis skaičių teorijos, kombinatorikos, diferencialinių lygčių dalinėmis išvestinėmis, reprezentacijų teorijos ir kt. srityse; Kalifornijos un-to profesorius. Labiausiai žinomas kartu su B. Grynu įrodyta teorema apie pirminių skaičių aritmetines progresijas. 2006 m. Fieldso medalio laureatas. Pasižymi intensyviu darbu su kitais matematikais, aktyviu matematikos populiarinimu tinklaraštyje.
Plačiau apie jį skaitykite >>>>>

⁵⁾ Džeongas Kimas (Jeong Han Kim, g. 1962 m.) – Pietų Korėjos matematikas. Pagrindinės turimų sritys yra kombinatorika ir kompiuterinė matematika. Didžiausias jo pasiekimas – įrodymas, kad Ramzio skaičius R(3,k) turi asimptotinį įvertinimą lygų k²/log k – už tai 1997 m. gavo Fulkersono premiją.

⁶⁾ Miklošas Aitajus (Miklos Ajtai, g. 1946 m.) – vengrų kilmės amerikiečių kompiuterių mokslo specialistas, dirbantis IBM tyrimų srityje. 2003 m. gavo Knuto premiją už indėlį kompiuterijoje, įskaitant klasikinį tinklinį rūšiavimo algoritmą, sukurtą kartu su J. Komlošu ir E. Szemeredi (su kuriais įrodė ir daugiau teiginių iš kombinatorikos). Daug dirbo su gardelių klausimais. 1997 m. su C. Dwork‘u pasiūlė gardele pagrįstą viešo rakto kriptosistemą.

⁷⁾ Janas Komlošas (Janos Komlos, g. 1942 m.) – vengrų kilmės amerikiečių matematikas, dirbantis tikimybių teorijos ir diskrečiosios matematikos srityse; Rutgerso un-to profesorius (nuo 1988 m.). Yra parašęs plačiai cituojamų straipsnių apie atsitiktinių kintamųjų sumas, atsitiktines matricas, derandomizaciją ir kitais klausimais.