Paul Erdös
Sinds het Vermoeden van Poincaré is opgelost door de Rus Grigori Perelman, is de wiskunde één millenniumprobleem armer. Hoewel er nog zes millenniumproblemen open staan – genoeg werk aan de winkel, zou je zeggen – wordt er al volop gespeculeerd over welk probleem het door Perelman ontstane gat kan vullen. Volgens sommige wiskundigen is het volgende vermoeden van de Hongaar Paul Erdös een goede kandidaat:
Als A = {a1, a2, a3, …} een verzameling is die uit natuurlijke getallen bestaat en de som a1 + a2 + a3 + … divergeert (dat wil zeggen: wordt willekeurig groot), dan bevat A rekenkundige rijen van willekeurige lengte.
Een rekenkundige rij is een rij getallen waarvoor geldt dat het verschil van elk tweetal opvolgende termen altijd hetzelfde is. Een voorbeeld is de rij 2, 5, 8, 11, 14: het verschil is steeds 3.
De geschiedenis van het Vermoeden van Erdös gaat terug tot 1927. In dat jaar publiceerde de Nederlandse wiskundige Bartel van der Waerden de volgende stelling:
Voor elk paar getallen k en l bestaat er een getal W (= W(k, l)) met de volgende eigenschap: bij elke opsplitsing van de verzameling {1, 2, 3, …, W} in k deelverzamelingen, is er een deelverzameling te vinden die een rekenkundige rij van lengte l bevat.
Bartel van der Waerden
Neem je bijvoorbeeld k = 2 en l = 3, dan geldt W = 9 (of groter, natuurlijk); de tweedeling {1, 2, 4, 5} en {3, 4, 6, 8} laat zien dat het met W = 8 niet lukt (de eerste deelverzameling bevat géén rekenkundig rijtje van lengte 3).
Er bestaan verschillende bewijzen voor de Stelling van Van der Waerden – combinatorisch, dynamisch, verzameling-theoretisch en analytisch. Geen van die bewijzen geeft echter informatie over de optimale waarde van W. We zagen zojuist dat voor k = 2 en l = 3 die optimale waarde 9 is. Die waarde is met een beetje proberen gauw gevonden, maar voor grote waarden van k en l wordt dat een stuk lastiger.
Dichterbij dankzij Tom Sanders
Erdös en zijn landgenoot Paul Turan vroegen zich in 1936 af hoe groot een willekeurige deelverzameling van {1, 2, 3, …, n} moet zijn, opdat die deelverzameling zeker een rekenkundige rij van gegeven lengte l moet hebben. Voor l = 3 gaf de Brit Klaus Roth in 1956 een antwoord op deze vraag. Voor willekeurige waarden van l was het de Hongaar Endre Szemerédi die er, bijna twintig jaar later, iets over kon zeggen. Hij bewees in 1975 dat er een constante d moet bestaan, zodat het volgende geldt:
Endre Szemerédi
Er bestaat een getal d zó, dat voor grote waarden van n geldt: elke deelverzameling A van {1, 2, 3, …, n} waarvan het aantal elementen minstens gelijk is aan n/(log n)d, bevat een rekenkundige rij van lengte 3.
Szemerédi kon echter niet aangeven wat de waarde van d is. De Belg Jean Bourgain was de eerste die het concreet wist te maken; hij bewees:
Voor grote waarden van n geldt: elke deelverzameling A van {1, 2, 3, …, n} waarvan het aantal elementen minstens gelijk is aan n√((log log n)5/log n), bevat een rekenkundige rij van lengte 3.
Deze ondergrens is nog behoorlijk grof. Bourgain wist de grens n√((log log n)5/log n) zelf iets te verbeteren, maar een forse vooruitgang moest wachten tot 2010. Vorig jaar bewees Tom Sanders, fellow op het Christ’s College in Cambridge, namelijk het volgende:
Voor grote waarden van n geldt: elke deelverzameling A van {1, 2, 3, …, n} waarvan het aantal elementen minstens gelijk is aan n(log log n)5/log n, bevat een rekenkundige rij van lengte 3.
Tom Sanders
Oké, zul je zeggen, maar who cares? Wel, het resultaat van Sanders is voor getaltheoretici van groot belang, want het geeft nieuwe inzichten in de optimale waarde van W(k, 3). We weten nu dat deze optimale waarde hoogstens gelijk is aan 2k(log k)5.
En, nog veel belangrijker: Sanders’ resultaat brengt ons een stap dichter bij de ‘nieuwe heilige graal’, namelijk het vermoeden van Erdös. Het nieuwste grote resultaat over dit vermoeden stamt uit 2004, toen Terence Tao en Ben Green bewezen dat de verzameling priemgetallen willekeurig lange rekenkundige rijen bevat. Als Sanders zijn resultaat nog iets verder weet aan te scherpen, dan is een nieuw speciaal geval van Erdös’ vermoeden bewezen: als a1 + a2 + a3 + … divergeert, dan bevat de verzameling {a1, a2, a3, …} een rekenkundige rij van lengte 3.
Zie ook:
- A breakthrough result on density and 3-AP’s
- De Stelling van Van der Waerden (Nieuw Archief voor Wiskunde; pdf)
"
