DE NOMADISCHE WISKUNDE VAN PAUL ERDÖS; Bewijzen met je blote handen

Op 20 september overleed de Hongaars-Amerikaanse wiskundige Paul Erdös, 83 jaar oud. Hij was even briljant als excentriek en stelde zijn zwervende bestaan volledig in dienst van de getallen.

WISKUNDE IS DE studie van symmetrie en regelmaat. Alleen wie in de volle maan of in een pottenbakkerswiel het abstracte idee van een cirkel herkent, kan een uitspraak doen over alle ronde dingen. De onlangs overleden wiskundige Paul Erdös wist regelmaat te vinden op plaatsen waar die er per definitie niet lijkt te zijn: in de willekeur.

Paul Erdös was een legendarisch wiskundige, met een unieke stijl. Zijn leven ontsnapte aan de normale orde der dingen. Als een wiskundige nomade trok hij van universiteit naar universiteit. Zelden bleef hij ergens langer dan een paar dagen, al zijn bezittingen pasten in een koffer. “Bezit is hinderlijk”, verklaarde hij laconiek.

Onder wiskundigen was Paul Erdös een beroemdheid. Iedereen kende wel een Erdös-story, een verhaal over zijn eigenaardigheden. Als hij op bezoek kwam stonden studenten en professoren in de rij om hem te laten meedenken over hun onderzoek. Menigeen heeft zijn krachten beproefd op één van de intrigerende problemen die hij opwierp. De wiskunde van Erdös is net zo buitengewoon als zijn levenswijze. Veel grote wiskundigen zijn kasteelheren en bouwen op hun vakgebied theorieën waar zij heer en meester zijn. Overal waar hij kwam hielp Erdös mee: hij werkte samen met meer dan 450 wiskundigen uit vijfentwintig landen.

LOTTO-FORMULIER

Zijn invloed is vooral sterk in de combinatoriek, die door zijn bijdragen totaal is vernieuwd. De combinatoriek is de wiskunde van het tellen en combineren. Hoeveel manieren zijn er om een lotto-formulier in te vullen? Hoe werkt Rubik's cube? Dat soort vragen komt uit de combinatoriek. De aantallen lopen daarbij al gauw uit de hand. Drie boeken naast elkaar op een schap zetten kan op 6 manieren, maar voor tien boeken loopt dit aantal op tot meer dan 3,5 miljoen. In zo'n overdaad is het moeilijk nog structuur te herkennen. Erdös ontwikkelde een nieuwe manier van tellen gebaseerd op de kansberekening, en wist daarmee orde in de willekeur te ontdekken. Zo bewees hij bijvoorbeeld: van n boeken die willekeurig op een schap zijn gezet staan er altijd minstens wortel n op alfabetische volgorde (van links of van rechts gezien). Met andere woorden: in elke warboel is structuur te vinden.

Erdös' studie van de random graaf is nog zo'n voorbeeld. Een graaf is een netwerk van knooppunten en verbindingslijnen. Men kan denken aan een aantal kralen (de knooppunten) verbonden met touwtjes. Ieder paar kralen is op zijn hoogst verbonden met één touwtje. Een random graaf is een netwerk waarvan alleen het aantal knooppunten en verbindingslijnen bekend is. Dat is niet veel informatie. Met zes kralen en zes touwtjes kan ik verschillende grafen maken: een ketting van zes kralen bijvoorbeeld, of twee kettingen van drie kralen, of twee losse kralen en een cluster van vier waarvan ieder paar verbonden is. Ik weet dus niet zeker hoe een random graaf eruit ziet. Toch kan ik wel iets zeggen. In een random graaf met zes kralen en zes touwtjes kunnen er niet meer dan twee losse kralen zijn, bijvoorbeeld (omdat alle touwtjes gebruikt moeten worden), en er zijn niet genoeg touwtjes om een cluster van vijf te maken. Op zo'n manier lukte het Erdös en zijn collega Alfred Renyi in 1960 te bewijzen dat random grafen allerlei onvermoede eigenschappen hebben.

De bioloog Stuart Kaufman gaf onlangs aan deze vindingen een nieuwe dimensie. Kaufman ziet in de kralen moleculen, en in de verbindingstouwtjes chemische reacties. Hij gebruikt een stelling van Erdös en Re'nyi om te verklaren hoe uit de wanorde van de jonge aarde de structuur van het leven kan zijn ontstaan.

De studie van random grafen is dankzij Erdös uitgegroeid tot een nieuwe stroming in de wiskunde. Als een eigenwijze kleuter bleef Erdös na ieder antwoord nieuwe vragen stellen. Zijn vraagstukken leken op het eerste gezicht willekeurig, maar na maanden of jaren van zoeken naar oplossingen werd vaak ineens de onderliggende structuur zichtbaar. Ernst Strauss noemde hem dan ook 'the prince of problem solvers and the absolute monarch of problemposers'.

Voor zijn favoriete problemen loofde Erdös geldprijzen uit, variërend van 10 tot 3.000 dollar. Vaak waren prijswinnaars zo trots dat ze hun cheque liever inlijstten dan dat ze hem verzilverden. Prof.dr. J.H. van Lint van de Technische Universiteit Eindhoven hoefde die keuze niet te maken. Hij vertelt: “Ik heb ooit $ 100,- gewonnen en dat stuurde hij als opdracht aan een bank, dus ik heb de opdracht en het geld.”

'Schoonheid is waarheid', zeiden de Romantici. Het is geen toeval dat de vraagstukken van Erdös vaak beschreven worden als 'mooi' of 'elegant'. Gevoel voor schoonheid is voor een wiskundige geen aardige bijkomstigheid, het is het kompas waarmee hij of zij onbekend terrein verkent. Een fraai probleem leidt tot nieuwe wiskundige ontdekkingen, een mooi bewijs laat glashelder zien waarom het bewezene waar is.

HET BOEK

Erdös sprak over de esthetiek van de wiskunde als 'Het Boek', een transcendent werk, ontoegankelijk voor stervelingen, met daarin alle wiskundige stellingen en hun elegantste bewijs. Hij twijfelde aan het bestaan van God, maar nooit aan het bestaan van Het Boek. De elegantie van zijn wiskundig werk doet vermoeden dat hijzelf vaak even in Het Boek heeft mogen kijken.

Ik vroeg drie Nederlandse wiskundigen naar het mooiste resultaat van Erdös. Van Lint noemt het eerste grote wapenfeit van Erdös, een eenvoudig bewijs van de priemgetalstelling. (Een priemgetal is een getal dat alleen deelbaar is door zichzelf en door 1). Deze stelling beschrijft de kans dat een willekeurig getal een priemgetal is. Het oorspronkelijke bewijs gebruikte zwaar geschut uit de complexe functietheorie; alsof je met een kanon op een mug schiet. De heersende mathematische opinie was dat het niet zonder kon, maar Erdös bleef geloven in een bewijs uit Het Boek. Samen met Atle Selberg vond hij in 1948 een 'blote-handen-bewijs' dat alleen elementaire feiten over getallen gebruikt.

Prof.dr. A. Schrijver van het Centrum voor Wiskunde en Informatica in Amsterdam noemt de Erdös-Ko-Rado stelling als zijn favoriet. Deze stelling vertelt hoeveel verschillende verzamelingen van k getallen tussen 1 en n (n is een willekeurig getal) je maximaal kunt kiezen zodat ieder paar verzamelingen elkaar snijdt. Het aardige is dat je dit resultaat op verschillende manieren kunt bekijken. Bij iedere interpretatie hoort een ander bewijs, en voor ieder bewijs is nieuw wiskundig gereedschap ontwikkeld.

Het resultaat dat Prof.dr. R. Tijdeman van de Rijksuniversiteit Leiden erg fraai vindt heeft te maken met random grafen. Neem 2 kralen waarvan ieder paar verbonden is met een touwtje. Erdös bewees dat je alle touwtjes rood of groen kunt kleuren zodat geen enkel groepje van 2n kralen onderling met maar één kleur verbonden is. Het bewijs is een kwestie van zorgvuldig tellen; tot nu toe heeft niemand zulke kleuringen ook echt kunnen laten zien. Het vergde de fenomenale intuïtie van Paul Erdös zulke wiskundige structuren te vinden zonder te weten hoe ze er uitzien.