N.B. Het kan zijn dat elementen ontbreken aan deze printversie.
Wiskunde Na geruchtmakende berichten over een ogenschijnlijk eenvoudig wiskundig vraagstuk hebben veel wiskundigen zich er met succes op gestort.
:format(webp)/s3/static.nrc.nl/bvhw/files/2023/01/data95520433-e1ea77.png)
Illustratie Roland Blokhuizen
Soms wordt de opinie in de wetenschap voor even bepaald door berichten op blogs en sociale media. Dat gebeurde half november, toen een bekende wiskundige uit Cambridge een tweet postte over wat hij „een van de bekendste open problemen in de combinatoriek” noemde. De aanleiding voor zijn tweet was een nieuw artikel over dat probleem op de preprintserver arXiv. Een andere wiskundige, uit Jeruzalem, schreef erover op zijn door wiskundigen goed gelezen weblog.
Velen schoven hun bezigheden aan de kant en begonnen die preprint te bestuderen. De auteur was Justin Gilmer, een medewerker van Google die onderzoek doet op het gebied van machine learning. Meteen was duidelijk: als de inhoud correct is, gaat het om een grensverleggend resultaat, al ging het ‘slechts’ om een deeloplossing van het betreffende probleem. Vier dagen na het verschijnen van Gilmers artikel postten drie groepen wetenschappers nieuwe preprints met scherpere resultaten.
Het probleem in kwestie is afkomstig van Péter Frankl en dateert uit 1979. De originele formulering klinkt abstract, maar er is een parallel met kleurige knikkers in zakjes. Als een aantal zakjes onder een drietal voorwaarden (zie inzet) met gekleurde knikkers worden gevuld, is er altijd een kleur die in minstens 50 procent van de zakjes voorkomt, ongeacht het aantal aanwezige kleuren. Dat is het vermoeden van Frankl. Of het waar is, is nog altijd onduidelijk.
Straatartiest in Japan
Gilmer heeft bewezen dat er altijd een kleur moet zijn die in minstens 1 procent van de zakjes voorkomt. Diverse andere wetenschappers wisten dit vervolgens op te krikken tot 38,2 procent. Daarmee vergeleken klinkt het resultaat van Gilmer bescheiden. „Toch is het Gilmer die de credits voor de échte doorbraak verdient”, reageert de inmiddels 69-jarige Frankl per e-mail. Voordien was immers niet eens bekend of Frankl’s uitspraak überhaupt waar is voor een of ander vast percentage.
De van oorsprong Hongaarse Frankl woont al decennia in Japan, waar hij in de eerste jaren zijn centen als straatartiest bij elkaar jongleerde, omdat het hem als buitenlander niet lukte een betrekking aan een universiteit te krijgen. Het naar hem vernoemde probleem bedacht hij enkele jaren vóór hij in 1982 voor het eerst naar Japan ging. Op de vraag hoe hij erop kwam, antwoordt hij: „Ik werkte aan een probleem over eindige verzamelingen en ik realiseerde me dat als deze bewering zou kloppen, ik diverse andere resultaten kon verbeteren.”
Het probleem deed rond 1980 via via de ronde. Al gauw had een groot deel van de wiskundige gemeenschap erover gehoord, via de telefoon of op conferenties. Maar niemand wist de oorsprong. Dat Frankl een jonge onbekende wiskundige was, hielp ook niet. „Jamie Simpson vertelde over een probleem, die het hoorde van Franz Salzborn, die het ergens in Nederland had opgevangen”, zei iemand. Een ander: „Ik ken het als Grinsteads vermoeden, maar Charles Grinstead, de enige Grinstead van wie ik ooit heb gehoord, ontkent de oorsprong ervan te zijn.” Sommigen schreven het probleem toe aan de ‘folklore’, de schatkist van goed verspreide wiskundeproblemen zonder duidelijke oorsprong. „Dat doet echt pijn”, zegt Frankl.
:strip_icc()/s3/static.nrc.nl/bvhw/files/2023/01/010.jpg%7C//images.nrc.nl/ebBMRSMfWqYW06sW-Xy9X7aREws=/1920x/smart/filters:no_upscale():strip_icc()/s3/static.nrc.nl/bvhw/files/2023/01/010.jpg)
Foto uit privéarchief
Ik wou gewoon begrijpen waarom het zo moeilijk is
Justin Gilmer wiskundige
In oktober was Gilmer op vakantie in New York. Daar bezocht hij de campus waar hij zes jaar geleden was gepromoveerd. Zijn gedachten dwaalden af naar wat destijds zijn favoriete probleem was: dat van Frankl. „Mensen hebben er zo lang over nagedacht, zo veel doodlopende wegen bewandeld”, mailt Gilmer. „Ik had nooit verwacht er iets aan te kunnen bijdragen, maar ik wou gewoon begrijpen waarom het zo moeilijk is.”
Gilmer vroeg aan een paar collega’s van destijds of ze de ‘entropiebenadering’ ooit hadden overwogen. „Toen ze antwoordden dat dat niet het geval was maar dit wel een interessante invalshoek vonden, werd ik enthousiast. Ik kreeg het idee dat dat zou kunnen werken”, zegt Gilmer.
‘Entropie’ is een wiskundige maat voor hoe ‘willekeurig’ iets is. Dit concept wordt gebruikt in de informatietheorie, het deelgebied van de wiskunde dat zich bezighoudt met het efficiënt en betrouwbaar overdragen en opslaan van informatie. Het kent veel toepassingen, onder meer bij het genereren van wachtwoorden – hoe hoger de entropie, hoe veiliger.
Opschroeven van percentage
Gilmers intuïtie dat ‘entropie’ toepasbaar zou kunnen zijn op het probleem van Frankl, bleek te kloppen. Zodoende kon hij bewijzen dat er altijd een kleur is die in minstens 1 procent van de zakjes voorkomt. In korte tijd lukte het meerdere wiskundigen de methode van Gilmer zodanig aan te passen, dat dat kon worden opgeschroefd tot 38,2 procent. De meest recente verbetering komt van de Belg Stijn Cambie, die verbonden is aan het onderzoeksinstituut IBS in Zuid-Korea. Cambie kon het resultaat met nog eens een kleine fractie verbeteren, blijkt uit zijn preprint van 26 december.
Kan die 38,2 procent omhoog worden gebracht tot 50 procent? Dan zou het probleem van Frankl zijn opgelost. Zelf zegt Frankl erover: „De toekomst voorspellen is altijd moeilijk. Mijn gevoel is dat óf het volledige vermoeden binnen zes maanden zal worden bewezen, óf de huidige methoden zijn onvoldoende. In dat geval moeten we waarschijnlijk nog een paar jaar wachten.”
Gilmer beaamt dat. Was hij aanvankelijk nog „voorzichtig optimistisch” dat de volledige oplossing binnen handbereik was, nu vindt hij het „nogal verrassend” dat Cambies waarde een hardnekkige grens lijkt te zijn voor de entropie-aanpak.
