Wiskundige uit Delft Dion Gijswijt lost vraagstuk uit de combinatoriek op

Twee pagina’s berekeningen. Meer had de Delftse wiskundige Dion Gijswijt niet nodig voor een doorbraak in een decennia oud probleem. Het laat zich illustreren door een vraag over het kaartspel Set: hoeveel van de 81 kaarten kan je maximaal trekken zonder dat er een trio bij zit dat volgens de regels van het spel een Set vormt? Voor kaartspelen met veel kaarten blijkt dit maximum veel lager te liggen dan men tot nu toe dacht. Maar wiskundigen staan vooral paf van hoe simpel het bewijs is.

10 juni 2016

Je hebt een la met acht witte, zeven zwarte en vijf bruine sokken. Hoeveel sokken moet je hoogstens, zonder te kijken, uit de la halen, wil je een paar sokken van dezelfde kleur aan kunnen trekken? Dit is een heel simpel voorbeeld van ‘extremale combinatoriek’: je hebt een verzameling objecten met zekere eigenschappen, en daaruit haal je een deelverzameling die aan een of andere eis moet voldoen. Hoe groot is die deelverzameling hoogstens?

Bovengrenzen bepalen

Zelfs voor vrij kleine verzamelingen blijkt het verrassend lastig om zulke bovengrenzen te bepalen. Het kaartspel Set heeft 81 unieke kaarten, waaruit je met bepaalde spelregels (zie onderstaande fotobijschriften) drietallen kunt halen die een geldige Set vormen. De cap set voor dit spel heeft 20 kaarten: je kunt hoogstens 20 kaarten uit het spel halen waarin géén Set zit.

Het bewijs hiervoor vergt flink wat lastige wiskunde. Gewoon uitproberen loopt stuk op het enorme aantal mogelijkheden: je kunt op 286.360.607.519.186.119.920 manieren 20 kaarten uit een set van 81 trekken.

De spelregels van Set komen overeen met een klassiek probleem in de combinatoriek, dat vraagt naar de grootte van de cap set als elke kaart n eigenschappen heeft, (zodat het complete pak 3ⁿ kaarten heeft). Als n=3 komt dit probleem overeen met het spel Set waarbij je, bijvoorbeeld, alleen de 27 blauwe kaarten gebruikt. De cap set heeft dan 9 kaarten.

Als je Set uit zou breiden met een vijfde eigenschap, bijvoorbeeld achtergrondkleur wit/grijs/zwart, zodat je 3⁵=243 unieke kaarten hebt, is de cap set 45 kaarten groot. Pas onlangs is bewezen, dat voor n=6 de cap set 112 kaarten heeft. En voor n=7 en alle grotere n? Niemand die het weet.

Het volledige spel kaarten van Set. De kaarten hebben vier eigenschappen, in drie varianten: vorm (ovaal/driehoek/rechthoek), kleur (blauw/groen/rood), aantal (1/2/3) en vulling (open, gearceerd, vol). Daarom zijn er 3⁴=81 verschillende kaarten.
Een Set is een drietal kaarten, waarbij voor elk van de vier eigenschappen geldt, dat de drie kaarten óf allemaal verschillend óf allemaal hetzelfde zijn. Zie de voorbeelden hieronder.
AJ

Asymptotisch

Dion Gijswijt en, onafhankelijk van hem, Jordan Ellenberg bewezen iets veel algemeners: zij vonden een formule voor de bovengrens van het aantal kaarten in de cap set voor alle n. De formule is ‘asymptotisch’, wat betekent dat hij steeds beter werkt naarmate n groter wordt. Dus hoewel de exacte waardes voor elke n groter dan 6 nog steeds onbekend zijn, perkt hun formule de mogelijke waarde voor alle n drastisch in.

Overigens is het kaartspel Set pas bedacht toen dit probleem al een klassieker was in de extremale combinatoriek. Gijswijt: “Set is een mooie manier om dit probleem aanschouwelijk te maken.” Het zou zelfs kunnen, dat deze formule de theoretisch best mogelijke is om het asymptotische gedrag van de cap set te beschrijven. Maar Gijswijt zelf is daar niet van overtuigd.

Een legitieme Set. De drie kaarten zijn wat betreft alle vier hun eigenschappen verschillend. Dus alle drie de kleuren komen voor, alle drie de vormen, alle drie de aantallen en alle drie de vullingen.
aj

Voor dit probleem was sinds 1995 al een veel zwakkere bovengrens bekend (zie het kader), die met veel geavanceerde wiskunde was afgeleid. De nieuwe bovengrens van Gijswijt en Ellenberg, daarentegen, berust op relatief simpele wiskunde, de zogeheten polynomiale methode. Terence Tao, winnaar van de Fields medaille en een van de beroemdste wiskundigen ter wereld, is er zo van onder de indruk, dat hij de techniek in Quantamagazine ‘magisch’ noemt.

Ook dit is een Set. Qua kleur, vorm en vulling zijn de kaarten alle drie verschillend, qua aantal alle drie gelijk.
aj

Leesclubje

Hoe kwam dit probleem op Gijswijts pad, en heeft hij er lang aan gewerkt? Gijswijt: “Nee hoor, het begon met een leesclubje op het Centrum voor Wiskunde & Informatica, waar ik af en toe met collega’s bij elkaar kom om samen nieuwe wiskundige methoden te bestuderen. Toevallig had iemand een artikel meegebracht van drie andere wiskundigen, Ernie Croot, Vsevolod Lev en Peter Pach, die begin mei een probleem hadden opgelost dat op het Set-probleem lijkt. Hun methode was niet heel technisch, maar leek heel specifiek voor dat probleem.”

Dit is geen Set. Het gaat mis bij de eigenschap vulling: de kaarten zijn wat dit betreft noch alle drie verschillend, noch alle drie hetzelfde.
aj

Volkomen onverwacht slaagde Gijswijt er toch in om de methode toe te passen op het klassieke Set-probleem, en het was niet eens bijzonder moeilijk: “Dit is een probleem waar ik al sinds m’n studententijd af en toe over nadenk, zonder veel succes. Nu vielen plots alle stukjes op z’n plek en was het bewijs in een paar dagen rond.”

Toen hij zijn resultaat half mei besprak met de leesclub, bleek de Amerikaan Jordan Ellenberg net een paar dagen eerder hetzelfde resultaat al op een blog gezet te hebben. Hij mailde Ellenberg hierover, en ze besloten er gezamenlijk een wetenschappelijk artikel over te publiceren. Gijswijt: “Dat was heel vriendelijk. Hij had ook kunnen zeggen: ‘Ik was eerder, en jij hebt geen enkel bewijs dat je dit onafhankelijk van mij hebt ontdekt’”.

Zwakke en sterke bovengrenzen

De bovengrens van Gijswijt en Ellenberg stelt dat de cap set hoogstens (2,756/3)ⁿ maal het totaal aantal kaarten bevat.
Een veel zwakkere bovengrens voor de cap set was al sinds 1995 bewezen: 1/n maal het totaal aantal kaarten. Voor kleine n klopt dat heel aardig. Voor n=4: 3⁴=81 unieke kaarten met een cap set van 20 kaarten, en 1/4 maal 81 is ongeveer 20. Voor n=6: 3⁶ = 729 unieke kaarten, met een cap set van 112 kaarten, terwijl 1/6 maal 729 ~ 121.
Maar voor grote n geeft 1/n een veel te hoge bovengrens. Neem bijvoorbeeld n=100. Dan zou de cap set 1/100 van het totaal aantal kaarten bevatten. De formule van Gijswijt en Ellenberg, (2,756/3)ⁿ, levert voor n=100 als bovengrens op, dat een cap set hoogstens 1/5000-ste van het totaal aantal kaarten omvat.

De vorige ‘doorbraak’ op dit gebied was in 2012. Toen werd slechts bewezen dat de bovengrens ietsje lager lag dan bij 1/n, namelijk bij 1/n^(1+e), met e een piepklein getal waarvan de waarde niet precies bekend was. Dus voor n=100 zou de bovengrens dan niet bij 1/100, maar bij 1/(100^1,01) kunnen liggen, ofwel 1/105.
Het bewijs hiervoor was lang, moeilijk en zeer technisch. Gijswijt: “Veel wiskundigen dachten toen dat dit de beste bovengrens was die je menselijkerwijs kon vinden.” De bovengrens van Gijswijt en Ellerberg is hierop een enorme verbetering, en komt voor vakgenoten als een donderslag bij heldere hemel.

Rechte lijnen in een puntenwolk

Hoewel de polynomiale methode voor experts relatief eenvoudig is, is deze voor leken toch een brug te ver. Gijswijt weet ook geen simpel voorbeeld om het uit te leggen: “Het is een samenraapsel van allerlei technieken.”

Heel algemeen gesteld, pakken wiskundigen Set-achtige problemen aan door de n eigenschappen van een kaart voor te stellen als een punt in een n-dimensionale ruimte. Een compleet spel bestaat dan uit een puntenwolk van 3ⁿ punten in die ruimte, en als drie van die punten op een rechte lijn liggen vormt dit een Set.

Het probleem is dan, te bepalen hoeveel punten je maximaal in die puntenwolk kunt aanwijzen, waar geen enkele rechte lijn doorheen gaat. De grote verrassing was, dat polynomen (een heel algemeen type wiskundige vergelijkingen) in verband kunnen worden gebracht met zo’n puntenwolk, en dat de eigenschappen van deze polynomen nuttige dingen zeggen over de structuur van de puntenwolk.

Volgens Gijswijt zijn de nuttige toepassingen van het Set-probleem heel beperkt (voor de kenners: hun resultaat sluit bepaalde, tot nu toe kansrijk geachte methoden om matrix-vermenigvuldiging sneller te maken uit). Maar zijn vakgebied, extremale combinatoriek, heeft wel degelijk belangrijke toepassingen, bijvoorbeeld voor het ontwerpen van fout-corrigerende codes.

Digitale informatie is te coderen op zo’n manier dat allerlei fouten – die ontstaan op een slechte internetverbinding – nog te herstellen zijn door de ontvanger. Dit gebeurt nu al, maar als je een betere methode ontdekt, betekent dit dat je over dezelfde verbinding nog meer data kunt versturen zonder kwaliteitsverlies.

Wiskunde per blog

De razendsnelle ontwikkelingen rond dit probleem zijn een typisch voorbeeld van ‘wiskunde per blog’. Ook wereldberoemde wiskundigen als Terence Tao en Timothy Gowers bloggen dagelijks over hun onderzoek, en delen hun voorlopige resultaten met iedereen die maar wil kijken. En wanneer iemand als Terence Tao ergens een beginnetje vindt, is er een vette kans dat dit belangrijke wiskunde zal blijken te zijn. Dus gaan andere wiskundebloggers daar ook mee aan de slag.

Gijswijt: “Ik vind het niet prettig. Als je één nacht niet kijkt, zijn er alweer allerlei nieuwe ontwikkelingen. Het begint dan ook op een race te lijken.” Maar wiskunde per blog heeft het amechtige ritme van facebook: “Na een tijdje zijn alle makkelijke dingen over een nieuw onderwerp wel gedaan, en dan dooft die activiteit snel weer uit.”

Nu dit resultaat binnen is, wordt het voor Gijswijt tijd om breder te kijken. De polynomiale methode is waarschijnlijk niet alleen op Set-achtige problemen toepasbaar: “Deze methode is heel nieuw. Het is heel interessant om te verkennen: wat kan je er nog meer mee?”

Reageer