🔢 mathematics

Lean-verified lower bounds for the Shannon capacity of odd cycles

Dit artikel presenteert nieuwe, volledig geformaliseerde ondergrenzen in Lean voor de Shannon-capaciteiten van verschillende kleine oneven cycli ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ), afgeleid via een iteratieve procedure gebaseerd op recente methoden door Gao en Itty et al.

Oorspronkelijke auteurs: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Gepubliceerd 2026-08-03

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Pjotr Buys, Sven Polak, Jeroen Zuiddam

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 geheime boodschap probeert te sturen door een lawaaierige, chaotische stad. De stad is vol afleidingen, en soms raakt je signaal verward met de verkeerde straatnamen. In de wereld van de informatietheorie is dit een echt probleem: hoe verstuur je data perfect zonder fouten? In de jaren 1950 bedacht een wiskundige genaamd Claude Shannon dat als je een "ruisachtig" kanaal hebt, je nog steeds perfecte berichten kunt verzenden, maar alleen als je slim bent in hoe je je letters bij elkaar groepeert. Hij introduceerde een concept genaamd "Shannon-capaciteit", wat in essentie een score is die de maximale snelheid aangeeft waarmee je perfecte berichten kunt verzenden via een specifiek type ruisachtig netwerk.

Om dit te visualiseren, stel je een spel voor dat gespeeld wordt op een kaart van de stad. De kaart is een graaf, waarbij de kruispunten punten zijn en de straten lijnen. Sommige straten zijn "veilig" om samen te reizen, terwijl andere gevaarlijk zijn en voor een crash zullen zorgen als je ze met elkaar mengt. Het doel is om de grootste mogbare groep kruispunten (een "onafhankelijke verzameling") te kiezen die je kunt bezoeken zonder ooit een gevaarlijke straat tussen twee daarvan te nemen. De "Shannon-capaciteit" stelt een lastige vraag: als je dit spel niet slechts één keer speelt, maar door meerdere kopieën van de kaart op elkaar te stapelen om een gigantische, meerdimensionale stad te creëren, hoe veel groter kan je veilige groep dan worden? Voor sommige vormen weten we het antwoord. Voor andere, specifiek de onregelmatige lussen in de stad (zoals een vijfhoek of een zevenhoek), is het antwoord decennialang een mysterie gebleven. Het is alsoal het kennen van de maximumsnelheid op een rechte weg, maar geen enkel idee hebben hoe snel je kunt gaan op een kronkelend, zevenhoekig parcours.

Dit artikel gaat over het kraken van dat mysterie voor verschillende van die lastige, zevenhoekige (en grotere) parcours's. De auteurs, een team van wiskundigen en informatici, hebben nieuwe, iets snellere manieren gevonden om perfecte berichten door deze specifieke lussen te sturen. Ze hebben niet simpelweg gegokt; ze gebruikten een slim, stapsgewijs recept om steeds grotere groepen veilige kruispunten te bouwen. Om er zeker van te zijn dat ze geen enkele fout maakten in hun complexe wiskunde, hadden ze een superstrenge digitale scheidsrechter genaamd "Lean" die elke stap van hun werk controleerde. Het resultaat? Ze hebben bewezen dat voor deze specifieke onregelmatige lussen, de maximale snelheid van perfecte communicatie hoger is dan voorheen berekend.

Het Spel van Veilige Kruispunten

Laten we ontleden wat de auteurs daadwerkelijk hebben gedaan. Ze keken naar grafen die eruitzien als eenvoudige ringen met een oneven aantal punten: een ring van 7, een ring van 11, een ring van 13, enzovoort. Een lange tijd kenden wiskundigen de "maximumsnelheid" (de Shannon-capaciteit) voor een ring met 5 punten. Maar voor ringen met 7 punten of meer, bleef het antwoord in een mist gehuld. We wisten dat het ten minste een bepaald aantal was, maar we wisten niet of het hoger kon zijn.

De auteurs gebruikten een methode die aanvoelt als een magisch recept voor het laten groeien van je veilige groep. Stel je voor dat je een kleine, veilige club vrienden (een verzameling punten) hebt op een enkele kaart. Het artikel beschrijft een "productstelling", wat een machine is die twee van deze kaarten pakt en ze op elkaar stampt om een nieuwe, grotere kaart te creëren. Als je een veilige club hebt op de eerste kaart en een veilige club op de tweede kaart, kun je ze combineren om een veilige club op de nieuwe, grotere kaart te maken. Meestal is de grootte van deze nieuwe club simpelweg de grootte van de eerste club vermenigvuldigd met de tweede. Maar de auteurs vonden een speciale "gadget" of truc. Door een specifiek patroon van verbindingen te gebruiken (een "geldige tuple"), konden ze de nieuwe club groter maken dan de eenvoudige vermenigvuldiging zou suggereren.

Denk er zo over na: als je een team hebt van 2 mensen die samen kunnen werken zonder ruzie te maken, en je combineert twee dergelijke teams, dan verwacht je misschien een team van 4. Maar met deze speciale truc vonden de auteurs een manier om de teams te combineren en een team van 5 mensen te krijgen die allemaal perfect met elkaar door één deur kunnen. Door deze truc keer op keer te herhalen, de kaarten steeds hoger op te stapelen, konden ze deze veilige teams laten groeien tot massieve groepen.

De Nieuwe Records

Het team paste dit recept toe op zeven verschillende onregelmatige ringen: die met 7, 11, 13, 15, 19, 21 en 23 punten. Voor elk van hen begonnen ze met een bekende veilige groep en draaiden ze hun "stapelmachine" vele malen. Het resultaat was een nieuwe, hogere ondergrens voor de Shannon-capaciteit.

Dit is wat zij vonden, met de exacte getallen zoals zij die berekend hebben:

Voor de 7-puntenring bewezen ze dat de capaciteit ten minste 3.258805369885 is. Dit is een klein beetje hoger dan de vorige beste schatting.
Voor de 11-puntenring is de nieuwe ondergrens 5.294502522149.
Voor de 13-puntenring hebben ze de grens verlegd naar 6.302455083464.
Voor de 15-puntenring is het getal 7.301600534487.
Voor de 19-puntenring bereikten ze 9.357192705918.
Voor de 21-puntenring is de ondergrens 10.342455853338.
En voor de 23-puntenring vonden ze een capaciteit van ten minste 11.328224257774.

Deze getallen zien er misschien uit als een reeks willekeurige cijfers, maar in de wereld van de informatietheorie vertegenwoordigen ze een concrete verbetering. Het betekent dat we voor deze specifieke netwerken nu zeker weten dat we berichten iets sneller kunnen versturen dan we voorheen voor mogelijk hielden.

De Digitale Scheidsrechter

Wat dit artikel bijzonder maakt, is niet alleen de getallen, maar de manier waarop ze die hebben verkregen. De wiskunde die erbij betrokken is, is ongelooflijk complex en omvat enorme datasets en duizenden stappen. Het is het soort werk waarbij een mens gemakkelijk een kleine fout zou kunnen maken. Om dit op te lossen, schreven de auteurs hun volledige bewijs in een computertaal genaamd Lean.

Beschouw Lean als een hyperstrenge, digitale scheidsrechter die geen "ik denk dat dit klopt" of "het ziet er goed uit voor mij" accepteert. Het eist een absolute, logische bewijsvoering voor elke stap. Als de auteurs een fout in hun logica zouden maken, zou Lean stoppen en zeggen: "Nee, dat volgt er niet uit." Het feit dat het artikel "Lean-geverifieerd" is, betekent dat een computer elke regel van hun redenering heeft gecontroleerd en heeft bevestigd dat hun nieuwe ondergrenzen wiskundig solide zijn. Ze hebben niet alleen de resultaten gesimuleerd; ze hebben ze formeel bewezen.

De auteurs vermelden ook dat ze grote taalmodellen (zoals geavanceerde AI-chatbots) hebben gebruikt om hen te helpen de initiële patronen en recepten voor deze veilige groepen te vinden. Het is een beetje als het hebben van een creatieve assistent die een wild idee suggereert, waarna de wiskundigen hun rigoureuze instrumenten gebruiken om te testen of dat idee daadwerkelijk standhoudt. In dit geval suggereerde de AI een pad, en het mens-wiskundige-AI-team liep dat pad helemaal af naar een geverifieerde finishlijn.

Waarom het ertoe doet

Je vraagt je misschien af: "En dus? We weten alleen dat het getal een klein beetje hoger is." Het antwoord ligt in de aard van het probleem. Decennialang was de capaciteit van deze onregelmatige ringen een openstaande vraag. We wisten dat het antwoord ergens tussen een ondergrens en een bovengrens (de Lovász-bound) lag, maar we konden het niet vastpinnen. Elke keer dat we de ondergrens omhoog duwen, zelfs met een fractie, verkleinen we de kloof. We komen dichter bij het ware antwoord.

Dit werk laat zien dat er zelfs voor problemen die al lange tijd vastzitten, nog steeds ruimte is voor verbetering als je de juiste instrumenten hebt en het geduld om je werk te controleren met de meest rigoureuze standaarden mogelijk. De auteurs hebben het mysterie van de Shannon-capaciteit voor alle onregelmatige ringen niet volledig opgelost, maar ze hebben een paar meer mistige hoekjes opgehelderd, waarmee ze hebben bewezen dat we voor ringen van 7, 11, 13, 15, 19, 21 en 23 net iets sneller kunnen communiceren dan we voorheen geloofden.

Technische Samenvatting: Lean-geverifieerde ondergrenzen voor de Shannon-capaciteit van oneven cycli

Probleemstelling
Het artikel behandelt het langlopende openstaande probleem van het bepalen van de Shannon-capaciteit, $\Theta(G)$ , voor oneven cycli $C_n$ waarbij $n \geq 7$ . De Shannon-capaciteit is gedefinieerd als $\Theta(G) := \sup_{d \geq 1} \alpha(G^{\boxtimes d})^{1/d}$ , waarbij $\alpha$ de onafhankelijkheidsgetal is en $\boxtimes$ het sterke graafproduct is. Terwijl Lovász bepaalde dat $\Theta(C_5) = \sqrt{5}$ met behulp van de theta-functie $\vartheta(G)$ , blijven de exacte capaciteiten voor alle oneven cycli van lengte zeven of groter onbekend. De primaire uitdaging ligt in het vinden van grotere onafhankelijke verzamelingen in hogere sterke machten van deze cycli om de bekende ondergrenzen te verbeteren.

Methodologie
De auteurs maken gebruik van een iteratieve procedure gebaseerd op een "gadget-constructie" en een "productlemma" die recentelijk door Gao (2026) is voorgesteld, wat op zijn beurt voortbouwt op methoden van Itty, Rosin, Carstensen en Reichman (2026). De kern van de methodologie omvat:

Geldige tupels: Voor een graaf $G$ wordt een geldig tupel $\tau = (I, S, f_0, f_1, X)$ gedefinieerd, waarbij $I$ een onafhankelijke verzameling is, $S \subseteq I$ , en $f_0, f_1$ specifieke afbeeldingen zijn die voldoen aan strikte buurtrestricties. Dit tupel genereert een "profiel" $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N_G[f_0(S)] \cup N_G[f_1(S)])|)$ .
Productoperatie: Een binaire operatie $\star$ wordt gedefinieerd op profielen. Stelling 1 stelt vast dat als $\tau$ en $\tau'$ geldige tupels zijn voor grafen $G$ en $H$ , er een geldig tupel bestaat voor de sterke productgraaf $G \boxtimes H$ waarvan het profiel het $\star$ -product is van de individuele profielen.
Iteratieve constructie: Beginnend bij een computationeel ontdekt geldig tupel in een specifieke macht van een oneven cyclus, passen de auteurs de $\star$ -productiteratie toe om profielen voor hogere machten te genereren. Dit proces construeert onafhankelijke verzamelingen in sterke machten $C_n^{\boxtimes d}$ die groter zijn dan die verkregen door eenvoudige Cartesiaanse producten van de basis-onafhankelijke verzamelingen.
Formele verificatie: Een cruciaal onderdeel van de methodologie is de volledige formalisering van deze grenzen in de Lean proof assistant. De basis-tupels (verzamelingen $I, S, X$ en afbeeldingen $f_0, f_1$ ) worden gecodeerd als expliciete literalen, en hun geldigheid wordt mechanisch geverifieerd binnen de Lean-omgeving.

Belangrijkste bijdragen en resultaten
Het artikel presenteert nieuwe, verbeterde ondergrenzen voor de Shannon-capaciteiten van zeven kleine oneven cycli ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ). Deze grenzen worden afgeleid door specifieke basis-geldige tupels te identificeren en de iteratieve productprocedure toe te passen. De resultaten zijn:

$\Theta(C_7)$ : Verbeterd naar $\geq 3.258805369885\dots$ (voorheen $3.2587891\dots$ door Gao 2026). De constructie maakt gebruik van een basis-tupel in $C_7^{\boxtimes 5}$ geïtegreerd naar macht 200.
$\Theta(C_{11})$ : Verbeterd naar $\geq 5.294502522149\dots$ (voorheen $5.2897736\dots$ door Itty et al. 2026). Het basis-tupel bevindt zich in $C_{11}^{\boxtimes 3}$ , geïtegreerd naar macht 174.
$\Theta(C_{13})$ : Verbeterd naar $\geq 6.302455083464\dots$ (voorheen $6.3001091\dots$ door Itty et al. 2026). Het basis-tupel bevindt zich in $C_{13}^{\boxtimes 6}$ , geïtegreerd naar macht 432.
$\Theta(C_{15})$ : Verbeterd naar $\geq 7.301600534487\dots$ (voorheen $7.3013990\dots$ door Itty et al. 2026). Het basis-tupel bevindt zich in $C_{15}^{\boxtimes 4}$ , geïtegreerd naar macht 4096.
$\Theta(C_{19})$ : Verbeterd naar $\geq 9.357192705918\dots$ (voorheen $9.3571200\dots$ door Baumert et al. 1971). Het basis-tupel bevindt zich in $C_{19}^{\boxtimes 4}$ , geïtegreerd naar macht 16384.
$\Theta(C_{21})$ : Verbeterd naar $\geq 10.342455853338\dots$ (voorheen $10.3422729\dots$ door Baumert et al. 1971). Het basis-tupel bevindt zich in $C_{21}^{\boxtimes 4}$ , geïtegreerd naar macht 4096.
$\Theta(C_{23})$ : Verbeterd naar $\geq 11.328224257774\dots$ (voorheen $11.3278379\dots$ door Baumert et al. 1971). Het basis-tupel bevindt zich in $C_{23}^{\boxtimes 4}$ , geïtegreerd naar macht 2048.

De verbeteringen, hoewel numeriek klein (variërend van $10^{-5}$ tot $10^{-3}$ ), vertegenwoordigen de huidige stand van zaken voor deze specifieke cycli.

Betekenis en claims
Het artikel claimt betekenis primair door de rigoureuze verificatie van deze resultaten. Door de gehele constructie en de resulterende grenzen te formaliseren in Lean, waarborgen de auteurs dat de complexe combinatorische argumenten en de specifieke verzamelingenconstructies vrij zijn van menselijke fouten. Het werk volgt het traject van recent onderzoek dat gebruikmaakt van grote taalmodellen (LLM's) om initiële constructies te ontdekken (zoals gezien in [IRCR26] en [Gao26]), maar onderscheidt zich door het bieden van een volledig geformaliseerd, machine-gecontroleerd bewijs van de geldigheid van de basis-tupels en de correctheid van de toepassing van het bestaande productlemma van Gao. De auteurs beweren niet het algemene probleem van de Shannon-capaciteit voor oneven cycli te hebben opgelost, noch stellen zij nieuwe theoretische kaders voor buiten de toepassing van Gao's bestaande productlemma; in plaats daarvan leveren zij de best bekende numerieke ondergrenzen voor deze specifieke instanties, geverifieerd met wiskundige zekerheid.

Het Spel van Veilige Kruispunten

De Nieuwe Records

De Digitale Scheidsrechter

Waarom het ertoe doet

Technische Samenvatting: Lean-geverifieerde ondergrenzen voor de Shannon-capaciteit van oneven cycli

Meer zoals dit