Man van ‘we leven ooit 1.000 jaar’ brengt oplossing oud pixelprobleem dichterbij

Een gedachtenexperiment: stel je een foto voor waarvan de pixels oneindig klein zijn. Dus hoever je ook inzoomt, de individuele pixels zijn nooit te herkennen, omdat ze oppervlakte nul hebben. Elke pixel – dat zijn er uiteraard oneindig veel – heeft een kleur. De vraag is: hoeveel verschillende kleuren zijn er minimaal nodig om ervoor te zorgen dat twee pixels die op een vaste afstand, bijvoorbeeld 1 centimeter, van elkaar vandaan liggen, nooit dezelfde kleur hebben?

Dit simpel ogende vraagstuk staat in de wiskunde bekend als het Hadwiger-Nelson-probleem, vernoemd naar de Zwitser Hugo Hadwiger en de Amerikaan Edward Nelson, die er in de jaren vijftig van de vorige eeuw, onafhankelijk van elkaar, over nadachten.

Aan twee kleuren heb je zeker niet genoeg en dat is simpel in te zien. Stel maar dat de foto enkel uit rode en blauwe pixels bestaat. Van de drie hoekpunten van een gelijkzijdige driehoek met zijden van 1 centimeter, die je ergens willekeurig op de foto kunt tekenen, hebben er dan minstens twee dezelfde kleur. Die twee hoekpunten (pixels) hebben een afstand van 1 centimeter, maar het was nu juist de bedoeling dat pixels die 1 centimeter van elkaar vandaan liggen, een verschillende kleur hebben.

Ook aan drie kleuren heb je niet genoeg (zie kader). Dat betekent dat er minstens vier kleuren nodig zijn. Sinds Hadwiger en Nelson hun probleem formuleerden, was er nauwelijks voortgang geboekt bij het oplossen ervan. Tot nu, want eerder deze maand zette Aubrey de Grey een artikel online waarin hij bewijst dat ook vier kleuren niet voldoende zijn. De Grey is een bekende Britse gerontoloog die de controversiële mening verkondigt dat mensen duizend jaar oud kunnen worden. Maar hij houdt zich dus ook met meetkundige vraagstukken bezig. Van oorsprong is hij informaticus en zijn computerkennis kwam van pas bij zijn oplossing van het ‘pixelprobleem’.

De Grey vond een configuratie van 1.581 pixels, die nooit onder de gestelde voorwaarde met vier kleuren kan worden gekleurd. Zijn vondst trok de aandacht van diverse wiskundigen, waaronder Marijn Heule, een Nederlander die is verbonden aan Texas University. De Grey mag dan een amateurwiskundige zijn, Heule noemt zijn resultaat „zeer betrouwbaar”. Per e-mail licht hij toe: „De Greys claim is gecheckt door een combinatie van zogeheten SAT solvers en algebrasoftware.” Heule heeft zich er de laatste weken intensief mee bezig gehouden. Daarbij wist hij De Greys oplossing ook nog te vereenvoudigen. Heule vond een configuratie van ‘slechts’ 826 pixels, waarvoor minstens vijf kleuren nodig zijn. Hij sluit niet uit in de komende tijd een exemplaar te vinden met nóg minder pixels.

Het Hadwiger-Nelson-probleem is nog niet opgelost, maar zeker is nu wel dat het aantal benodigde kleuren minstens vijf is. Een bovengrens is ook bekend: meer dan zeven kleuren zijn er in elk geval niet nodig. Daarvan bestaan verschillende bewijzen, onder meer van de Hongaar László Székely en de Amerikaan Ed Pegg.

Een alledaagse toepassing heeft dit probleem niet, maar de gebruikte bewijsmethode – met behulp van een computer – kan de wiskunde in de toekomst enorm vooruit helpen. „SAT solvers kunnen bewijzen leveren voor problemen waarin decennialang geen progressie is geboekt”, zegt Heule. Bovendien worden dergelijke methodes steeds vaker gebruikt om planningsproblemen in de industrie en het bedrijfsleven op te lossen, of om de veiligheid van nieuw ontwikkelde systemen te checken.