Je leest:

Erdős’ vermoeden over rekenkundige rijen

Erdős’ vermoeden over rekenkundige rijen

Auteur: | 20 januari 2011

Getaltheorie was een van de lievelingsonderdelen uit de wiskunde van Paul Erdős. De deur naar een oplossing van een nog immer openstaand probleem van deze Hongaar staat inmiddels op een kier, dankzij het werk van wiskundige Tom Sanders.

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 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 1/a1 + 1/a2 + 1/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, 4, 5, 8} en {2, 3, 6, 7} laat zien dat het met W = 8 niet lukt: géén van beide deelverzamelingen bevat een 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 het volgende:

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 1/a1 + 1/a2 + 1/a3 + … divergeert, dan bevat de verzameling {a1, a2, a3, …} een rekenkundige rij van lengte 3.

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 20 januari 2011

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.