De eenzame loper

Wiskunde ‘Vermoeden van de eenzame loper’ is de poëtische naam van een vijftig jaar oud wiskundig probleem. Nog altijd onopgelost, maar nieuw onderzoek van de bekende wiskundige Terence Tao heeft wel een paar interessante bevindingen opgeleverd.

Illustratie Studio NRC, bron Luis Goddyn

Een jaar geleden zette een wiskundige een bewijs online van een lang openstaand probleem, bekend als het ‘vermoeden van de eenzame loper’. Meer dan vier pagina’s had Matthias Beck van de San Francisco State University niet nodig om aan te tonen dat ‘elke loper wel eens eenzaam is’ [pdf]. Wat wiskundigen met ‘eenzame lopers’ bedoelen? Dat komt zodadelijk.

Beck is een gerespecteerd wiskundige. In 2013 won hij de Deborah and Franklin Tepper Haimo Award, een prijs die de Mathematical Association of America jaarlijks toekent aan drie universitaire wiskundigen die uitzonderlijk goed doceren en motiveren. „Hij is een voorbeeld van het feit dat onze beste leraren meestal onze beste onderzoekers zijn, en vice versa”, reageerde de leiding van de San Francisco State University trots.

In de laatste regel maakte Beck een pijnlijke uitglijer: weg bewijs

Maar gerespecteerd of niet, iedereen maakt fouten. Becks bewijs van het vermoeden van de eenzame loper trok de aandacht van Terence Tao (University of California, Los Angeles). Tot de een-na-laatste regel kon hij geen fout ontdekken. Maar toen ging het mis: in de laatste regel maakte Beck een pijnlijke uitglijer. Weg bewijs.

De uit Australië afkomstige Tao is 42 jaar, won als tienjarig jochie een medaille op de Internationale Wiskunde Olympiade, heeft inmiddels een publicatielijst met meer dan driehonderd papers, en onder het kopje ‘Awards’ op zijn Wikipedia-lemma staan 21 prijzen vermeld, waaronder de Fields Medal en de Breakthrough Prize in Mathematics. Hij houdt een weblog bij waarop hij zijn eigen en andermans resultaten bespreekt. De vraag of je een genie moet zijn om wiskunde te doen, beantwoordt hij op zijn blog met een vetgedrukt ‘no’. Hard werken is een vereiste om zo ver te komen, wil hij maar zeggen. Al zal niemand ontkennen dat Tao veel talent heeft.

Tao bewees dat elke loper ooit wel eens ‘enigszins eenzaam’ is

Ondanks deze indrukwekkende lijst van feiten, kon Tao die laatste regel in Becks bewijs niet dusdanig omwerken dat een rotsvaste redenering zou ontstaan. Het probleem liet hem echter niet los. Oplossen lukte niet, maar Tao bereikte wel een paar interessante tussenresultaten. Die hebben de peer review inmiddels doorstaan en worden binnenkort gepubliceerd in het tijdschrift Contributions to Discrete Mathematics.

Kettingbreuken

Het vermoeden van de eenzame loper werd voor het eerst geformuleerd in 1967, door de Duitser Jörg Wills. Met lopers had het niks te maken – die poëtische naam is dan ook van later. In zijn oorspronkelijke vorm ging het probleem over benaderingen van irrationale getallen, zoals π, met behulp van zogenaamde kettingbreuken. Later bleek dat Wills’ probleem op diverse andere manieren geformuleerd kan worden: in termen van ‘chromatische getallen van gewogen grafen’, ‘reguliere matroïden’ of ‘view obstructions’. Stuk voor stuk deelgebieden van de wiskunde die allemaal gebaat zijn bij een bewijs van dat ene vermoeden. Een wiskundig probleem staat zelden op zichzelf.

Het vermoeden dankt zijn naam aan een formulering – in 1998 gevonden door de Canadees Luis Goddyn – die voor outsiders goed te begrijpen is. Een aantal lopers (wiskundigen noemen dat aantal n) lopen op een cirkelvormige baan. De lengte van één ronde is precies één kilometer. Voor wiskundigen doet die eenheid er trouwens niet toe; zij spreken gewoon van ‘lengte 1’. De lopers starten gelijktijdig vanaf hetzelfde punt. Ze doen geen wedstrijd; voor een Usain Bolt is er niet meer eer te behalen dan voor recreanten. Elke loper heeft een constante snelheid en alle snelheden zijn verschillend. De lopers hebben geen aanloopproblemen en worden ook nooit moe; direct vanaf het startschot lopen ze allemaal eeuwigdurend, rondje na rondje, in hun eigen, constante tempo.

Een loper is ‘eenzaam’ als hij minstens 1/n kilometer van alle andere lopers verwijderd is. Eenzaamheid is dus een relatief begrip. Ben je met zijn tweeën, ben je eenzaam zodra de ander 1/2 van jou vandaan is. Met drie lopers ben je eenzaam als de andere lopers minstens 1/3 van jou verwijderd zijn, met vier lopers minstens 1/4, enzovoorts. Het vermoeden luidt dat elke loper op een zeker moment eenzaam is. Verschillende lopers natuurlijk op verschillende tijdstippen. Het kader gaat over een situatie met vier lopers.

Aan de situatie met twee lopers valt wiskundig niets te beleven. Zij zijn eenzaam op het moment dat ze diametraal tegenover elkaar staan en omdat hun snelheden verschillend zijn, is het duidelijk dat dat moment ooit komen gaat. Hoe zit het met drie lopers? Wiskundigen zijn geneigd om ook dit geval af te doen als ‘triviaal’, of ze laten het als ‘opgave voor de lezer’. Voor de leek is het echter helemaal niet zo evident. Voor een waterdichte redenering moet je twee verschillende situaties onderscheiden. De oplossing staat in het andere kader.

Bar weinig bekend

Vanaf vier lopers is het eenzame-loper-probleem ook voor wiskundigen tricky. Vijf jaar nadat Wills zijn vermoeden formuleerde, bewees hij de juistheid voor n=4. Het geval n=5 werd in 1984 bewezen, n=6 volgde in 2001 en n=7 in 2008. Al die bewijzen staan op zichzelf; geen ervan bevat een argument dat gemakkelijk gegeneraliseerd kan worden. Daarom is er, los van de speciale gevallen tot en met zeven lopers, bar weinig bekend. Niemand weet of het vermoeden voor meer dan zeven lopers waar is.

Een van de moeilijkheden is de snelle toename van het aantal situaties, die allemaal afzonderlijk nagevlooid moeten worden. Zijn er bij drie lopers twee te onderscheiden situaties, bij acht lopers zijn dat er al vijfentwintig.

Een andere complicatie is dat er geen enkel voorbehoud is met betrekking tot de snelheden van de lopers. Loopt de eerste loper met een snelheid van 1 kilometer per uur, de tweede 2 km/uur, de derde 3 km/uur en zo verder, dan is elke loper wel eens eenzaam; dát concrete geval is wel voor elke n bewezen. Maar bij het eenzame-loper-vermoeden is élke snelheid toegestaan: 1, 100, √2 of π kilometer per uur, het kan allemaal.

Wat dit betreft zijn wel vereenvoudigingen te maken. Wills toonde al aan dat het voldoende is om alleen geheeltallige snelheden te onderzoeken. Als het vermoeden voor die gevallen bewezen is, is het voor álle gevallen bewezen – wat overigens helemaal niet vanzelfsprekend is.

Ook mag je alle snelheden met eenzelfde factor vergroten of verkleinen, of van elke snelheid een vaste snelheid aftrekken. Dus als drie lopers met snelheden 2, 3 en 7 lopen, is dat gelijkwaardig met de situatie waarbij de snelheden 0, 1 en 5, of -1 (achteruit lopen met snelheid 1), 0 en 4 zijn. Dat laatste is een erg nuttige vereenvoudiging, omdat eenzaamheid het makkelijkst is aan te tonen voor iemand die stilstaat (snelheid 0). Ook is het geen beperking om de snelheden positief te veronderstellen: voor de afstand tot degene met snelheid 0 maakt het niet uit of iemand met snelheid -1 of +1 loopt.

Tao heeft nu bewezen dat je het aantal te onderzoeken gevallen nog verder kunt uitdunnen. Je mag aannemen dat de snelheden elementen zijn van een rekenkundige rij. Dat is een rij getallen met gelijke onderlinge afstand, zoals 1, 4, 7, 10, … De snelheden hoeven geen aaneensluitende elementen te zijn; er kunnen bijvoorbeeld lopers zijn met snelheden 1, 4 en 10, terwijl 7 ontbreekt. Ook heeft Tao een zwakke versie van het vermoeden bewezen: hij liet zien dat elke loper ooit ‘enigszins eenzaam’ is. Wat dat betekent? Dat de afstand tot elke andere loper minstens 1/(2n–2) + c log(n–1)/((n–1)2 (log log n – 1)2) is. Dat is weliswaar minder dan 1/n, waar het in het vermoeden om draait, maar meer dan de reeds gekende ondergrens. Die c in Tao’s formule is een constante die expliciet berekend kan worden, maar die moeite heeft Tao niet genomen. Hij blijft een echte theoreticus.

    • Alex van den Brandhof