Improved lower bounds for the Shannon capacity of odd cycles

Source: arXiv:2607.21517 · Published 2026-07-23 · By Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

TL;DR

This paper addresses a long-standing open problem in information theory and combinatorics: improving lower bounds for the Shannon capacity of odd cycles, denoted Θ(C_k). The Shannon capacity quantifies the maximum zero-error communication rate over a noisy channel modeled by a graph. While Θ(C_5) is known exactly due to Lovász’s ϑ-function, values for odd cycles with more vertices, such as C_7, C_11, and C_13, remain unknown. Existing lower bounds rely on constructing large independent sets in strong powers of these cycles, but obtaining larger independent sets is computationally challenging due to exponential growth in graph size and NP-hardness of the independence number problem. This work leverages iterative interactions with a large language model (ChatGPT-5.6 Sol Pro) to generate new combinatorial constructions of large independent sets in high powers of odd cycles. The authors find independent sets of size 134,753 in C_7^{10}, 21,909 in C_{11}^{6}, and 62,530 in C_{13}^{6}, surpassing all previously known constructions. These yield improved lower bounds: Θ(C_7) > 3.258020, Θ(C_{11}) > 5.289773, and Θ(C_{13}) > 6.300109. The results also include improved lower bounds for individual powers of other odd cycles without improving the Shannon capacity directly. Reliable verification and detailed constructions ensure correctness and demonstrate the potential of LLMs to discover explicit mathematical structures previously inaccessible to heuristic searches over months.

Key findings

• Constructed an independent set of size 134,753 in the 10th strong power of 7-cycle (C_7^{10}), improving previous best lower bound on Θ(C_7) from >3.257865 to >3.258020.
• Constructed an independent set of size 21,909 in the 6th strong power of the 11-cycle (C_{11}^{6}), improving previous best lower bound on Θ(C_{11}) from >5.289572 to >5.289773.
• Constructed an independent set of size 62,530 in the 6th strong power of the 13-cycle (C_{13}^{6}), improving previous best lower bound on Θ(C_{13}) from >6.274305 to >6.300109.
• Improved lower bound on independence number of C_3^{15} from 382 to 383, demonstrating improvements on other powers without raising Shannon capacity lower bounds.
• ChatGPT-5.6 Sol Pro succeeded in finding constructions and independent sets that manual heuristic searches, including simulated annealing and state-of-art local search methods, failed to find after months.
• The approach confirms that the Shannon capacity of odd cycles remains difficult to compute exactly but can be incrementally improved using AI-assisted mathematical exploration.
• The authors publicly released code, generated constructions, prompts, and verification scripts, enabling reproducibility.
• Improved independent sets for C_7, C_11, and C_13 strong powers push the largest known explicit zero-error codes for corresponding channel models.

Threat model

n/a — This is a theoretical combinatorial research paper addressing explicit constructions of independent sets in graph powers. There is no adversary or security threat model considered.

Methodology — deep read

1. Threat model & assumptions: The paper studies the combinatorial problem of constructing large independent sets in the d-th strong powers of cycle graphs C_k, where vertices represent length-d vectors over Z_k, edges impose constraints on coordinate differences by ≤1 circularly. The adversary is the intrinsic computational hardness of finding maximum independent sets (NP-hard), with no external attacker. The goal is explicit constructive improvements for Shannon capacity lower bounds.

2. Data: The initial known independent sets come from literature: e.g., size 367 in C_7^5 [Polak & Schrijver, 2019], size 148 in C_11^3 [Baumert et al. 1971], size 247 in C_13^3 [Bohman et al. 2013]. These sets serve as bases for new constructions. The datasets are combinatorial sets of integer vectors modulo k.

3. Architecture / algorithm: The authors use a human-LLM iterative workflow. The input is a prompt describing the cycle length, product dimension, existing independent set constructions, and target cardinality goal. The LLM generates programmatic search algorithms to produce larger independent sets, combining arithmetic manipulations and set theory operations on vectors. Core novelty lies in how multiple sets are combined and augmented (e.g., deleting subsets, defining mappings h_j and v_j for C_7^10) to build larger independent sets. For C_13^6, a linear algebraic approach defines an auxiliary graph G_A via a matrix A and uses randomized local search to find large independent sets mapped back to the strong product.

4. Training regime: Not applicable; this is a symbolic combinatorial search. The “training” corresponds to prompt engineering and iterative conversational refinement with ChatGPT-5.6 Sol Pro, pushing the model to incrementally improve independent set size over multiple prompts.

5. Evaluation protocol: Correctness is verified by the authors by checking that no pair of distinct vertices in the constructed set are adjacent under the strong product graph definition (coordinate differences ≤1 circularly). Metrics are the independent set sizes and implied lower bounds on Θ(C_k). Baselines are previous largest known independent sets from the literature. The paper provides exact cardinalities and corresponding lower bounds.

6. Reproducibility: The authors released all code, generated independent sets, prompts, and verification scripts on GitHub https://github.com/nathanielitty/lower-bounds-for-shannon-capacity. The seed data sets from prior work are referenced and included where applicable.

A concrete example end-to-end for C_7^{10} involves starting with known R (size 367 in C_7^5), removing a small set of 8 vectors to form B (359 vectors), constructing sets X, PH, PV with defined operations modulo 7, defining functions h_j and v_j to augment the product B×B with additional vectors, forming I with 134,753 vectors. Verification ensures no two distinct vectors in I differ by ≤1 in all 10 coordinates (mod 7).

This step-by-step constructive approach, guided by the LLM, yields the largest known independent set in C_7^{10}, improving the Shannon capacity lower bound.

Technical innovations

• Use of iterative prompting and program synthesis via Large Language Models (ChatGPT-5.6 Sol Pro) to discover new large independent sets in strong powers of odd cycles, outperforming months of heuristic searches.
• Novel algebraic and combinatorial constructions combining deletion, augmentation, and set operations in the vector space Z_k^n to build larger independent sets than simple product sets (e.g., for C_7^{10}, the set I combining B×B with h_j, v_j-based augmentations).
• Construction of auxiliary graphs via matrix transformations (A in C_13^6) enabling randomized local search in a reduced search space to find independent sets that map back to large independent sets in the original strong power graph.
• Detailed closed-form descriptions of new independent sets with explicit vector sets and combinatorial operations, establishing improved exact cardinalities.
• Demonstration that AI-generated mathematical knowledge can meaningfully contribute to explicit zero-error capacity code design for high-dimensional noisy channels modeled by odd cycles.

Datasets

• C_7^{5} independent set — size 367 — from [Polak & Schrijver, 2019]
• C_{11}^3 independent set — size 148 — from [Baumert et al., 1971]
• C_{13}^3 independent set — size 247 — from [Bohman et al., 2013]
• Constructed sets for C_7^{10}, C_{11}^6, C_{13}^6 — sizes 134,753, 21,909, 62,530 respectively — generated by authors with code available at GitHub

Baselines vs proposed

• C_7: Previous Θ(C_7) lower bound from size 367 in C_7^5 yields >3.257865; proposed: size 134,753 in C_7^{10} yields >3.258020
• C_{11}: Previous Θ(C_{11}) lower bound from size 148 in C_{11}^3 yields >5.289572; proposed: size 21,909 in C_{11}^6 yields >5.289773
• C_{13}: Previous Θ(C_{13}) lower bound from size 247 in C_{13}^3 yields >6.274305; proposed: size 62,530 in C_{13}^6 yields >6.300109
• C_3^{15}: Previous best independence number 382; proposed 383 (does not improve Shannon capacity)

Limitations

• Improvements to Shannon capacity lower bounds are numerically modest, indicating the fundamental difficulty of the problem remains.
• Verification is combinatorial and empirical rather than a formal mathematical proof of optimality or exact capacity values.
• The approach heavily relies on the quality of LLM interactions which may not guarantee reproducibility or success in other combinatorial settings without human guidance.
• No adversarial or distribution shift evaluation since this is a pure combinatorial construction problem, not a learning system.
• Strong powers have exponentially growing vertex sets limiting scalability beyond moderate values of d and k.
• The construction methodology is somewhat specialized to odd cycle graphs and may not generalize easily to other graph classes without significant adaptation.

Open questions / follow-ons

• Can the approach be extended to construct even larger independent sets for other odd cycles or even larger powers to further improve Shannon capacity lower bounds?
• What are the theoretical limits or asymptotic behavior of the Shannon capacity for higher odd cycles, and can such AI-assisted combinatorial methods provide insights?
• Can the interplay of algebraic graph theory and AI-generated constructions lead to novel exact formulas or tighter bounds for α(G^d) where G is an odd cycle?
• How generalizable is the LLM-guided combinatorial search paradigm to other hard combinatorial or coding theory problems beyond odd cycles?

Why it matters for bot defense

Shannon capacity and zero-error communication problems inform fundamental limits on distinguishing complex patterns under noise, which is conceptually related to challenges in bot-detection and CAPTCHA design requiring reliable classification with minimal false positives. The techniques in this paper illustrate how explicit combinatorial constructions can push theoretical boundaries by combining human expertise with AI assistance. For bot-defense engineers, this research underscores the utility of computational and AI-driven combinatorial search approaches to discover or certify hard problem instances and constructions, potentially inspiring analogous strategies for designing or analyzing CAPTCHA puzzles with provable hardness properties or guaranteed security margins. However, direct application is limited since this paper addresses purely combinatorial graph capacities rather than adversarial machine learning or real-world bot behaviors.

Cite

@article{arxiv2607_21517,
  title={ Improved lower bounds for the Shannon capacity of odd cycles },
  author={ Nathaniel Itty and Christopher D. Rosin and Chase Carstensen and Daniel Reichman },
  journal={arXiv preprint arXiv:2607.21517},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.21517}
}

Read the full paper

• arXiv:2607.21517 (abstract)
• arXiv:2607.21517 (PDF)