iedereen kan zich wel een piramidevormig stapeltje sinaasappels voorstellen. wiskundig gezien is dit een voorbeeld van een bolstapeling in de driedimensionale ruimte. vorig jaar werd de wiskundige gemeenschap verrast door twee opmerkelijke studies, waarin bewezen werd wat de beste manier is om bollen te stapelen in respectievelijk dimensies 8 en 24. maar wat moeten we ons voorstellen bij een hoogdimensionale bol? wat is er zo bijzonder aan de dimensies 8 en 24? En vooral … who cares?

Optimale bolstapelingen. Over sinaasappels en foutenverbeterende codes

Joeri Van der Veken

Beschouw even het volgende probleem: je krijgt een grote hoeveelheid identieke massieve bollen en je wil die zodanig plaatsen dat ze samen zo weinig mogelijk ruimte innemen. We houden geen rekening met de stabiliteit van het geheel, met de zwaartekracht of met andere fysische obstakels. De enige regel is dat de bollen elkaar wel mogen raken, maar dat ze elkaar niet overlappen. Het is dus louter een gedachte-experiment: hoe moeten we de bollen plaatsen zodat er zo weinig mogelijk open ruimte tussen zit? Reeds in 1611 formuleerde de Duitse wis- en natuurkundige en astronoom Johannes Kepler de vermoedelijke oplossing, maar hij gaf geen bewijs. Het werd een populair probleem onder wiskundigen en amateurwiskundigen, maar niemand slaagde erin het vermoeden van Kepler hard te maken. Het probleem werd dan ook wel eens smalend ‘de stelling die elke fruithandelaar kent, maar geen enkele wiskundige kan bewijzen’ genoemd. Inderdaad, de typische piramidevormige stapeling van sinaasappels die je wel eens in een marktkraam ziet, is een oplossing voor het probleem. Uiteindelijk kwam er – na bijna vierhonderd jaar – toch een bewijs, en wat voor één. In 1998 gaf de Amerikaanse wiskundige Thomas Hales een bewijs van meer dan driehonderd pagina’s dat bovendien gebruikmaakte van gigantische computerberekeningen.

Het vermoeden van Kepler werd wel eens smalend ‘de stelling die elke fruithandelaar kent, maar geen enkele wiskundige kan bewijzen’ genoemd

Om alles wat beter te begrijpen zullen we eerst het overeenkomstige tweedimensionale probleem bekijken, namelijk dat voor identieke schijven in het vlak. Vermits het probleem niet essentieel verandert als we de grootte van de schijven aanpassen, kunnen we ter vereenvoudiging veronderstellen dat ze allemaal straal 1 hebben. Laten we meteen ook de gangbare wiskundige ‘vereenvoudiging’ doorvoeren en veronderstellen dat we oneindig veel zulke schijven hebben. Op het eerste gezicht maakt dit het misschien eerder moeilijker, maar in feite vergemakkelijkt het wel degelijk de zaak omdat we bijvoorbeeld geen rekening moeten houden met de rand van de figuur die we gaan vormen. De vraag is: hoe moeten we de schijven plaatsen zodat een zo groot mogelijk deel van het vlak bedekt is? Uiteraard is enige voorzichtigheid geboden met het meten van het bedekte deel: omdat we oneindig veel schijven hebben, zal de bedekte oppervlakte oneindig zijn, net zoals de oppervlakte van het vlak zelf oneindig is. Toch kan men op een precieze manier een betekenis geven aan dit concept, die bovendien overeenkomt met de intuïtie. Als het vlak bijvoorbeeld volledig bedekt wordt door een oneindig groot schaakbordpatroon, dan zal iedereen het erover eens zijn dat de helft van het vlak wit gekleurd is en de helft zwart, hoewel het witte deel, het zwarte deel en het volledige vlak allemaal oneindige oppervlakte hebben. De volgende figuur toont twee mogelijke stapelingen van de schijven. Beide stapelingen zijn periodiek in de zin dat eenzelfde patroon zich steeds weer herhaalt. Niemand zegt dat de oplossing van het probleem periodiek moet zijn, maar uiteraard zijn periodieke stapelingen gemakkelijker te behandelen dan willekeurige.

In de linkse figuur (voor de figuren: zie de papieren versie van Karakter 60) vormen de middelpunten van de schijven een rooster waarin vierkanten met zijde 2 te zien zijn, die niet overlappen en samen het hele vlak bedekken. Zo’n vierkant heeft oppervlakte 4. Slechts een deel van dit vierkant wordt bedekt door schijven en dit deel heeft de oppervlakte van één volledige schijf, namelijk p. Het bedekte deel van één vierkant en a fortiori van het hele vlak is dus p/4 ≈ 0,785. We zeggen dat deze stapeling een dichtheid van ongeveer 78,5 procent heeft. In de rechtse figuur vormen de middelpunten opnieuw een rooster, het zogenaamde honingraatrooster. Hierin zien we regelmatige zeshoeken met zijde 2 die elkaar niet overlappen en het hele vlak bedekken. Zo’n zeshoek heeft oppervlakte 6√3 en het deel ervan dat bedekt wordt door schijven heeft de oppervlakte van drie schijven, 3p. De dichtheid is dus 3p/6√3 = p/√12 ≈ 0,907, of ongeveer 90,7 procent. De tweede stapeling is dus dichter dan de eerste, maar is ze ook de dichtst mogelijke? De Noorse wiskundige Axel Thue beweerde in 1892 al van wel en het eerste echte bewijs werd in 1940 gegeven door de Hongaarse wiskundige László Fejes Tóth. Hij bewees bovendien dat deze stapeling de unieke oplossing onder de periodieke stapelingen is, uiteraard op draaiingen en verschuivingen na. Ondertussen zijn er verschillende bewijzen voor dit resultaat bekend en hoewel ze stuk voor stuk een origineel idee vergen, en dus zeker niet triviaal zijn, zijn sommige toch elementair te noemen, zeker in vergelijking met wat er in hogere dimensies te wachten stond.

Nu we de oplossing van het tweedimensionale probleem kennen, zouden we aan de hand hiervan kunnen proberen om ‘laag per laag’ een oplossing voor het driedimensionale geval te construeren. We beginnen met het plaatsen van een eerste laag bollen zodat alle middelpunten in eenzelfde vlak liggen en een honingraatrooster vormen. Het bovenaanzicht ziet er dus precies zo uit als de rechtse figuur hierboven. We gaan nu een tweede identieke laag op de eerste plaatsen. We zullen de middelpunten van de bollen in de tweede laag echter niet boven die van de bollen in de eerste laag plaatsen, maar wel telkens precies boven een opening tussen drie bollen in de eerste laag die elkaar twee aan twee raken. Op die manier komt de tweede laag zo laag mogelijk te liggen en vergroot de dichtheid. Bij het plaatsen van een derde identieke laag merken we iets bijzonders op. We willen de middelpunten uiteraard boven openingen in de tweede laag plaatsen, maar er zijn verschillende mogelijkheden: we kunnen ze precies boven de middelpunten van de eerste laag plaatsen of net niet. Bij het plaatsen van elke nieuwe laag hebben we deze keuzevrijheid en het zal blijken dat alle bolstapelingen die we op deze manier bekomen eenzelfde dichtheid hebben, namelijk p/√18 ≈ 0,740, of ongeveer 74 procent. Alles wijst erop dat dit geen goede aanpak is: de bekomen dichtheid is een pak lager dan die van de optimale stapeling in twee dimensies, we krijgen essentieel verschillende stapelingen met eenzelfde dichtheid en bovendien lijkt de hele aanpak vrij naïef. En toch: dit geeft een juiste oplossing. De piramidevormige fruitstapelingen die we hierboven reeds vermeldden, worden inderdaad op deze manier bekomen. Merk op dat elke laag van de piramide gebaseerd is op de linkse stapeling in de figuur hierboven in plaats van op de rechtse. Inderdaad, de piramide is een draaiing van een constructie zoals net beschreven: in elk zijvlak herken je namelijk wel het honingraatrooster. De ideale bolstapeling is dus niet uniek, zelfs niet als we ons beperken tot periodieke stapelingen. Meer nog: ondertussen weet men dat het aantal essentieel verschillende optimale bolstapelingen in dimensie drie overaftelbaar is, een term die wiskundigen gebruiken om een oneindig grote hoeveelheid aan te duiden die je zelfs niet kunt beginnen tellen, zoals het aantal punten in het vlak. Het feit dat er overaftelbaar veel oplossingen zijn, is één van de problemen waarmee Hales te maken kreeg voor zijn bewijs, waarvoor hij trouwens een aanpak volgde die gesuggereerd werd door Fejes Tóth.

Het opmerkelijke aan hoogdimensionale ruimten is dat er zo onvoorstelbaar veel plaats is

Laten we nu naar een willekeurige dimensie n kijken. Zoals we een punt in het vlak kunnen weergeven met twee coördinaten en een punt in de driedimensionale ruimte met drie coördinaten, kunnen we aan een punt in de n-dimensionale ruimte denken als een n-tal van coördinaten (x1, …, xn). Door twee verschillende punten in de n-dimensionale ruimte bestaat er altijd een unieke rechte lijn en we kunnen de afstand tussen punten dus meten zoals voor punten op een rechte. Een n-dimensionale bol is dan per definitie de verzameling van punten in de n-dimensionale ruimte die maximaal op een gegeven afstand (de straal van de n-dimensionale bol) van een gegeven punt (het middelpunt van de n-dimensionale bol) liggen. Voor n = 2 krijgen we gewoon een schijf en voor n = 3 een driedimensionale bol. Het opmerkelijke aan hoogdimensionale ruimten is dat er zo onvoorstelbaar veel plaats is. Denk bijvoorbeeld aan de volgende situatie. Als je in het vlak vier schijven met straal 1 tegen elkaar schuift op zo’n manier dat hun middelpunten een vierkant vormen, dan past er tussen deze vier schijven een klein schijfje met straal √2 – 1. Als je op dezelfde manier in de ruimte acht bollen tegen elkaar schuift zodat hun middelpunten op de hoekpunten van een kubus liggen, past er in het midden een kleine bol tussen met straal √3 – 1. In de n-dimensionale ruimte kan je hetzelfde doen met 2n n-dimensionale bollen en nu past er in het midden een ‘kleine’ bol met straal √n – 1. Als n groot is, is deze laatste bol echter niet zo klein meer: in dimensie n = 4, past er al een nieuwe bol met straal 1 tussen de gegeven bollen en vanaf dimensie n = 5 zelfs een nog grotere.

Alle ingrediënten zijn dus aanwezig om de zoektocht naar de ideale bolstapeling aan te vatten in willekeurige dimensies. Voor dimensies groter dan drie bestond er tot vorig jaar voor geen enkele dimensie een bewijs dat uitlegde wat de optimale bolstapeling of de optimale dichtheid nu precies is. Wel vonden de wiskundigen Henry Cohn en Noam Elkies in 2003 hulpfuncties die voor elke dimensie bovengrenzen op de optimale dichtheid geven. In zowat alle dimensies ligt de dichtheid van de best bekende bolstapeling ver onder de kleinst bekende bovengrens, behalve in dimensies 8 en 24. Precies in deze dimensies zijn er immers roosters bekend die uitermate geschikt zijn om een bolstapeling te construeren, respectievelijk het rooster E8 (genoemd naar een wiskundige structuur, de Liegroep E8) en het Leechrooster (genoemd naar de Britse wiskundige John Leech), ook wel met L24 genoteerd. Denk hierbij dus aan analogen van het honingraatrooster in deze dimensies. De roosters duiken op in verschillende takken van de wiskunde, zoals getaltheorie, combinatoriek en hyperbolische meetkunde, en zelfs van de theoretische fysica, zoals snaartheorie, en hebben enorm veel symmetrie. Er zijn zelfs nieuwe types van symmetrieën ontdekt door het Leechrooster te bestuderen. Om nogmaals te illustreren hoeveel plaats er is in hoogdimensionale ruimten, vermelden we dat in de bolstapeling gebaseerd op E8 elke bol 240 buren heeft, terwijl er dat voor de bolstapeling gebaseerd op L24 maar liefst 196 560 zijn. Beide bolstapelingen hebben een zodanig grote dichtheid, dat het uit de resultaten van Cohn en Elkies volgt dat een optimale bolstapeling nog maximaal 0,0000000000000000000000000001 procent dichter zou kunnen zijn. Iedereen ging er dus van uit dat deze twee bolstapelingen wel optimaal moesten zijn, maar er was geen bewijs, tot de Iraanse wiskundige Maryna Viazovska in maart 2016 een artikel op het internet plaatste waarin ze bewees dat de bolstapeling gebaseerd op E8 optimaal is in dimensie 8. Dit deed ze door de bovengrens op de dichtheid te verlagen met nieuwe hulpfuncties, gebaseerd op zogenaamde modulaire vormen, die eerder het onderwerp vormden van haar doctoraatsthesis. Dezelfde avond nog kreeg ze een e-mail van Cohn die suggereerde dat dezelfde techniek ook zou kunnen werken voor dimensie 24. Een week later plaatsten ze samen met Abhinav Kumar, Stephen D. Miller en Danylo Radchenko een artikel op het internet waarin ze bewezen dat ook de bolstapeling gebaseerd op L24 optimaal is. Hales omschreef het werk van Viazovska als ‘she pulled a Ramanujan’, een verwijzing naar de Indische wiskundige die erom bekend stond om briljante ideeën schijnbaar uit het niets tevoorschijn te toveren. Beide artikels verschenen eerder dit jaar in het toonaangevende tijdschrift Annals of Mathematics.

Hales omschreef het werk van Viazovska als ‘she pulled a Ramanujan’, een verwijzing naar de Indische wiskundige die erom bekend stond om briljante ideeën schijnbaar uit het niets tevoorschijn te toveren

Waarom is iemand nu geïnteresseerd in optimale bolstapelingen? Terwijl de vraag in dimensies 2 en 3 nog gebaseerd is op een probleem uit de realiteit dat bovendien een model vormt in de studie van materialen opgebouwd uit korrels (zand, rijst, poeders, …), die belangrijk is voor bijvoorbeeld de farmacie, bouwsector, voedingsindustrie en de landbouw, zijn er ook verrassende toepassingen van de hogerdimensionale gevallen. Als we een boodschap verzenden via een communicatiekanaal zoals internet of een gsm, wordt die omgezet in een rij van nullen en enen. Bij het verzenden kan er uiteraard iets mislopen en zullen sommige nullen in enen veranderen en omgekeerd. Er is een heel onderzoeksgebied dat gewijd is aan het detecteren en verbeteren van zulke fouten. Een eenvoudig voorbeeld is het volgende: stel dat we aan een rij van n nullen en enen een extra controlecijfer toevoegen: een één als het oorspronkelijke aantal enen oneven is en een nul als het oorspronkelijke aantal enen even is. Op die manier krijgen we een rij van n+1 cijfers met een even aantal enen, die we zullen verzenden. Als de ontvanger een oneven aantal enen ziet, weet hij dat er iets is misgegaan, deze code kan dus één fout detecteren. Met een meer geavanceerde aanpak kunnen we ook meerdere fouten detecteren en zelfs verbeteren. De toegelaten codewoorden kunnen we bekijken als punten. In het vorige voorbeeld zijn dit de punten in een (n+1)-dimensionale ruimte met coördinaten 0 of 1, waarbij een even aantal coördinaten 1 is. Stel je nu rond elk toegelaten codewoord een bol voor, allemaal met dezelfde straal. Als we een boodschap ontvangen die niet overeenkomt met een toegelaten codewoord, maar wel in één van de bollen ligt, ligt het voor de hand deze te verbeteren naar het meest nabijgelegen toegelaten codewoord, het middelpunt van de bol. Om een goed werkend algoritme te hebben is het dus belangrijk dat er zo weinig mogelijk plaats tussen de bollen is, maar dat ze elkaar niet overlappen. We moeten op zoek naar een optimale bolstapeling. Zo werden de allereerste foto’s van Jupiter, Saturnus, Uranus en Neptunus, genomen door de NASA Voyagers, gelanceerd in 1977, naar de aarde gestuurd met behulp van een foutenverbeterende code die gebruikmaakt van een bolstapeling in dimensie 24. En als je vandaag je favoriete film op blu-ray bekijkt, worden de fouten bij het uitlezen verbeterd met een code waarvan de woorden maar liefst in een 248-dimensionale ruimte liggen.

De belangrijkste gevolgen van de zoektocht naar optimale bolstapelingen zijn wellicht echter niet de directe toepassingen, noch de resultaten zelf. Waar het wel om gaat, is dat er gaandeweg nieuwe wiskunde werd ontdekt, nieuwe roosters, nieuwe symmetrieën, nieuwe functies, die belangrijk zijn in verschillende takken van de wiskunde en fysica en daar weer tot andere ontdekkingen en toepassingen zullen leiden. En dat terwijl alles begon met een schijnbaar eenvoudige vraag aan het begin van de zeventiende eeuw.

Maryna Viazovska, ‘The sphere packing problem in dimension 8’, in:
Annals of Mathematics, 2017, 185, 991-1015 (beschikbaar als preprint op https://arxiv.org/abs/1603.04246).
Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko en Maryna Viazovska, ‘The sphere packing problem in dimension 24’, in: Annals of Mathematics, 2017, 185, 1017-1033 (beschikbaar als preprint op https://arxiv.org/abs/1603.06518).

Joeri Van der Veken is als wiskundige verbonden aan de KU Leuven, waar hij aan het hoofd staat van de Afdeling Meetkunde.