Gesneuveld vermoeden

Bob Hough krijgt straks duizend dollar beloning voor het weerleggen van een Erdös-probleem. Maar het is vooral de eer.

Het gebeurt niet elke dag dat iemand een bewijs geeft van een vermoeden van de Hongaarse wiskundige Paul Erdös. En nog zeldzamer: een weerlegging. De Amerikaan Bob Hough, afkomstig van Stanford University en sinds kort postdoc aan de universiteit van Cambridge, ontkrachtte in Erdös’ honderdste geboortejaar het zogeheten ‘overdekkingsvermoeden’ van Erdös.

Het bewijs van Hough staat nu nog in de databank van Arxiv.org maar zodra het manuscript door een tijdschrift geaccepteerd wordt, ligt er een cheque van duizend dollar klaar voor Hough, het bedrag dat Erdös reserveerde voor een oplossing van het overdekkingsvermoeden. Een symbolisch bedrag, Erdös was nu eenmaal geen miljonair. Veel belangrijker dan het geld is de eer tot de wiskundigen te behoren die een probleem van Erdös wisten op te lossen.

Erdös (1913-1996) geldt als een fenomeen. Met meer dan 500 collega-wiskundigen publiceerde hij ruim 1.500 artikelen. Vanaf zijn veertigste had hij geen vaste woonplaats, maar reisde hij tot aan zijn dood over de hele wereld, rondkomend van hetgeen gastdocentschappen aan universiteiten en lezingen bij conferenties hem opleverden. Overnachten deed hij bij collega’s.

Het doen van schijnbaar eenvoudige uitspraken in de wiskunde was een groot talent van Erdös. Hij had een fantastische intuïtie en stelde talloze vermoedens op die wiskundigen prikkelden. Voor veel problemen stelde hij geld beschikbaar voor degene die met een oplossing kwam. Dat het allerminst om eenvoudige problemen ging, blijkt wel uit het feit dat ook nu nog lang niet alle problemen zijn opgelost.

Simpelste regelmaat

Het overdekkingsprobleem, dat dit jaar dus is opgelost, gaat over rijen getallen met de simpelst denkbare regelmaat: het verschil tussen twee opeenvolgende getallen is steeds hetzelfde. Een voorbeeld van zo’n rekenkundige rij is 1, 4, 7, 10, 13, ...: het verschil tussen de getallen is steeds 3. Als we naast deze rij nog de volgende twee rijen zetten: 2, 5, 8, 11, ... en 3, 6, 9, 12, ..., dan valt onmiddellijk op dat elk natuurlijk (dat wil zeggen: positief, geheel) getal een keer voorkomt in een van deze drie rijen.

Erdös noemde een serie rekenkundige rijen een ‘overdekkingssysteem’ als elk natuurlijk getal voorkomt in ten minste één van de rijen uit de serie. Het voorbeeld van zo-even is simpel: élke rij heeft verschil 3. Op deze manier is het kinderspel om een overdekkingssysteem te vinden. Anders wordt dit wanneer elke rij een ánder verschil moet hebben. Het eenvoudigste overdekkingssysteem onder deze voorwaarde bestaat uit vijf rijen (zie kader Overdekking).

In 1934 vroeg Erdös zich af of het waar is dat er voor elke willekeurige waarde x een overdekkingssysteem bestaat als geldt dat elk verschil groter is dan x (en verschillend, uiteraard). Hij vermoedde dat het antwoord ja was, maar kon dit zelf niet bewijzen. In 1995, een jaar voor zijn dood, zei hij erover: „Dit is misschien wel mijn favoriete probleem.” En dat zegt wat, voor iemand die in zijn leven duizenden problemen heeft langs zien komen.

Meer dan 1050 rekenkundige rijen

Nu is er dus Bob Hough, die heeft aangetoond dat Erdös’ intuïtie er nu eens naast zat: er zit een grens aan hoe groot het kleinste verschil binnen een overdekkingssysteem kan worden. Recordhouder op dit moment is Pace Nielsen (Brigham Young University). Hij toonde in 2008 hij het bestaan aan van een overdekkingssysteem met als kleinste verschil 40. Daarvoor had hij wel meer dan 1050 rekenkundige rijen nodig. Als Erdös’ vermoeden waar zou zijn, zou er een overdekkingssysteem moeten bestaan met een groter kleinste verschil. Nu het vermoeden is weerlegd, is het niet ondenkbaar dat Nielsens systeem de absolute kampioen is. In elk geval bestáát er een absolute kampioen. Zoveel is dankzij het werk van Hough zeker.

Houghs bewijs berust voor een belangrijk deel op een gewiekste toepassing van een stelling uit de kansrekening die in 1975 werd bewezen door de Hongaars-Amerikaanse wiskundige László Lovász. Hough presenteerde zijn resultaat afgelopen zomer tijdens de ‘Erdös Centennial’ in Boedapest, een congres gewijd aan Erdös’ honderdste geboortejaar. De afgelopen maanden heeft de kersverse Cambridge-postdoc zijn lezing op diverse universiteiten herhaald.

Houghs artikel is nog niet in een internationaal vaktijdschrift gepubliceerd, maar dat lijkt een kwestie van tijd. Referenten lopen elke stap in het bewijs zorgvuldig na en het is niet ongebruikelijk dat ze daar maanden voor uittrekken. Ben Green en Terence Tao, twee wiskundigen die in dit deelgebied van de wiskunde tot de wereldtop behoren, reageren in een e-mail positief op Houghs werk. „Voor zover ik weet, is het correct”, aldus Tao.