Improved lower bounds for the Shannon capacity of odd cycles

Technical Summary: Improved Lower Bounds for the Shannon Capacity of Odd Cycles

Problem Statement
The Shannon capacity $\Theta(G)$ of a graph $G$ quantifies the maximum zero-error communication rate over a noisy channel defined by $G$. It is defined as $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$, where $\alpha(G^d)$ is the independence number of the $d$-th strong product of $G$. While $\Theta(C_p) = p/2$ for even cycles and $\Theta(C_5) = \sqrt{5}$, the values for odd cycles $C_{2r+1}$ with $r > 2$ remain unknown. Determining $\Theta(C_7)$ is a notoriously difficult open problem. The standard approach to establishing lower bounds involves constructing large independent sets in strong products $C_k^d$ to maximize the quantity $\alpha(C_k^d)^{1/d}$.

Methodology
The authors employ an iterative interaction with a Large Language Model (LLM), specifically ChatGPT-5.6 Sol Pro, to discover explicit combinatorial constructions of independent sets. The methodology differs from traditional heuristic searches (such as simulated annealing or local search algorithms) which the authors note failed to reach the reported bounds despite extensive attempts.

The process involved:

1. Prompting: The authors provided the LLM with specific parameters: the cycle length ($k$), the product dimension ($d$), the best-known existing construction, and a target cardinality for improvement.
2. Generation and Execution: The model generated search programs, executed them within its environment, and returned candidate independent sets.
3. Iterative Refinement: The authors engaged in follow-up prompts to push the cardinality beyond the initial results found by the model.
4. Verification: All constructed sets were rigorously verified by the authors to ensure they constitute valid independent sets (i.e., no two vectors differ by at most 1 in every coordinate modulo $k$).

Key Contributions and Results
The paper presents improved lower bounds for the Shannon capacity of four specific odd cycles by constructing larger independent sets in their strong products:

• $C_7$ (7-Cycle): The authors constructed an independent set of size 134,753 in the strong 10-product $C_7^{10}$. This improves the previous best bound of $367^{1/5}$ (from an independent set of size 367 in $C_7^5$).

  • New Lower Bound: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (previously $> 3.257865$).
  • Construction Strategy: The set was derived by modifying the known size-367 set $R$ from Polak and Schrijver. The authors deleted specific vectors from $R$ to form a subset $B$, then constructed the final set $I$ using the Cartesian product $B \times B$ augmented with additional vectors derived from $R$ and specific transformations.

• $C_{11}$ (11-Cycle): An independent set of size 21,909 was found in $C_{11}^6$.

  • New Lower Bound: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (previously $148^{1/3} > 5.289572$).
  • Construction Strategy: Starting from the size-148 set in $C_{11}^3$, the authors defined specific subsets ($DL, DR, BL, BR$) and auxiliary vector sets ($F_A, F_B, \dots$) to construct the set in the 6-product.

• $C_{13}$ (13-Cycle): An independent set of size 62,530 was found in $C_{13}^6$.

  • New Lower Bound: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (previously $247^{1/3} > 6.274305$).
  • Construction Strategy: The LLM implemented a randomized local search on an auxiliary graph $G_A$ (with 134 vertices) to find a large independent set $S$ of 370 vectors in $\mathbb{Z}_{13}^4$. The final set $I$ was defined as $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$.

• $C_{15}$ (15-Cycle): An independent set of size 8,076,974 was found in $C_{15}^8$.

  • New Lower Bound: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (previously $2842^{1/4} > 7.301397$).
  • Construction Strategy: Starting from the size-2842 set in $C_{15}^4$, the authors deleted specific vectors and added others to form a base set $R$. The final set was formed by $B \times B$ (where $B \subset R$) augmented with vectors determined by lookup tables ($W_0, W_1$) based on adjacency conditions.

Additionally, the paper reports improved lower bounds on the independence numbers of several individual strong products that do not directly improve the Shannon capacity bounds (e.g., $\alpha(C_{11}^4) \geq 766$, $\alpha(C_{15}^3) \geq 383$).

Significance and Claims
The paper claims that these results represent modest improvements to the known lower bounds for $\Theta(C_7)$, $\Theta(C_{11})$, and $\Theta(C_{15})$, and a more significant improvement for $\Theta(C_{13})$.

The primary significance of the work lies in the methodology:

1. LLM Efficacy: The constructions were discovered through iterative interaction with an LLM, which produced independent sets that manual search heuristics (including simulated annealing and AI-constructed local search algorithms) failed to find despite months of effort.
2. Role of Knowledge: The authors suggest that the LLM's success may stem from its ability to leverage existing mathematical knowledge and modify known independent sets using "small" changes, highlighting the potential of LLMs for finding explicit combinatorial constructions.
3. Future Direction: The paper posits that studying the mechanisms allowing LLMs to surpass traditional search heuristics in finding independent sets is a valuable future research direction.

The authors remain modest regarding the magnitude of the numerical improvements (e.g., the increase in $\Theta(C_{15})$ is in the sixth decimal place) but emphasize the novelty of the discovery process. All constructions and code are made available in a public repository.