Het Hirsch-vermoeden werd in 2010 ontkracht; de Spaanse wiskundige Francisco Santos ontdekte een tegenvoorbeeld voor een vermoeden dat al vijftig jaar onopgelost was. Een prestatie van formaat. Hoe gaat zo een ontdekking in zijn werk? In een recent interview in de nieuwsbrief van de European Mathematical Society vertelt Santos over zijn inspiratiebronnen en zijn werkwijzen.
In 2010 stierf een 50 jaar oud wiskundig idee. Het Hirsch-vermoeden, een stelling uit de discrete meetkunde en grafentheorie, werd eindelijk met een ingewikkeld voorbeeld ontkracht. De wiskundige Francisco Santos ontdekte het tegenvoorbeeld. Maar hoe ontdekte hij dat? Deed hij het alleen, of had hij veel hulp?
Wat is het Hirsch-vermoeden?
Het Hirsch-vermoeden is een idee uit de grafentheorie. Het stelt dat voor een speciaal soort figuur (een zogenaamde polytoop) met n randen (of facetten, zoals de nette wiskundige term is) in dimensie d, de diameter van deze figuur maximaal n-d is. Een beetje uitleg past hier wel bij. Omdat we het hier over discrete meetkunde en grafentheorie hebben en niet over ‘gewone’ meetkunde, betekent het woord diameter iets anders dan je misschien gewend bent.
Voor dimensie d=2 is een polytoop een veelhoek en zijn de facetten de zijden van die veelhoek. Voor dimensie d=3 is een polytoop een veelvlak (zoals een kubus of een octaëder, maar het veelvlak hoeft niet regelmatig te zijn). Dan zijn de facetten de zijvlakken van dat veelvlak en elk zijvlak is een veelhoek. De zijden van de zijvlakken vormen de ribben van het veelvlak en de hoekpunten van de zijvlakken (dit zijn ook de eindpunten van de ribben) vormen de hoekpunten van het veelvlak. De ribben samen met de hoekpunten van zo’n veelvlak vormen een graaf. Over zulke grafen gaat het Hirsch-vermoeden.
Als in een graaf twee punten met elkaar verbonden zijn dan is hun afstand het kleinste aantal lijnen dat je moet doorlopen om van het ene punt naar het andere punt te gaan. De diameter van een graaf is de maximale afstand tussen twee punten die op die graaf voorkomt. Voor dimensie d=4 wordt het al moeilijker om het je voor te stellen, maar daar is elk facet van de polytoop een (drie-dimensionaal) veelvlak. Daarvan zijn de randen veelhoeken. Hun zijden en hoekpunten vormen de ribben en hoekpunten van de polytoop en dat levert weer een graaf. Zo kun je deze begrippen voor steeds hogere dimensie opbouwen.
Het is relatief eenvoudig om te zien dat het Hirsch-vermoeden waar is voor dimensie d=2. Ook voor d=3 is het bewezen. Hoewel het geen bewijs is, kan je het zelf ook testen door een graaf te maken op papier die behoort bij een veelvlak (bijvoorbeeld een tetraëder of een octaëder) en de diameter te berekenen volgens de regels hierboven.
De interesse van Santos in het Hirsch-vermoeden ontstond toen hij bezig van met promoveren. Op dat moment las hij een wiskundeboek waarin het Hirsch-vermoeden besproken werd. Interessant, maar verder dacht hij er niet veel aan. Totdat hij in 2007-2008 tijdens een sabbatical veel tijd had om te werken aan het vermoeden met een collega op de universiteit van Californië. Na een jaar van intensief onderzoek begon hij lezingen te geven over het vermoeden.
“Maar misschien nog wel belangrijker dan dat jaar,” vertelt hij in het interview, “was mijn ontmoeting met Victor Klee in 2002. Hij was na zijn pensioen op een conferentie waar ik een tegenvoorbeeld van een ander vermoeden gaf. Hij stapte op me af en zei ‘je bent goed in tegenvoorbeelden; waarom probeer je niet Hirsch te ontkrachten?” Jaren later dacht Santos hieraan terug en zag dat het Hirschvermoeden misschien inderdaad wel te ontkrachten was.
Idee en tegenvoorbeeld
In die tijd was het namelijk nog steeds onduidelijk of het vermoeden klopte of niet. Voor d=3 en voor d=4 met n hoogstens 12 bleek de stelling waar. En Klee had samen met Walkup een tegenvoorbeeld gemaakt in hogere dimensies voor een onbegrensde polytoop. Het resterende Hirsch-vermoeden betrof dus begrensde polytopen.
Het hele vermoeden was dus nog nooit voor alle dimensies bewezen of ontkracht. “Ik heb nooit echt bewust een keuze gemaakt om een tegenvoorbeeld te zoeken,” zegt Santos. “Maar Klee had daar al wat aan gedaan en toen ik dat voorbeeld echt helemaal begreep, dacht ik dat het misschien wel uitgebreid kon worden. Dat uitbreiden leek me zelfs zó simpel, dat ik begon te vermoeden dat er goed werk te doen viel aan de tegenvoorbeeldkant.”
Uiteindelijke ontdekte Santos een tegenvoorbeeld van een figuur met 43 dimensies en 86 facetten. Het was echter niet zomaar een voorbeeld; de figuur werd namelijk niet direct gevormd, maar afgeleid vanuit een veel eenvoudiger figuur met ‘slechts’ vijf dimensies.
Ingewikkeld voorbeeld
Er kan bewezen kan worden dat het voorbeeld inderdaad niet aan het Hirschvermoeden voldoet. Maar vreemd genoeg zijn bepaalde dingen van het voorbeeld die heel simpel lijken niet duidelijk. Zo is het onbekend hoeveel punten de figuur heeft. “Omdat de uitbreiding van vijf naar 43 dimensies een ingewikkeld proces is, met 38 stappen, is het niet goed mogelijk om te zeggen hoeveel punten je precies hebt.”
Santos hield echter niet op met tegenvoorbeelden vinden; later vond hij een tweede voorbeeld, dat simpeler was; 20 dimensies, 40 facetten. In dit voorbeeld is bovendien het aantal punten precies te berekenen: dat komt uit op 36425.
Geen computers nodig
Wat interessant is, is dat het tegenvoorbeeld in theorie ook al ten tijde van Klee en Hirsch ontdekt had kunnen worden. Er worden geen geavanceerde computertechnieken of algoritmes gebruikt (zoals bij het bewijs van de laatste stelling van Fermat bijvoorbeeld wel gebeurt). Computers zijn natuurlijk wel gebruikt om ideeën op te doen, om modellen te testen, enzovoort, maar het basisidee maakt puur gebruik van ‘oude’ wiskunde. “Maar natuurlijk had ik dit voorbeeld niet kunnen bedenken zonder het eerdere werk van vele andere wiskundigen, waaronder Klee. Hij is een grote inspiratie voor mij geweest.
De toekomst
Hoewel het Hirschvermoeden nu officieel ontkracht is, houdt Santos’ insteresse in het vermoeden niet op. Op Polymath, waar eerder succesvolle resultaten behaald zijn door met veel mensen aan een probleem te werken, loopt nu een project om een alternatief Hirsch-vermoeden te vinden. Door de maximale diameter aan te passen, kan er misschien een nieuwe stelling worden bedacht die wel klopt. “De nieuwe grens waar we aan zitten te denken is (n-d)d, maar er moet veel onderzoek worden gedaan voor we daar meer over kunnen zeggen.”
Er is dus nog genoeg te doen in de toekomst. Wat Santos ook nog gaat ontdekken, hij zal het zeker niet alleen doen. Het ontkrachten van het Hirschvermoeden kostte tijd en moeite van heel veel mensen. En zo is het met alle wiskundige stellingen, ideeen, bewijzen en vermoedens. Het romatische idee van de eenzame wiskundige in zijn torenkamertje is mooi, maar klopt zeker in deze tijd niet meer. En voordat een stelling met een mooi bewijs wordt uitgelegd in de collegezalen, gaan er vele gefaalde, lelijke of onjuiste pogingen aan vooraf. Dat is hoe het er in de wiskunde echt aan toegaat.