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.
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.
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’.
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"}