Shannon capacities of odd cycles
Follow the latest progress by email.
The Shannon capacity of an odd cycle measures asymptotic independent-set growth in its strong powers. The target is better explicit lower bounds for C7,C11,C13,C15,C19,C21,C23; reported examples include 3.258805369885… for C7 and 5.294502522149… for C11.
Why it matters and what counts as progress
Why it matters: It narrows concrete zero-error capacity gaps using finite independent-set constructions and product amplification.
What counts as progress: A larger independent set in an odd-cycle strong power giving a better capacity lower bound, or an upper bound narrowing the capacity gap.
How the problem developed
- 1956 · Definition [1]
Claude Shannon Introduced zero-error channel capacity, whose graph formulation gives the Shannon capacity problem.
- 1979 · Exact value [2]
László Lovász Determined the Shannon capacity of the five-cycle exactly, C( C₅ )=√5.
- 23 Jul 2026 · Lower bounds [3]
Itty et al., with LLM-assisted exploration Improved known lower bounds for the Shannon capacities of several odd cycles, including C₇, C₁₁, and C₁₃.
- 31 Jul 2026 · Formalized lower bounds [4]
Pjotr Buys, Sven Polak, and Jeroen Zuiddam Lean-verified further lower bounds for C₇, C₁₁, C₁₃, C₁₅, C₁₉, C₂₁, and C₂₃, using the reported construction methods.
AI contributions 2
AI-assisted improvement to the C₁₁ Shannon-capacity lower bound
An explicit independent set in the 213rd strong power of the 11-cycle gives Shannon capacity C₁₁ ≥ 5.295526013632343.
Lean-verified lower bounds for the Shannon capacity of odd cycles
Buys, Polak and Zuiddam give Lean-formalized Shannon-capacity lower bounds for C7, C11, C13, C15, C19, C21 and C23 using seven explicit base tuples and Gao’s product lemma. Their C7 bound is 3.258805369885… and their C11 bound is 5.294502522149….
Sources
- Claude E. Shannon, The zero error capacity of a noisy channel
- László Lovász, On the Shannon capacity of a graph
- Itty et al., Improved lower bounds for the Shannon capacity of odd cycles
- Pjotr Buys, Sven Polak, and Jeroen Zuiddam, Lean-verified lower bounds for the Shannon capacity of odd cycles
- Protti’s checked C₁₁ release
- Earlier C₁₁ certificate
- Buys, Polak and Zuiddam, Lean-verified odd-cycle capacity bounds
- Itty and coauthors, AI-generated odd-cycle independent sets
- Later C7 capacity improvement
Website timeline
Publication dates and editorial changes.
AI-assisted constructions yield Lean-checked odd-cycle capacity bounds
AI-assisted improvement to the C₁₁ Shannon-capacity lower bound