Puzzels van een miljoen per stuk

Op 8 augustus 1900 liep de befaamde wiskundige David Hilbert naar het spreekgestoelte tijdens een congres in Parijs. Daar ontvouwde hij de wiskundige uitdagingen voor de twintigste eeuw, een lijst van 23 onopgeloste problemen. Sommige daarvan waren te algemeen gesteld om bij de kop te pakken, andere bleken vrij simpel, maar de rest hield knappe koppen de rest van de eeuw bezig. Een van de laatste die werd opgelost was de stelling van Fermat, nummer tien op Hilberts lijst. Andrew Wiles vond de oplossing in 1994.

Wiles is een van de samenstellers van de in mei 2000 opgestelde lijst van zeven problemen waarop de Amerikaanse miljonair London Clay een prijs van een miljoen dollar heeft gezet. Die problemen laten zich, zelfs in essentie, moeilijk uitleggen. Daarom is het goed dat Keith Devlin ‘The millennium problems’ heeft geschreven, waarin hij de basics netjes op een rijtje zet. Niemand met enige wiskundige aanleg zal immers een miljoen dollar voorbij laten gaan zonder tenminste eventjes gekeken te hebben of hij iets met deze zeven kan.

De eerste van de zeven problemen is de laatste onopgeloste van Hilberts lijstje en inmiddels 140 jaar oud: de Riemann-hypothese. Net als Fermat zette Bernhard Riemann zijn formule op papier zonder het bewijs erbij, maar wel met de mededeling dat hij het had. Toen ging hij dood. Sindsdien hebben wiskundigen zich wild gezocht naar dat bewijs. De formule zelf is behoorlijk ingewikkeld en beweert dat er een bepaald patroon zit in de verdeling van priemgetallen onder de natuurlijke getallen. Computers hebben de juistheid vastgesteld voor de eerste tigtiljoenste getallen vanaf nul, maar dat is voor wiskundigen natuurlijk niet genoeg.

Naast pure wiskundigen zijn ook cryptografen uiterst geïnteresseerd in de Riemann-hypothese. Priemgetallen spelen namelijk een cruciale rol bij het genereren van cryptografische sleutels. Een bewijs van de hypothese zou wel eens gepaard kunnen gaan met diepe cryptografische inzichten, met twee potentiële gevolgen: simpel kraken van bestaande versleutelingen en opstellen van verbeterde algoritmen. Wie het bewijs niet bij London Clay inlevert, maar bij de Amerikaanse afluisterdienst NSA, zou wel eens veel meer kunnen opstrijken dan een miljoen dollar, maar dan als zwijggeld.

Devlin gaat op die laatste mogelijkheid niet in. Hij houdt het bij de wiskunde en dat doet hij goed. Hij behandelt net genoeg wiskunde om niet oppervlakkig te zijn, maar ook weer niet zoveel dat het ongezellig wordt. Het hoofdstuk over Riemann, bijvoorbeeld, gaat grotendeels in op de historische achtergrond van studie naar priemgetallen. Dat is niet alleen franje, maar ook noodzakelijk om te begrijpen hoe Riemann tot zijn hypothese kwam en wat die úberhaupt betekent.

De andere zes problemen spreken minder tot de verbeelding, hoewel twee ervan zeker relevant zijn voor ingenieurs. Uit de stromingsleer komen de Navier Stokes-vergelijkingen, die onderzoekers van het Burgerscentrum vermoedelijk dagelijks onder handen hebben. Je kunt ze namelijk numeriek benaderen en dat is belangrijk voor het ontwerp van bijvoorbeeld vliegtuigvleugels en scheepskielen. Maar echte oplossingen van deze vergelijkingen zijn niet bekend.

Tot de nachtmerries van informaticastudenten behoort het P-NP-probleem, omdat het aan de orde komt in een erkend struikelvak. P-NP gaat over het verband tussen de complexiteit van een probleem en de benodigde rekentijd om het op te lossen. Als de rekentijd namelijk exponentieel groeit bij iedere kleine groei in complexiteit, lopen berekeningen snel uit de klauwen. Daarom zou je bij complexe problemen graag van tevoren iets willen weten over de rekentijd. Volgens Devlin is dit het probleem dat de minste mathematische voorkennis vereist, dus het meest geëigend voor liefhebbers die zich aangetrokken voelen tot die miljoen dollar.

Voor degenen die na het lezen van ‘The millennium problems’ serieus in de verleiding komen om zich aan een van de problemen te wagen, mag het levensverhaal van Andrew Wiles tot inspiratie dienen. Betaald door Cambridge University sloot hij zichzelf jarenlang op in zijn studeerkamer, met allerlei geheimzinnige smoezen om anderen niet te laten achterhalen waar hij op broedde, om uiteindelijk met de oplossing van Fermats laatste stelling te komen. Die hem eeuwige roem bracht.

Keith Devlin, ‘The millennium problems; the seven greatest unsolved mathematical puzzles of our time’. Granta, 2004, pp. 237, 21,91 euro (bij Amazon).

Een van de nachtmerries van informaticastudenten

Op 8 augustus 1900 liep de befaamde wiskundige David Hilbert naar het spreekgestoelte tijdens een congres in Parijs. Daar ontvouwde hij de wiskundige uitdagingen voor de twintigste eeuw, een lijst van 23 onopgeloste problemen. Sommige daarvan waren te algemeen gesteld om bij de kop te pakken, andere bleken vrij simpel, maar de rest hield knappe koppen de rest van de eeuw bezig. Een van de laatste die werd opgelost was de stelling van Fermat, nummer tien op Hilberts lijst. Andrew Wiles vond de oplossing in 1994.

Wiles is een van de samenstellers van de in mei 2000 opgestelde lijst van zeven problemen waarop de Amerikaanse miljonair London Clay een prijs van een miljoen dollar heeft gezet. Die problemen laten zich, zelfs in essentie, moeilijk uitleggen. Daarom is het goed dat Keith Devlin ‘The millennium problems’ heeft geschreven, waarin hij de basics netjes op een rijtje zet. Niemand met enige wiskundige aanleg zal immers een miljoen dollar voorbij laten gaan zonder tenminste eventjes gekeken te hebben of hij iets met deze zeven kan.

De eerste van de zeven problemen is de laatste onopgeloste van Hilberts lijstje en inmiddels 140 jaar oud: de Riemann-hypothese. Net als Fermat zette Bernhard Riemann zijn formule op papier zonder het bewijs erbij, maar wel met de mededeling dat hij het had. Toen ging hij dood. Sindsdien hebben wiskundigen zich wild gezocht naar dat bewijs. De formule zelf is behoorlijk ingewikkeld en beweert dat er een bepaald patroon zit in de verdeling van priemgetallen onder de natuurlijke getallen. Computers hebben de juistheid vastgesteld voor de eerste tigtiljoenste getallen vanaf nul, maar dat is voor wiskundigen natuurlijk niet genoeg.

Naast pure wiskundigen zijn ook cryptografen uiterst geïnteresseerd in de Riemann-hypothese. Priemgetallen spelen namelijk een cruciale rol bij het genereren van cryptografische sleutels. Een bewijs van de hypothese zou wel eens gepaard kunnen gaan met diepe cryptografische inzichten, met twee potentiële gevolgen: simpel kraken van bestaande versleutelingen en opstellen van verbeterde algoritmen. Wie het bewijs niet bij London Clay inlevert, maar bij de Amerikaanse afluisterdienst NSA, zou wel eens veel meer kunnen opstrijken dan een miljoen dollar, maar dan als zwijggeld.

Devlin gaat op die laatste mogelijkheid niet in. Hij houdt het bij de wiskunde en dat doet hij goed. Hij behandelt net genoeg wiskunde om niet oppervlakkig te zijn, maar ook weer niet zoveel dat het ongezellig wordt. Het hoofdstuk over Riemann, bijvoorbeeld, gaat grotendeels in op de historische achtergrond van studie naar priemgetallen. Dat is niet alleen franje, maar ook noodzakelijk om te begrijpen hoe Riemann tot zijn hypothese kwam en wat die úberhaupt betekent.

De andere zes problemen spreken minder tot de verbeelding, hoewel twee ervan zeker relevant zijn voor ingenieurs. Uit de stromingsleer komen de Navier Stokes-vergelijkingen, die onderzoekers van het Burgerscentrum vermoedelijk dagelijks onder handen hebben. Je kunt ze namelijk numeriek benaderen en dat is belangrijk voor het ontwerp van bijvoorbeeld vliegtuigvleugels en scheepskielen. Maar echte oplossingen van deze vergelijkingen zijn niet bekend.

Tot de nachtmerries van informaticastudenten behoort het P-NP-probleem, omdat het aan de orde komt in een erkend struikelvak. P-NP gaat over het verband tussen de complexiteit van een probleem en de benodigde rekentijd om het op te lossen. Als de rekentijd namelijk exponentieel groeit bij iedere kleine groei in complexiteit, lopen berekeningen snel uit de klauwen. Daarom zou je bij complexe problemen graag van tevoren iets willen weten over de rekentijd. Volgens Devlin is dit het probleem dat de minste mathematische voorkennis vereist, dus het meest geëigend voor liefhebbers die zich aangetrokken voelen tot die miljoen dollar.

Voor degenen die na het lezen van ‘The millennium problems’ serieus in de verleiding komen om zich aan een van de problemen te wagen, mag het levensverhaal van Andrew Wiles tot inspiratie dienen. Betaald door Cambridge University sloot hij zichzelf jarenlang op in zijn studeerkamer, met allerlei geheimzinnige smoezen om anderen niet te laten achterhalen waar hij op broedde, om uiteindelijk met de oplossing van Fermats laatste stelling te komen. Die hem eeuwige roem bracht.

Keith Devlin, ‘The millennium problems; the seven greatest unsolved mathematical puzzles of our time’. Granta, 2004, pp. 237, 21,91 euro (bij Amazon).

Een van de nachtmerries van informaticastudenten