Source-linked AI summary
Improved lower bounds for the Shannon capacity of odd cycles
Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman
TL;DR
The paper addresses the difficulty of improving lower bounds on the Shannon capacity of odd cycles through larger independent sets in strong products. It uses iterative interactions with ChatGPT-5.6 Sol Pro to discover explicit constructions, obtaining improved bounds for C7, C11, C13, and C15 while also improving some independence-number bounds that do not affect Shannon capacity.
Problem
Exact Shannon capacities of odd cycles beyond C5 remain unknown, and even determining strong-product independence numbers is difficult.
Method
The authors supplied targeted odd-cycle instances and construction goals to ChatGPT-5.6 Sol Pro, which generated search programs and independent sets that the authors verified.
Results
Θ(C7) > 3.258020, Θ(C11) > 5.289773, Θ(C13) > 6.300109, and Θ(C15) > 7.301399.
Takeaways & Limitations
The constructions illustrate the potential of LLM interactions for finding explicit combinatorial constructions and improving odd-cycle Shannon-capacity bounds.
Takeaways & Limitations
The mechanisms enabling the LLM to surpass the authors’ search heuristics remain an open direction for future research.
Abstract
from arXiv · showhide
The Shannon capacity $Θ(G)$ of a graph $G$ quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. It is lower bounded by $α(G^d)^{1/d}$ for any $d$, where $α(G^d)$ is the independence number of the $d$-th strong product of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, $62530$ in $C_{13}^{6}$, and $8076974$ in $C_{15}^{8}$, improving the best known lower bounds for the Shannon capacity of these graphs to $Θ(C_7)\geq 134753^{1/10}>3.258020$, $Θ(C_{11})\geq 21909^{1/6}>5.289773$, $Θ(C_{13})\geq 62530^{1/6}>6.300109$, and $Θ(C_{15})\geq 8076974^{1/8}>7.301399$. We also improve the best known lower bounds on the independence numbers of several individual strong products of odd cycles that do not improve the Shannon capacity lower bound. The constructions were discovered through iterative interactions with a Large Language Model (LLM), illustrating the potential of LLMs for finding explicit combinatorial constructions.
1 Introduction
The paper improves lower bounds on the Shannon capacity of several odd cycles by constructing larger independent sets in strong products, while also reporting additional independence-number improvements. These constructions were discovered through interactions with an LLM and verified by the authors.
- 1 Introduction: For odd cycles beyond C5, the exact Shannon capacity remains unknown, including the notoriously difficult case of C7.The previous C7 bound came from an independent set of size 367 in C7^5, yielding Θ(C7) ≥ 367^1/5 > 3.2578 [12].
- 1 Introduction: Θ(C7) > 3.258020, Θ(C11) > 5.289773, Θ(C13) > 6.300109, and Θ(C15) > 7.301399.These bounds follow from explicit independent sets in the corresponding strong products and improve previous lower bounds.
- 1 Introduction: 134753 vectors form an independent set in C7^10, while additional constructions contain 21909 vectors in C11^6, 62530 in C13^6, and 8076974 in C15^8.The resulting bounds are summarized and compared with previous bounds in Table 1.
- 1 Introduction: The paper also improves several lower bounds on independence numbers of odd-cycle products without improving the corresponding Shannon-capacity bounds.For example, it reports α(C15^?) ≥ 383, improving the previous bound in, with further results given in Appendix B.
- 1 Introduction: The constructions were obtained using multiple prompts to ChatGPT-5.6 Sol Pro, while the authors verified feasibility and wrote the paper.The LLM was used for minor grammar and style edits as well as construction discovery.
- 1 Introduction: ChatGPT-5.6 Sol Pro found independent sets missed by the authors’ heuristics, including simulated annealing and AI-generated local search after more than three months of attempts.The authors connect this outcome to the possible role of mathematical knowledge and leave the mechanisms for future study.
2 Finding independent sets in strong products of odd cycles
Finding larger independent sets in strong products is a natural route to improving Shannon-capacity bounds, but the underlying optimization problems quickly become computationally difficult. The paper uses ChatGPT-generated search programs to produce explicit constructions for targeted odd-cycle instances.
- 2 Finding independent sets in strong products of odd cycles: Finding larger independent sets in suitable strong products is a natural approach to improving Shannon-capacity lower bounds.The approach is difficult because independence number is NP-hard to compute even approximately, while strong products grow exponentially with the exponent.
- 2 Finding independent sets in strong products of odd cycles: The exact value of α(C7^3) is unknown, and exact formulas for α(C2r+1^3) remain open for r > 3.These difficulties arise even for third strong products of odd cycles.
- 2 Finding independent sets in strong products of odd cycles: Earlier LLM-based work rediscovered or improved independence-number bounds, but none of those results improved Shannon-capacity lower bounds for odd cycles.FunSearch used a greedy algorithm discovered through evolutionary algorithms and LLMs, while later work improved a C15 product bound to 19946.
- 2.1 Our approach: For each instance, ChatGPT-5.6 Sol Pro received the cycle length, product dimension, best known construction, and target cardinality, then generated search programs and returned independent sets.The searches were conducted through the standard ChatGPT web interface.
3 Constructions
The paper constructs explicit independent sets in strong products of C7, C11, C13, and C15 by modifying known sets and augmenting products with carefully selected vectors. These constructions yield improved Shannon-capacity lower bounds for all four odd cycles.
- 3 Constructions: Vertices are represented by vectors over Zk, with adjacency in the strong product determined by circular distance at most 1 in every coordinate.This representation makes independence equivalent to every pair differing by more than 1 modulo k in at least one coordinate.
- 3.1 7-Cycle C7: 134753 vectors in C7^10 improve the bound to Θ(C7) ≥ 134753^1/10 > 3.258020.The construction uses B × B together with vectors derived from R, where B has 359 vectors and R has 367.
- 3.2 11-Cycle C11: 21909 vectors in C11^6 improve the bound to Θ(C11) ≥ 21909^1/6 > 5.289773.The set combines BL × BR with vectors formed from X and Y through the set-valued functions H and V.
- 3.4 15-Cycle C15: 8076974 vectors in C15^8 improve the bound to Θ(C15) ≥ 8076974^1/8 > 7.301399.Starting from a modified 2842-vector set, the construction forms B × B and adds vectors selected using the W0 and W1 matrices.
A ChatGPT Interactions
The authors used iterative ChatGPT interactions to search for explicit Cycle Codes, progressively improving constructions for odd-cycle strong products, including a final CC(10, 7, 134753).
- A ChatGPT Interactions: Each instance used an initial prompt describing the problem, format, prior construction, and target, followed by instructions to continue beyond each new result.The other cycle sizes were handled in independent chats; the C15 search later applied techniques from an earlier report.
- A ChatGPT Interactions: The search targeted Cycle Codes: m length-n words over {0,...,k-1} whose distinct pairs differ by more than 1 circularly in at least one position.The requested instances used k<=15, n<=10, and m<200000.
- A ChatGPT Interactions: The C7 search focused on n=10 because smaller-dimension improvements were insufficient to improve the Shannon-capacity bound.The existing benchmark was CC(5,7,367), while the n=10 target exceeded 134689.
- A ChatGPT Interactions: The initial C7 search found CC(10, 7, 134690), after which repeated follow-ups progressively increased the construction to CC(10, 7, 134753).Intermediate results were 134693, 134698, 134714, 134738, and 134751.
B Additional Lower Bounds on Independence Numbers
Beyond Shannon-capacity improvements, the searches produced larger independent sets for several individual strong powers of odd cycles, although these do not improve the underlying capacity bounds.
- B Additional Lower Bounds on Independence Numbers: Several constructions improved lower bounds on independence numbers without improving the Shannon-capacity bound of the underlying cycle.The constructions are summarized in Table 5.
- B Additional Lower Bounds on Independence Numbers: The entry 1101 for C6 7 is an elementary product construction derived from an independent set of size 367 in C5.
C.1 Auxiliary Set S for the C6 13 Construction
Table 6 presents the auxiliary set S used in the C6 13 construction.
- C.1 Auxiliary Set S for the C6 13 Construction: Table 6 lists the set S ⊆ Z4 13 consisting of 370 vectors.
C.2 Base Construction in C3
The base constructions include tabulated vector sets for the C11 construction and independent sets for products of cycles.
- C.2 Base Construction in C3: Table 7 lists 148 vectors in Z3 11 forming the basis for the C11 construction.
- C.2 Base Construction in C3: Table 8 lists an independent set of size 766 in C4.
- C.2 Base Construction in C3: Table 9 lists an independent set of size 383 in C3.