Een precies antwoord is voor wiskundigen vaak te veel gevraagd

In een mooi gedachtenexperiment van de Hongaarse wiskundige Paul Erdös (1913-1996) landt een stel aliens op onze aarde, die ons vragen naar de waarde van het vijfde Ramseygetal. Kunnen we het antwoord niet binnen redelijke tijd geven, dan zullen ze onze planeet vernietigen. Volgens Erdös zouden we al onze wiskundigen bijeen moeten roepen, die alles op alles dienen te zetten om deze waarde te berekenen. Maar als de aliens niet het vijfde maar het zesde Ramseygetal willen horen, zouden we er alles aan moeten doen om de buitenaardse wezens te verwoesten.

Ramseygetallen, vernoemd naar Frank Ramsey (1903-1930), kwantificeren hoe groot iets moet zijn zodat bepaalde patronen onvermijdelijk ontstaan. Een gangbare omschrijving van het vijfde Ramseygetal, afgekort als R₅, is het kleinste aantal personen dat bij elkaar moet komen zodat er zeker een clubje is van vijf personen die elkaar allemaal wél, of juist allemaal níét kennen. Net zo is het zesde Ramseygetal R₆ de kleinste groepsgrootte met de eigenschap dat er hetzij zes zijn die elkaar allemaal kennen, hetzij zes die allen vreemden van elkaar zijn.

De aliens uitschakelen

Het bepalen van R₃ – hoeveel mensen moeten er op een feestje aanwezig zijn, zodat er beslist drie zijn die elkaar allen wel of allen niet kennen? – was in 1953 een opgave van een Amerikaanse wiskundewedstrijd voor bachelorstudenten. Het is een leuke puzzel om zelf na te gaan dat het antwoord zes is.

Grotere Ramseygetallen zijn extreem moeilijk te berekenen. Dat de studenten bij de wedstrijd niet naar R₄ werd gevraagd, zal ermee te maken hebben dat de opgavenbedenkers zélf geen idee hadden hoe ze dit moesten aanpakken – het was toentertijd een open probleem. Aangespoord door de wedstrijd stortten wiskundigen zich hierop. In 1955 kwam het verlossende antwoord: R₄ = 18. Dat betekent dat er minimaal 18 aanwezigen moeten zijn, opdat er altijd een groepje van vier is die elkaar allemaal wel of allemaal niet kennen.

Bij wiskunde denken veel mensen aan exacte antwoorden, al dan niet uitgedrukt in een bondige formule

Het probleem met dit type opgave is dat het aantal gevallen dat je moet bekijken, al snel heel erg groot wordt. Op dit moment weet niemand de precieze waarde van het vijfde Ramseygetal, laat staan het zesde of het zevende. Wellicht gaat het ooit lukken om R₅ exact uit te rekenen, maar R₆ zal vrijwel zeker nooit bekend worden. De berekening is domweg onhaalbaar vanwege het gigantische aantal mogelijkheden dat moet worden nagelopen. Vandaar dat dit vooral niet geprobeerd moet worden in Erdös’ gedachtenexperiment – de enige manier om te overleven is door de aliens uit te schakelen.

Bij wiskunde denken veel mensen aan exacte antwoorden, al dan niet uitgedrukt in een bondige formule. Op middelbareschoolniveau klopt dat, maar voor vraagstukken op een hoger niveau geldt dat het eerder uitzondering dan regel is als iemand met een precieze formule voor de oplossing zou komen. Als het te moeilijk is om exacte antwoorden te verkrijgen, proberen wiskundigen onder- en bovengrenzen te vinden. Iemand die het vijfde Ramseygetal wil berekenen, kan bijvoorbeeld zeggen: „Ik weet niet hoe groot R₅ precies is, maar ik kan wel bewijzen dat het op zijn minst 43 is en op zijn hoogst 48.”

Twee biljoen gevallen

Voor moeilijke problemen is een dergelijke uitspraak al een hele prestatie, al helemaal als op voorhand niet duidelijk is dat zo’n grens bestáát. Neem de priemgetallen, die alleen deelbaar zijn door 1 en zichzelf. Wat is de kleinste waarde van k met de eigenschap dat er oneindig veel paren van priemgetallen bestaan die hoogstens k van elkaar verschillen? Al eeuwen wordt vermoed dat die waarde 2 is – dit is het zogenaamde priemtweelingvermoeden. In 2013 werd voor het eerst een bovengrens voor k bewezen: 70 miljoen. Weliswaar een groot getal, nog ver van 2 verwijderd, maar voordien was het niet eens zeker of er voor dit vraagstuk überhaupt zo’n bovengrens bestaat. Die 70 miljoen geldt als een van de grootste doorbraken uit de wiskunde van deze eeuw. Inmiddels is de grens verlaagd tot 246.

Terug naar de Ramseygetallen. Het vijfde Ramseygetal ligt – inderdaad – tussen 43 en 48. De ondergrens 43 werd in 1989 bewezen, de bovengrens 48 in 2017. Voor het bewijs van deze bovengrens moesten ongeveer twee biljoen gevallen met behulp van computerberekeningen worden gecontroleerd. Wiskundigen denken dat 43 de exacte waarde is van R₅, omdat er al veel pogingen zijn ondernomen om die ondergrens te verbeteren – zonder resultaat.

Los van deze concrete gevallen zijn wiskundigen ook geïnteresseerd in algemene vragen

Uiteraard geldt: hoe dichter de onder- en de bovengrens bij elkaar liggen, hoe beter. Voor R₆ is de best bekende ondergrens 102, de beste bovengrens is 161. Het zesde Ramseygetal ligt dus ergens tussen die twee getallen. Voor grotere Ramseygetallen neemt de afstand tussen beide grenzen snel toe. Het tiende Ramseygetal ligt tussen 798 en 23.556.

Los van deze concrete gevallen zijn wiskundigen ook geïnteresseerd in algemene vragen. Bijvoorbeeld: hoe verandert R_n bij toenemende grootte van n? Is er sprake van een lineaire toename (gelijkmatig)? Of exponentieel (heel snel)? Of logaritmisch (langzaam)?

Kleinere bovengrenzen

Bij dit onderzoek spelen onder- en bovengrenzen een cruciale rol. Al in 1935 wist Erdös, samen met zijn vriend en collega George Szekeres, te bewijzen dat het n-de Ramseygetal in elk geval niet groter is dan 4 tot de macht n. Twaalf jaar later toonde hij aan dat de wortel uit 2 tot de macht n een te lage inschatting is. Erdös’ ondergrens voor R_n is dus (√2)ⁿ, zijn bovengrens is 4ⁿ. Die bovengrens is verre van scherp: vul je voor n de waarde 5 in, krijg je 1024, terwijl we weten dat R₅ niet groter is dan 48. Maar toch: de formule geeft een bovengrens die waar is voor elke waarde van n. In de decennia na 1935 werden meermaals kleinere bovengrenzen gevonden, maar die verbeteringen waren relatief klein. Tot maart van dit jaar: toen zetten vier wiskundigen een artikel op de preprintserver arXiv waarin ze een ‘exponentiële verbetering’ van die bovengrens geven.

Niet alleen in de wiskunde, ook in de informatica is zulke kennis van belang

Marcelo Campos, Simon Griffiths, Robert Morris en Julian Sahasrabudhe hebben aangetoond dat R_n niet groter is dan 3,993ⁿ. Dat klinkt niet als een spectaculair resultaat, omdat 3,993 nauwelijks kleiner is dan 4. Als je R_10.000 wilt weten, geeft de bovengrens van Erdös een getal van 6.021 cijfers. De bovengrens van Campos en zijn collega’s telt acht cijfers minder.

Om in te zien hoe substantieel deze verbetering is, kijken wiskundigen naar de verhouding tussen beide bovengrenzen als n alsmaar groter wordt. Het quotiënt 3,993ⁿ gedeeld door 4ⁿ is gelijk aan 0,99825ⁿ, hetgeen dicht bij nul ligt voor grote waarden van n. De quotiënten tussen de bovengrenzen die al langer bekend waren en 4ⁿ hebben weliswaar ook limiet nul, maar die quotiënten gaan vrij langzaam naar nul. De nieuwe bovengrens is ‘exponentieel beter’ in de zin dat de genoemde verhouding 0,99825ⁿ ‘exponentieel snel’ naar nul convergeert. Dat betekent dat de bovengrens van Campos, Griffiths, Morris en Sahasrabudhe kwalitatief echt veel beter is – al is dat pas zichtbaar voor zeer grote waarden van n.

Efficiënte computerprogramma’s

Het vinden van goede onder- en bovengrenzen is essentieel om kwaliteitsgaranties te kunnen geven. Uitspraken als ‘de berekende oplossing wijkt maximaal 10 procent af van de beste’ zijn zonder grenzen onmogelijk.

Niet alleen in de wiskunde, ook in de informatica is zulke kennis van belang. Een programmeur die bezig is met een computerprogramma dat een bepaalde taak moet verrichten, zal een zo efficiënt mogelijk programma willen schrijven. Hij kan bij de wiskundige aankloppen om te vragen hoe vlug een computer op zijn vlugst klaar kan zijn. De wiskundige kan zo’n vraag zelden exact beantwoorden, maar hij kan wel aangeven hoeveel stappen het programma minimaal of maximaal moet uitvoeren. Heeft de programmeur een programma gemaakt waarvan het aantal stappen dicht bij dat minimum ligt, dan weet hij dat zijn programma nauwelijks aan efficiëntie kan winnen door nog slimmer te programmeren.