Improved lower bounds for the Shannon capacity of odd cycles

Technische Samenvatting: Verbeterde Ondergrenzen voor de Shannon-capaciteit van Oneven Cycli

Probleemstelling
De Shannon-capaciteit $\Theta(G)$ van een graaf $G$ kwantificeert de maximale foutloze communicatiesnelheid over een door $G$ gedefinieerde ruisige kanaal. Deze wordt gedefinieerd als $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$, waarbij $\alpha(G^d)$ het onafhankelijkheidsgetal is van de $d$-de sterke product van $G$. Terwijl $\Theta(C_p) = p/2$ geldt voor even cycli en $\Theta(C_5) = \sqrt{5}$, blijven de waarden voor oneven cycli $C_{2r+1}$ met $r > 2$ onbekend. Het bepalen van $\Theta(C_7)$ is een berucht moeilijk openstaand probleem. De standaardbenadering voor het vaststellen van ondergrenzen omvat het construeren van grote onafhankelijke verzamelingen in sterke producten $C_k^d$ om de grootte van de hoeveelheid $\alpha(C_k^d)^{1/d}$ te maximaliseren.

Methodologie
De auteurs maken gebruik van een iteratieve interactie met een Large Language Model (LLM), specifelijk ChatGPT-5.6 Sol Pro, om expliciete combinatorische constructies van onafhankelijke verzamelingen te ontdekken. De methodologie verschilt van traditionele heuristische zoekmethoden (zoals simulated annealing of lokale zoekalgoritmen), die volgens de auteurs faalden om de gerapporteerde grenzen te bereiken ondanks uitgebreide pogingen.

Het proces omvatte:

1. Prompting: De auteurs voorzagen het LLM van specifieke parameters: de cycluslengte ($k$), de productdimensie ($d$), de best bekende bestaande constructie, en een doelstelling voor de cardinaliteit voor verbetering.
2. Generatie en Executie: Het model genereerde zoekprogramma's, voerde deze uit binnen zijn omgeving en retourneerde kandidaat-onafhankelijke verzamelingen.
3. Iteratieve Verfijning: De auteurs gingen over tot vervolgprompts om de cardinaliteit boven de initiële resultaten die het model vond, te duwen.
4. Verificatie: Alle geconstrueerde verzamelingen werden rigoureus geverifieerd door de auteurs om te waarborgen dat ze daadwerkelijk geldige onafhankelijke verzamelingen vormen (d.w.z. dat geen twee vectoren in elke coördinaat modulo $k$ met maximaal 1 verschillen).

Belangrijkste Bijdragen en Resultaten
Het artikel presenteert verbeterde ondergrenzen voor de Shannon-capaciteit van vier specifieke oneven cycli door grotere onafhankelijke verzamelingen te construeren in hun sterke producten:

• $C_7$ (7-cyclus): De auteurs construeerden een onafhankelijke verzameling van omvang 134.753 in de sterke 10-product $C_7^{10}$. Dit verbetert de voorheen bekende grens van $367^{1/5}$ (afkomstig van een onafhankelijke verzameling van omvang 367 in $C_7^5$).

  • Nieuwe ondergrens: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (voorheen $> 3.257865$).
  • Constructiestrategie: De verzameling werd afgeleid door de bekende grootte-367 verzameling $R$ van Polak en Schrijver te modificeren. De auteurs verwijderden specifieke vectoren uit $R$ om een deelverzameling $B$ te vormen, en construeerden vervolgens de uiteindelijke verzameling $I$ met behulp van het Cartesiaanse product $B \times B$, aangevuld met extra vectoren afgeleid van $R$ en specifieke transformaties.

• $C_{11}$ (11-cyclus): Een onafhankelijke verzameling van omvang 21.909 werd gevonden in $C_{11}^6$.

  • Nieuwe ondergrens: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (voorheen $148^{1/3} > 5.289572$).
  • Constructiestrategie: Vertrekkend vanuit de grootte-148 verzameling in $C_{11}^3$, definieerden de auteurs specifieke deelverzamelingen ($DL, DR, BL, BR$) en hulpvectorverzamelingen ($F_A, F_B, \dots$) om de verzameling in de 6-product te construeren.

• $C_{13}$ (13-cyclus): Een onafhankelijke verzameling van omvang 62.530 werd gevonden in $C_{13}^6$.

  • Nieuwe ondergrens: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (voorheen $247^{1/3} > 6.274305$).
  • Constructiestrategie: Het LLM implementeerde een gerandomiseerde lokale zoekopdracht op een hulpgraaf $G_A$ (met 134 knopen) om een grote onafhankelijke verzameling $S$ van 370 vectoren in $\mathbb{Z}_{13}^4$ te vinden. De uiteindelijke verzameling $I$ werd gedefinieerd als $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$.

• $C_{15}$ (15-cyclus): Een onafhankelijke verzameling van omvang 8.076.974 werd gevonden in $C_{15}^8$.

  • Nieuwe ondergrens: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (voorheen $2842^{1/4} > 7.301397$).
  • Constructiestrategie: Vertrekkend van de grootte-2842 verzameling in $C_{15}^4$, verwijderden de auteurs specifieke vectoren en voegden anderen toe om een basisverzameling $R$ te vormen. De uiteindelijke verzameling werd gevormd door $B \times B$ (waarbij $B \subset R$) aangevuld met vectoren bepaald door lookup-tabellen ($W_0, W_1$) gebaseerd op nabijheidscondities.

Daarnaast rapporteert het artikel verbeterde ondergrenzen voor de onafhankelijkheidsgetallen van verschillende individuele sterke producten die de Shannon-capaciteitsgrenzen niet direct verbeteren (bijv. $\alpha(C_{11}^4) \geq 766$, $\alpha(C_{15}^3) \geq 383$).

Betekenis en Claims
Het artikel stelt dat deze resultaten bescheiden verbeteringen vertegenwoordigen van de bekende ondergrenzen voor $\Theta(C_7)$, $\Theta(C_{11})$ en $\Theta(C_{15})$, en een meer significante verbetering voor $\Theta(C_{13})$.

De primaire betekenis van het werk ligt in de methodologie:

1. Effectiviteit van LLM's: De constructies werden ontdekt via iteratieve interactie met een LLM, die onafhankelijke verzamelingen produceerde die handmatige zoekheuristieken (inclusclusief simulated annealing en door AI geconstrueerde lokale zoekalgoritmen) niet konden vinden, ondanks maandenlange inspanning.
2. Rol van Kennis: De auteurs suggereren dat het succes van het LLM mogelijk voortkomt uit het vermogen om bestaande wiskundige kennis te benutten en bekende onafhankelijke verzamelingen te modificeren met "kleine" wijzigingen, wat het potentieel van LLM's voor het vinden van expliciete combinatorische constructies benadrukt.
3. Toekomstige Richting: Het artikel stelt dat het bestuderen van de mechanismen die het mogelijk maken voor LLM's om traditionele zoekheuristieken te overtreffen bij het vinden van onafhankelijke verzamelingen, een waardevolle toekomstige onderzoeksrichting is.

De auteurs blijven bescheiden over de omvang van de numerieke verbeteringen (bijv. de toename van $\Theta(C_{15})$ is in de zesde decimaal) maar benadrukken de nieuwheid van het ontdekkingsproces. Alle constructies en code worden beschikbaar gesteld in een publieke repository.