🔢 mathematics

The lattice packing problem in dimension 9 by Voronoi's algorithm

In dit artikel wordt de dichtste roosterverpakking in negen dimensies bepaald door via Voronoi's algoritme alle 2.237.251.040 perfecte roosters te berekenen, waarmee wordt aangetoond dat het gelamineerde rooster $\Lambda_9$ optimaal is en de mogelijke kissing numbers in deze dimensie zijn vastgesteld.

Oorspronkelijke auteurs: Mathieu Dutour Sikirić, Wessel van Woerden

Gepubliceerd 2026-02-10

📖 3 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mathieu Dutour Sikirić, Wessel van Woerden

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme doos hebt vol met knikkers van precies dezelfde grootte. Je wilt deze knikkers zo efficiënt mogelijk in de doos stoppen, zodat er zo min mogelijk lege ruimte overblijft. Dit klinkt simpel, maar in de wiskunde is dit een van de moeilijkste puzzels die er bestaan: het Sphere Packing Problem (het probleem van het verpakken van bollen).

In dit wetenschappelijke artikel hebben twee wiskundigen, Mathieu Dutour Sikirić en Wessel van Woerden, een gigantische sprong gemaakt in deze puzzel, specifiek voor de "9e dimensie".

Hier is de uitleg in begrijpelijke taal:

1. De 9e Dimensie: Een onzichtbare speeltuin

Wij leven in een wereld met drie dimensies (lengte, breedte, hoogte). Maar wiskundigen kunnen ook rekenen met 4, 8 of zelfs 9 dimensies. Denk aan een 9e dimensie als een soort "extra richtingen" waar je niet naar kunt kijken, maar waar de knikkers wel naartoe kunnen rollen om de gaten op te vullen.

Het probleem is: hoe ziet de perfecte "structuur" van die knikkers eruit in die 9e dimensie? In 3 dimensies weten we het (de manier waarop sinaasappels in de supermarkt liggen), maar in 9 dimensies is het een wiskundig labyrint.

2. Het algoritme: De digitale ontdekkingsreiziger

De onderzoekers gebruikten een methode die we het Voronoi-algoritme noemen. Je kunt dit zien als een soort digitale ontdekkingsreiziger die een onbekend landschap verkent.

Stel je voor dat je een landkaart wilt maken van alle mogelijke manieren om knikkers te stapelen. De ontdekkingsreiziger begint op één punt (een bekende stapelmethode) en kijkt: "Als ik deze knikker een klein beetje verschuif, ontstaat er dan een nieuwe, unieke manier om te stapelen?" Als het antwoord 'ja' is, zet hij een nieuw punt op de kaart.

In de 9e dimensie is dit landschap echter niet zomaar een heuvelachtig gebied; het is een gigantische, bijna oneindige jungle.

3. De prestatie: Een digitale bergverzet

Wat deze onderzoekers hebben gedaan, is ongekend. Ze hebben niet alleen een paar manieren gevonden, ze hebben alle mogelijke unieke structuren (de zogenaamde "perfecte roosters") in de 9e dimensie geteld.

Het aantal is astronomisch: 2.237.251.040.
Dat zijn ruim twee miljard verschillende manieren om die knikkers te stapelen! Om dit te berekenen, moesten ze enorme supercomputers gebruiken die dagenlang onafgebroken doorwerkten. Het is alsovergelijkbaar met het tellen van elk individueel korreltje zand in een hele zandbak, om vervolgens te kunnen zeggen: "Dit is de allerbeste manier om de zandkorrels te rangschikken."

4. De ontdekking: De winnaar is bekend

Dankzij dit gigantische rekenwerk hebben ze de winnaar van de wedstrijd gevonden. Ze hebben bewezen dat een specifieke structuur, genaamd de $\Lambda_9$ (Laminated Lattice), de absolute kampioen is. Dit is de manier waarop je de knikkers in de 9e dimensie moet stapelen om de allerkleinste gaatjes over te houden.

5. Wat hebben we eraan? (De "Kissing Number")

Een grappig bijproduct van hun onderzoek is de oplossing voor de "Kissing Number" vraag. Stel je voor dat je een knikker in het midden legt. Hoeveel andere knikkers kunnen er tegelijkertijd de middelste knikker "kussen" (aanraken) zonder dat ze elkaar in de weg zitten?

In de 9e dimensie hebben ze precies uitgerekend welke aantallen mogelijk zijn. Het is niet zomaar elk getal; er zijn bepaalde "magische getallen" waar de knikkers precies passen.

Samenvatting

Dit papier is eigenlijk het verslag van een digitale expeditie naar de grenzen van de menselijke rekenkracht. De onderzoekers hebben de chaos van de 9e dimensie getemd, de miljarden mogelijkheden in kaart gebracht en de ultieme blauwdruk gevonden voor de meest efficiënte verpakking ooit.

Technische Samenvatting: Het Lattice Packing Probleem in Dimensie 9 via Voronoi’s Algoritme

1. Het Probleem: Sphere Packing en Lattice Packings

Het centrale probleem in dit onderzoek is het sphere packing problem: het vinden van de maximale dichtheid waarmee identieke $n$ -dimensionale bollen in de $\mathbb{R}^n$ kunnen worden gestapeld. Hoewel dit probleem in specifieke dimensies (1, 2, 3, 8 en 24) is opgelost, blijft het voor andere dimensies extreem complex.

Een natuurlijke restrictie is het lattice packing problem, waarbij de centra van de bollen een rooster (lattice) vormen. De dichtheid van een rooster wordt bepaald door de Hermite-constante $\gamma_d$ . Het doel is om het rooster te vinden dat de Hermite-invariant $\gamma(Q)$ maximaliseert. Voronoi bewees dat een optimaal rooster altijd een perfect rooster moet zijn. Een perfect rooster wordt uniek bepaald door zijn minimale vectoren.

2. Methodologie: Voronoi’s Algoritme en Computationele Innovaties

De auteurs maken gebruik van Voronoi’s algoritme, een graaf-traversal methode die alle niet-isomorfe perfecte roosters in een gegeven dimensie systematisch opsomt. De complexiteit van dit algoritme groeit echter super-exponentieel met de dimensie, waardoor dimensie 9 tot nu toe onbereikbaar was.

Om de enorme computationele last van dimensie 9 te overwinnen, hebben de auteurs verschillende cruciale verbeteringen doorgevoerd:

Dual Description Problem under Symmetry: Het grootste knelpunt is het berekenen van de "buren" van een perfect rooster. Dit vereist het oplossen van het duale beschrijvingsprobleem (het vinden van de facetten van een polyedrische kegel). De auteurs ontwikkelden een methode om dit te doen met behulp van polyedrische symmetrieën (automorfismen), waardoor ze alleen de banen (orbits) van facetten hoeven te berekenen in plaats van elk facet afzonderlijk.
Recursive Adjacency Decomposition Method (ADM): Een recursief algoritme om de facetten van een kegel te vinden door de verbondenheid van de facetten in de face-lattice te verkennen.
Canonical Forms: Om te voorkomen dat miljarden equivalente roosters dubbel worden opgeslagen, gebruikten de auteurs geavanceerde canonieke functies. Ze reduceerden het probleem van rooster-equivalentie tot het probleem van graaf-isomorfisme via gewogen grafen.
Parallelisatie via MPI: Het algoritme werd geparallelliseerd met het Message Passing Interface (MPI), waardoor het over honderden processen kon worden verdeeld.
Saving Bank (Memoization): Een systeem om eerder berekende duale beschrijvingen op te slaan en te hergebruiken, wat essentieel was voor de efficiëntie bij complexe gevallen.

3. Belangrijkste Resultaten

De uitvoering van het algoritme leidde tot een volledige classificatie van de perfecte roosters in dimensie 9.

Classificatie van Perfecte Roosters: Er zijn exact 2.237.251.040 niet-isomorfe perfecte roosters in dimensie 9 gevonden.
Optimale Dichtheid: De auteurs bewijzen dat het gelamineerde rooster $\Lambda_9$ de dichtste lattice packing in dimensie 9 oplevert. Hiermee wordt de Hermite-constante voor dimensie 9 vastgesteld op $\gamma_9 = 2$ .
Kissing Numbers: Het onderzoek levert een volledige classificatie op van de mogelijke kissing numbers (het aantal minimale vectoren) in dimensie 9. De verzameling is exact: $2 \cdot \{1, \dots, 91, 99, 120, \dots, 129, 136\}$ .
Basis van Minimale Vectoren: De auteurs tonen aan dat, met uitzondering van het Coxeter-rooster $A_9^2$ , alle perfecte roosters in dimensie 9 een basis hebben die bestaat uit minimale vectoren.
Hollow Perfect Lattices: Ze identificeren het Coxeter-rooster $A_9^5$ als het enige "hollow" perfecte rooster in dimensie 9.
Bergé-Martinet Invariant: Er zijn 18 dual-extreme perfecte roosters gevonden die de lokale maxima van de Bergé-Martinet invariant bereiken.

4. Betekenis en Impact

Dit werk is een mijlpaal in de geometrische getaltheorie en de discrete meetkunde. Het overbrugt het gat tussen dimensie 8 en dimensie 24 door een dimensie aan te pakken die voorheen als computationeel onmogelijk werd beschouwd. De ontwikkelde software en de enorme dataset (ca. 150 GB aan data) vormen een belangrijke bijdrage aan de wetenschappelijke gemeenschap. Bovendien biedt het resultaat $\gamma_8 = \gamma_9 = 2$ het bewijs dat de Hermite-constante niet strikt monotoon stijgend hoeft te zijn in hogere dimensies.