Erdős en de probabilistische methode: bestaan bewijzen met toeval
Paul Erdős had geen huis, geen baan in de gewone zin, en bijna geen bezittingen. Hij bracht zijn leven door met reizen tussen universiteiten met een koffer, verscheen op de stoep van een collega met de zin "mijn brein is open", en liet een stroom stellingen en onopgeloste problemen achter waar wiskundigen vandaag nog aan werken. Onder alles wat hij schiep steekt één idee uit, omdat het veranderde hoe bewijzen überhaupt worden gedaan. Het heet de probabilistische methode, en in de kern zit een zet die bijna op valsspelen lijkt: bewijzen dat iets bestaat door te weigeren het te bouwen.
De vraag: wanneer is orde onvermijdelijk?
Begin met een eenvoudig klinkende puzzel. Op een feest van zes mensen zijn twee willekeurige personen ofwel vrienden ofwel vreemden. Het blijkt dat je onder zes mensen altijd drie kunt vinden die allemaal wederzijdse vrienden zijn, of drie die allemaal wederzijdse vreemden zijn. Orde dwingt zichzelf af. De tak van de wiskunde die bestudeert wanneer dit moet gebeuren is de Ramsey-theorie, en die hangt een getal aan de vraag.
Ramseys stelling garandeert dat deze getallen bestaan, maar zegt niet hoe groot ze zijn. De natuurlijke vervolgvraag is: hoe groot kan een groep worden terwijl ze nog elk eentonig cluster van grootte k vermijdt? Dat beantwoorden betekent bewijzen dat zo'n slimme kleuring bestaat. En precies daar wordt het met de hand bouwen hopeloos, omdat het aantal mogelijke kleuringen astronomisch is.
De zet van Erdős: niet bouwen, tellen
Het inzicht van Erdős, in 1947, was om te stoppen met het ontwerpen van een goede kleuring en in plaats daarvan volledig willekeurig te kleuren, en de rekenkunde het werk te laten doen. Het argument is kort genoeg om volledig te volgen.
Kleur elke verbinding door een munt op te gooien
Neem n mensen en bekijk het complete netwerk waarin elk paar door een kant is verbonden. Kleur elke kant onafhankelijk willekeurig, rood of blauw, elk met kans een half. Geen slimheid, geen ontwerp. Gewoon een eerlijke munt voor elke enkele kant.
Meet hoe waarschijnlijk één groep eentonig is
Fixeer een willekeurige verzameling van k mensen. Onder hen zijn C(k,2) kanten, dat is verbindingen. Dat al die kanten één enkele kleur delen is onwaarschijnlijk: de kans is , want er zijn twee kleuren en elk van de C(k,2) muntworpen moet overeenstemmen. Noem dit kleine getal p.
Tel het verwachte aantal slechte groepen op
Er zijn C(n,k) verschillende groepen van k mensen om je zorgen over te maken. Door de lineariteit van verwachting is het verwachte aantal volledig eentonige groepen gewoon het aantal groepen keer de kans voor elk daarvan: . Deze ene uitdrukking vangt, gemiddeld, hoeveel éénkleurige clusters een willekeurige kleuring bevat.
Als het gemiddelde onder 1 ligt, moet een smetteloze kleuring bestaan
Kies nu n grofweg . Met die keuze komt het verwachte aantal hierboven uit onder 1. Maar een telling van echte eentonige groepen is een geheel getal, en als het gemiddelde over alle kleuringen onder 1 ligt, moet minstens één kleuring 0 scoren. Die kleuring heeft helemaal geen eentonige groep van grootte k. Daarom is R(k,k) groter dan n, wat ongeveer is.
Lees die laatste stap nog eens, want dat is de hele magie. We hebben nooit een goede kleuring gemaakt. We hebben er nooit één beschreven. We lieten zien dat de gemiddelde kleuring zo dicht bij smetteloos ligt dat een perfecte ergens in de stapel moet bestaan. Het bewijs geeft je zekerheid over een specifiek object terwijl het naar geen enkel object in het bijzonder wijst.
Waarom dit revolutionair was
Voor Erdős betekende bewijzen dat iets bestaat bijna altijd: het construeren, of op zijn minst een procedure beschrijven die dat zou doen. De probabilistische methode brak die verwachting. Ze stelde vast dat toeval zelf als bewijs kon dienen: als een willekeurige poging slaagt met welke kans boven nul dan ook, is succes mogelijk, punt.
Die niet-constructieve smaak zet het argument in dezelfde familie als sommige van de elegantste resultaten in de wiskunde. Cantors diagonaalargument bewijst ook het bestaan van iets, een getal dat op elke lijst ontbreekt, door pure logische kracht in plaats van expliciete constructie. Beide delen die stille, bijna ongemakkelijke kracht: de conclusie is waterdicht, ook al laat ze je het beloofde ding nooit zien. Het toeval hier rust op dezelfde fundamenten als in waarschijnlijkheid intuïtief begrijpen, waar het idee van een verwachte waarde, de motor van stap drie, vanaf nul wordt opgebouwd.
De problemen van Erdős en hun AI-moment
Erdős bewees niet alleen stellingen. Hij stelde problemen, honderden, vaak met kleine geldprijzen eraan, van een paar dollar voor een lastige oefening tot duizenden voor een vraag die hij werkelijk diep vond. Veel van die problemen zijn nog open, en ze zijn zorgvuldig gecatalogiseerd en bijgehouden op erdosproblems.com.
De zen ervan
De probabilistische methode is mooi om dezelfde reden als een goede goocheltruc: je ziet elke stap, je kunt de plek niet vinden waar je bedrogen werd, en toch voelt het resultaat onmogelijk. Er is geen goochelarij. De verwachte waarde ligt écht onder de één, en een geheel getal onder zijn eigen gemiddelde moet ergens naar nul duiken. De zekerheid is totaal, de constructie ontbreekt, en beide dingen zijn tegelijk waar.
Dat is de blijvende les die Erdős naliet. Bestaan en constructie zijn niet hetzelfde. Soms is de schoonste manier om te weten dat een perfect object ergens is, te bewijzen dat het gemiddelde object bijna perfect is, en het gat de rest te laten doen. Voor een ander resultaat waarin één regel ideeën samenbindt die los van elkaar lijken, biedt de identiteit van Euler de tegenovergestelde soort schoonheid: waar Erdős bestaan tovert uit tellen, spijkert Euler één exact en onvermijdelijk getal vast.
Veelgestelde vragen
- Wat is de probabilistische methode?
- Het is een manier om te bewijzen dat een object met een bepaalde eigenschap bestaat, zonder dat object direct te construeren. Je bouwt een willekeurige versie van het ding, laat zien dat de kans dat het de gewenste eigenschap heeft groter is dan nul, en concludeert dat minstens één zo'n object moet bestaan. Paul Erdős pionierde de techniek, en ze is nu een centraal gereedschap in combinatoriek en informatica.
- Wat bewees Erdős ermee?
- Zijn baanbrekende resultaat uit 1947 gaf een ondergrens op Ramsey-getallen: hij toonde dat het diagonale Ramsey-getal R(k,k) groter is dan 2^(k/2). In gewone taal: er bestaan manieren om de verbindingen in een groot netwerk met twee kleuren te kleuren zodat geen grote groep volledig in één kleur verbonden is. Hij bewees dat die kleuringen bestaan zonder er ooit één te laten zien, puur door te tellen.
- Hoe bewijs je dat iets bestaat zonder het te bouwen?
- Via gemiddelden. Als je een object willekeurig kiest en het verwachte aantal gebreken berekent, en dat verwachte aantal onder 1 uitkomt, dan moet minstens één object in de pool nul gebreken hebben. Een willekeurige keuze waarvan het gemiddelde aantal gebreken kleiner is dan één garandeert dat er ergens in de verzameling een perfect voorbeeld zit, ook al wijst het argument nooit naar welk exemplaar.
- Wat is een Ramsey-getal?
- Het Ramsey-getal R(k,k) is de kleinste groepsgrootte die orde afdwingt, hoe je de dingen ook rangschikt. Concreet is R(k,k) het kleinste aantal mensen zodat, hoe je elk paar ook splitst in vrienden of vreemden, je gegarandeerd een groep van k mensen vindt die allemaal wederzijdse vrienden of allemaal wederzijdse vreemden zijn. Ramseys stelling zegt dat deze getallen bestaan; de methode van Erdős laat zien dat ze heel snel groeien.
- Waarom is de probabilistische methode vandaag belangrijk?
- Ze maakte toeval tot een bewijstechniek, en dat idee loopt nu door combinatoriek, algoritmeontwerp, coderingstheorie en theoretische informatica. Veel resultaten over netwerken en algoritmen worden nog steeds bewezen door te laten zien dat een willekeurige constructie met positieve kans werkt. De methode is ook de reden dat een groot deel van Erdős' eigen problemen actieve onderzoeksdoelen blijft.
Oefen het zelf
Vond je het leuk om dit door te denken?
Math Zen maakt van dit soort inzicht dagelijkse oefening, met adaptieve opgaven bij 24 wiskundeonderwerpen.
