Om 12 uur werd in Oslo bekend gemaakt dat Endre Szemerédi winnaar is van de Abelprijs 2012. Er werd telefonisch contact met hem gezocht en dit was live te volgen via internet. In een eerste reactie toonde Szemerédi zich bescheiden: “Ik ben erg blij met de prijs, maar moet er ook bij zeggen dat er andere wiskundigen bestaan die de prijs meer verdienen.”

Met het toekennen van de Abelprijs, een geldbedrag van 6 miljoen Noorse kronen (ongeveer 800.000 euro of 1 miljoen dollar), erkent de Noorse Academie van Wetenschappen Szemerédi’s ‘diepgaande en blijvende impact’ op de discrete wiskunde en de theoretische informatica.

Discrete wiskunde gaat over wiskundige structuren van ‘discrete’ objecten. De term ‘discreet’ wordt hier gebruikt in tegenstelling tot ‘continu’; er zitten als het ware ‘gaten’ tussen de discrete waarden, bijvoorbeeld tussen de natuurlijke getallen 1, 2, 3, 4, …

Bekende deelgebieden van de discrete wiskunde zijn combinatoriek, grafentheorie en getallenrijen.

Szemerédi was een van de eerste wiskundigen die het fundamentele belang van de discrete wiskunde voor de theoretische informatica erkenden. Het internet is bijvoorbeeld niets anders dan een graaf.

Een graaf bestaat uit een verzameling punten, verbonden door lijnen of, in het geval van een gerichte graaf, pijlen. Het internet is een voorbeeld van een reusachtige gerichte graaf, met websites als punten en de hyperlinks als pijlen. Deze graaf is gericht, omdat een hyperlink van de ene site verwijst naar een andere, maar niet andersom (twee sites kunnen naar elkaar verwijzen, maar dat vergt twee aparte links). De afbeelding hiernaast geeft het wereldwijde web weer als graaf.

Flickr, NetMapper via CC BY-NC 2.0

Flickr, NetMapper via CC BY-NC 2.0

Van fabrieksarbeider tot miljonair

Endre Szemerédi werd geboren op 21 augustus 1940 in de Hongaarse hoofdstad Boedapest. In tegenstelling tot de meeste grote wiskundigen kreeg hij pas op relatief hoge leeftijd een passie voor wiskunde. Hij studeerde een jaar lang medicijnen en werkte in een fabriek, voordat hij de overstap naar de wiskunde maakte.

Hij studeerde aan de Loránd Eötvös Universiteit, waar zijn talent tijdens de studentencolloquia werd opgemerkt door de vermaarde Paul Erdös. Szemerédi promoveerde in 1970 aan de Staatsuniversiteit van Moskou bij Israel Gelfand. Hij is verbonden aan het Alfréd Rényi Instituut voor Wiskunde in Hongarije, een plek die hij sinds 1986 deelt met Rutgers-universiteit in de Amerikaanse staat New Jersey.

Nils Christian Stenseth, de president van de Noorse Academie van Wetenschappen, maakt bekend dat Endre Szemerédi de winnaar is van de Abelprijs 2012. Tijdens een feestelijke ceremonie op 22 mei zal koning Harald de Abelprijs – een cheque ter waarde van 6 miljoen Noorse kronen – aan Szemerédi overhandigen.

Szemerédi publiceerde meer dan 200 artikelen en veel van zijn ontdekkingen dragen inmiddels zijn naam. Om er een paar te noemen: Szemerédi-Trotter stelling, Ajtai-Komlos-Szemerédi semi-random methode, Erdös-Szemerédi som-product-stelling, Balog-Szemerédi-Gowers lemma. Zijn beroemdste resultaat is ongetwijfeld zijn bewijs van het Erdös-Turán-vermoeden, dat inmiddels de Stelling van Szemerédi heet.

Szemerédi’s stelling en rekenkundige rijen

Een rekenkundige rij is niets anders dan een rij getallen waarvoor geldt dat het verschil tussen twee opvolgende getallen steeds hetzelfde is. Een voorbeeld van een rekenkundige rij ter lengte 5 is het rijtje 2, 5, 8, 11, 14: het verschil is steeds 3.

Een stelling van de Nederlandse wiskundige Bartel van der Waerden zegt dat bij iedere partitie van de verzameling natuurlijke getallen (1, 2, 3, …) in twee delen, ten minste één van de delen willekeurig lange rekenkundige rijen bevat. In 1936 leidde dit bij Paul Erdös en zijn naam- en landgenoot Paul Turán tot het volgende vermoeden: elke verzameling van natuurlijke getallen met positieve dichtheid bevat willekeurig lange rekenkundige rijen.

Ruwweg kun je zeggen dat de dichtheid van een verzameling de fractie is van het aantal natuurlijke getallen dat tot die verzameling behoort. Bijvoorbeeld de verzameling van even getallen (2, 4, 6, …) heeft dichtheid 0,5, omdat ‘de helft van alle natuurlijke getallen even is’.

Timothy Gowers betreedt het podium tijdens de ceremonie op 21 maart, om te vertellen over het werk van Szemerédi.

Bijna veertig jaar later, in 1975, gaf Szemerédi een bewijs van het Erdös-Turán-vermoeden. Dit betekende een doorbraak in de discrete wiskunde. Om het vermoeden alleen voor het geval van rekenkundige rijen van lengte 3 te bewijzen (dit deed de Brit Klaus Roth in 1956), was al een tour de force. Laat staan het algemene geval.

Szemerédi’s bewijs, dat bijna vijftig bladzijden lang is, berust op een ontbinding van een bipartiete graaf in componenten die ‘bijna regulier’ zijn, gevolgd door een ingewikkeld inductieproces.

Veel van de problemen die Erdös voorstelde, voorzag hij van een moeilijkheidsgraad door voor de oplossingen geldprijzen uit te loven. De hoogste prijs die Erdös ooit betaald heeft, was aan Szemerédi, 3000 dollar. Dit nieuws ging destijds als een lopend vuurtje de wereld rond.

Het belang van Szemerédi’s bewijs blijkt wel uit de resultaten die hierna werden geboekt, gebruikmakend van Szemerédi’s werk. Een recent resultaat is de stelling van Tao en Green uit 2004, die zegt dat de rij priemgetallen rekenkundige rijen van willekeurige lengte bevat. Dit is echt een uitbreiding van Szemerédi’s stelling, want de verzameling priemgetallen heeft dichtheid nul: ondanks dat er oneindig veel priemgetallen bestaan, zijn ze zo dun gezaaid dat het percentage priemgetallen kleiner dan n naar nul convergeert, voor n naar oneindig. Dat volgt uit de priemgetalstelling, die zegt dat de fractie priemgetallen kleiner dan n ongeveer gelijk is aan 1/ln(n).

Zie ook:

• De officiële website van de Abelprijs (Noors/Engels)
• Eindeloze priemen (Kennislinkartikel over de stelling van Tao en Green)
• Erdős’ vermoeden over rekenkundige rijen (Kennislinkartikel over een ander, nog onopgelost vermoeden van Erdös uit 1981)

Kennislinkartikelen over de Abelprijs:

Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/abelprijs.atom", “max”=>"10", “detail”=>"minder"}